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

Question

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

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

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

Answer 1

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

Возможна реконструкция только одного бинарного дерева с учетом порядка и порядка.

См:

• Nonrecursive algorithms for reconstructing a binary tree from its traversals (бумага)
• reconstructing a tree from its preorder and postorder lists (SO вопрос)