Проверка двоичного дерева с использованием заданного обхода

Question

Можно ли идентифицировать последовательности, для которых не существует бинарного дерева с учетом двух обходов (пример: в порядке и обход после ордера)?

Я понимаю, что последний элемент обхода послепорядка или первый элемент обхода предварительного заказа - это корень дерева. Используя такие основные факты, можно ли тестировать эти массивы без фактического построения дерева и выяснить, производят ли они одно и то же дерево?

У меня есть алгоритм, который может построить дерево из этих двух последовательностей (внутри и после), но я не хочу запускать алгоритм, если есть способ проверить массивы заранее. Это позволит сэкономить много времени, а не запустить алгоритм и выяснить в конце.

Примечание: Это НЕ должно быть двоичное дерево поиска. Бинарного дерева будет достаточно.

Answer 1

Я начинаю снова, так как вопрос немного отличается от того, что я думал. Учитывая обход порядка и постопераций, вы можете найти, есть ли дерево, которое может их генерировать?

Давайте рассмотрим это дерево:

 a 
/ \ 
    b  e 
/\ /\ 
c d f g 

В обходы являются:

inorder: CBDAFEG 
postorder: CDBFGEA 

Теперь некоторые наблюдения:

а. Последний узел в postorder всегда является корневым узлом.

b Если вы знаете корневой узел, вы можете разделить обход по порядку влево-обход, корень, правый обход.

Таким образом, вы можете без создания дерева запустить рекурсивный алгоритм, который определяет, могут ли они быть созданы одним и тем же деревом.

Как это:

Учитывая Io и Po как два traverals,

Если они имеют разную длину, то нет дерева общего.

Если же длина затем:

1. Возьмите последний узел Po - назовем его R
2. Find R в Ио. Если не найдено, нет общего дерева.

3. R определяет границы левого и правого суб дерева, так что разделение Io и Po на основе положения R в Io:

   CBD A FEG

   ЦКБ FEG A

(например, как только вы знаете, что левое вспомогательное дерево должно быть длиной 3 узла, а правое сиг-дерево также имеет длину 3 узла, вы также можете разделить Po так же)

4. Вызвать этот алгоритм рекурсивно в левом и правом поддеревах.

Answer 2

Я не думаю, что вы можете сделать это в общем случае, так как вы не можете определить структуру дерева только из обхода. То есть есть много деревьев, которые генерируют один и тот же обход.

Например, два дерева с одинаковым обходным порядком.

A      A 
/\     /
B C     B 
        /
         C 

Но их ход по-разному отличается. Таким образом, невозможно сказать, что данные в порядке и постоперационных обходах, если одно и то же дерево использовалось для их создания.