Сколько может быть последовательности BST уровня порядка с учетом последовательности preOrder и inOrder?

Question

Когда я пытаюсь напечатать уровень заказа BST, этот вопрос подсказывал мне.

Вот

Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8 
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8 

Последовательность заказа уровня для BST с выше pre_order и In_order является [4, 2, 6, 1, 3, 5, 7, 8]

Тем не менее, для того же предварительного заказа последовательность В-го порядка эта последовательность заказа уровня похоже возможно. [4, 1, 5, 2, 6, 3, 7, 8]. Я не знаю, как это сделать. Я пытаюсь понять это.

Я не могу построить BST в документе (чертеже), который удовлетворяет всем последовательностям последовательности pre_order, In-order и level.

Answer 1

Если у вас есть обход в порядке с одним из пред/послепорядка, этого достаточно для восстановления двоичного дерева. Кроме того, в случае BST (двоичный код поиск дерева) достаточно только после заказа или предварительного заказа.

В вашем случае, реконструирование BST от предварительного заказа 4, 1, 2, 3, 5, 6, 7, 8 дает следующее BST:

 4 
/ \ 
    1  5 
    \  \ 
    2  6 
    \  \ 
     3  7 
      \ 
       8 

, который дает, опять-таки уникальный, уровень порядка обхода [4,1,5,2,6,3,7,8].

Смотрите также:

• Reconstructing binary trees from tree traversals

Answer 2

следующая комбинация будет генерировать уникальный бинарное дерево (которое может быть БСТ).

Inorder and Preorder. 
Inorder and Postorder. 
Inorder and Level-order. 

Так что в вашем случае заказовМой & предварительного заказа приведен который будет генерировать уникальное бинарное дерево, которое BST в вашем случае так заказ уровня будет уникальным для этого дерева.

Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8 
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8 

SO дерево будет

level 0- 4 
level 1- 1,5 
level 2- 2,6 
level 3- 3,7 
level 4- 8 

заказ Уровень является

4,1,5,2,6,3,7,8

в сортировке всегда будет уникальный обход уровня порядка