Блог

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

Предварительный заказ:

 B C I J K H D E F G
  

Последующий порядок:

 I H K J C G F E D B
  

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

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

 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]
    }
}
  

итак, из inorder order мы можем заключить:

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

и из последующего порядка мы можем заключить:

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

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

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

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

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

   a         a
 /    vs.    
b             b
  

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