Можно ли создать двоичное неуникальное дерево, используя последовательности предварительного и последующего порядка?

Question

Можно ли создать двоичное неуникальное дерево, используя последовательности предварительного и последующего порядка?
Если да, то как это можно сделать? Например, как я могу сделать неуникальное дерево для:

Предзаказ:

B C I J K H D E F G

Postorder:

I H K J C G F E D B

Сколько их может быть?

Answer 1

предварительный заказ псевдокода:

preorder (tree)
{
    if tree isn't empty then
    {
        print key[tree]
        preorder left[tree]
        preorder right[tree]
    }
}

и почтовый заказ:

postorder (tree)
{
    if tree isn't empty then
    {
        preorder left[tree]
        preorder right[tree]
        print key[tree]
    }
}

, поэтому из порядка заказа мы можем сделать вывод:

• "B"должен быть корнем
• " C "должен быть дочерним элементом" B "
• " G "должен быть максимальным значением (самый дальний правый узел в дереве) или минимальнымзначение в левом поддереве (самый дальний левый узел в левом поддереве) - в этом случае «G» должен быть листом, а «F» должен быть родителем «G»

и из порядка после заказа мы можем сделать вывод:

• "I" должен быть листом и минимальным значением (самый правый узел в дереве).
• "H" долженбыть родителем "I" ("I" - это "H" левый потомок), если у меня нет детей, иначе "H" - следующий крайний левый потомок в дереве.

отсюдаэто похоже на судоку:

и да: с помощью выходов предварительного и пост-заказа вы можете построить дерево только одним способом.

Answer 2

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

Это минимальный пример

  a         a
 /    vs.    \
b             b

показывает два дерева, которые оба имеют предварительный порядок a b и последующий порядок b a.