Рубрики

Если вам даны две последовательности обхода, можете ли вы построить двоичное дерево?

Это зависит от того, какие обходы даны. Если одним из методов обхода является Inorder, то дерево может быть построено, в противном случае — нет.

Следовательно, следующая комбинация может однозначно идентифицировать дерево.

Порядок и предзаказ.
Inorder и Postorder.
Порядок и уровень порядка.

А следующих нет.

Postorder и Preorder.
Предзаказ и Уровень-порядок.
Почтовый перевод и уровень заказа.

Например, обходы Preorder, Level-order и Postorder одинаковы для деревьев, представленных на диаграмме выше.

Предварительный заказ = AB
Обход почтового заказа = BA
Уровень порядка обхода = AB

Таким образом, даже если три из них (Pre, Post и Level) заданы, дерево не может быть построено.

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

Если вам даны две последовательности обхода, можете ли вы построить двоичное дерево?

0.00 (0%) 0 votes