Рубрики

Структуры данных | Обход дерева | Вопрос 11

Пусть LASTPOST, LASTIN и LASTPRE обозначают последнюю вершину, посещенную в обходе после заказа, порядка и предзаказа. Соответственно, из полного бинарного дерева. Что из следующего всегда верно? (GATE CS 2000)
(A) LASTIN = LASTPOST
(B) LASTIN = LASTPRE
(C) LASTPRE = LASTPOST
(D) Ничего из вышеперечисленного

Ответ: (Д)
Объяснение: Дано, что данное дерево является полным двоичным деревом . Для полного двоичного дерева последний посещенный узел всегда будет одинаковым для обхода по предварительному заказу и предварительному заказу. Ничто из вышесказанного не верно даже для полного двоичного дерева.

Опция (a) неверна, поскольку последний узел, посещенный в обходе Inorder, является правым дочерним, а последний узел, посещенный в обходе Postorder, является корневым.

Опция (c) неверна, поскольку последний узел, посещенный в обходе Предзаказа, является правым дочерним, а последний узел, посещенный в обходе Предзаказа, является корневым.

Для варианта (b) см. Следующий пример счетчика. Спасибо Хунайфу Мухаммеду за правильное объяснение.

     1
   /    \
  2      3
 / \    /
4   5  6  

Inorder traversal is 4 2 5 1 6 3
Preorder traversal is 1 2 4 5 3 6 

Тест на этот вопрос

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

Структуры данных | Обход дерева | Вопрос 11

0.00 (0%) 0 votes