Докажите, что двоичные деревья с одинаковыми обходами по порядку и порядку одинаковы?

Question

Кто-нибудь знает, как доказать , что если два бинарных дерева имеют одинаковые обходы по порядку и по порядку, то они идентичны? (возможно, показывая, что у вас не может быть двух разных двоичных деревьев с одинаковыми обходами по порядку и по предзаказу)

В качестве альтернативы, показать случай, который опровергает это, или показать, почему это не может быть сделано?

(Я признаю, это чисто академическое, но это не домашняя работа или что-то в этом роде. Мои инстинкты говорят мне, что это правда, но я не думаю, что когда-либо делал какие-либо доказательства на графиках.)

Answer 1

Основная идея состоит в том, как реконструировать двоичное дерево по заданным обходам и порядку.

Можно восстановить только одно двоичное дерево из обходов по порядку и предзаказу.

См .:

• Нерекурсивные алгоритмы для реконструировать двоичное дерево из его обходы (бумага)
• восстановление дерева по его списки предварительных и почтовых заказов (ТАК вопрос)