Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 35

GATE

Рассмотрим последовательности меток, полученные с помощью следующих пар обходов на помеченном двоичном дереве. Какая из этих пар однозначно идентифицирует дерево?

(i)     preorder and postorder
(ii)    inorder and postorder
(iii)   preorder and inorder
(iv)   level order and postorder

(A) (I) только
(B) (ii), (iii)
(C) (iii) только
(D) (iv) только

Ответ: (Б)
Объяснение: Здесь мы рассматриваем каждый вариант, чтобы проверить, является ли он истинным или ложным.

1) Предзаказ и почтовый заказ


Для вышеуказанных деревьев,

Предзаказ AB

Почтовый перевод BA

Это показывает, что предварительный заказ и почтовый заказ не могут однозначно идентифицировать дерево.

2) Inorder и postorder определяют дерево однозначно

3) Предзаказ и порядок также определяют дерево однозначно

4) Levelorder и postorder не могут однозначно определить дерево. Для приведенного выше примера

Уровень порядка AB

Почтовый перевод BA

См. Http://espressocode.top/if-you-are-given-two-traversal-sequence-can-you-construct-the-binary-tree/ для получения подробной информации.

Это решение предоставлено Анил Сайкришна Деварасетты
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2004 | Вопрос 35

0.00 (0%) 0 votes