Рубрики

ВОРОТА | GATE CS 2013 | Вопрос 43

Последовательность обхода предзаказа дерева двоичного поиска составляет 30, 20, 10, 15, 25, 23, 39, 35, 42. Что из перечисленного является последовательностью обхода после заказа того же дерева?
(А) 10, 20, 15, 23, 25, 35, 42, 39, 30
(В) 15, 10, 25, 23, 20, 42, 35, 39, 30
(С) 15, 20, 10, 23, 25, 42, 35, 39, 30
(D) 15, 10, 23, 25, 20, 35, 42, 39, 30

Ответ: (Д)
Объяснение: Чтобы построить двоичное дерево из заданных последовательностей обхода, одна из последовательностей обхода должна быть Inorder. Другая последовательность прохождения может быть либо Предзаказ, либо Постзаказ. Мы знаем, что обход Inorder в дереве бинарного поиска всегда в порядке возрастания, поэтому обход Inorder будет в порядке возрастания данного обхода Preorder, т.е. 10, 15, 20, 23, 25, 30, 35, 39, 42. Теперь мы имеем построить дерево из заданных обходов Inorder и Preorder.

Ссылки:
http://espressocode.top/construct-tree-from-given-inorder-and-preorder-traversal/
http://espressocode.top/data-structures-and-algorithms-set-31/

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

ВОРОТА | GATE CS 2013 | Вопрос 43

0.00 (0%) 0 votes