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

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

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

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

13.10.2009 03:10:28
1 ОТВЕТ
РЕШЕНИЕ

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

Можно восстановить только один бинарное дерево из заказовМои и PREORDER обходов.

Видеть:

5
23.05.2017 12:01:26