Можно ли воссоздать двоичное дерево поиска (BST) только с его предварительным обходом?

Question

У меня есть предварительный обход для дерева. Не могу ли я просто воссоздать фактическое дерево только с этим? Большинство вопросов и статей, которые я видел, говорят, что нам нужен предварительный заказ и i-порядок, или пост-порядок и порядок.

Например:

Consider the BST created by inserting following nodes in order : 7 10 5 6 8 9 
Its preorder traversal is : 7 5 6 10 8 9 

И дерево создается с помощью 7 5 6 8 9 10 удивительно же, как исходного дерева. И это не только с этим набором узлов. Он работает с любым набором узлов.

Я что-то упустил?

Answer 1

Пожалуйста, исправьте меня, если я ошибаюсь.

(a) Вы не можете создать дерево только с обходным путем, потому что вы не знаете, что такое ваш корень.

(b) Технически ваши рассуждения могут быть применены к воссозданию дерева только с обходным порядком.

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

Например, рассмотрим обход 7 5 6 10 8 9. (i) Вы знаете, что 7 является корнем. (ii) 5 меньше 7. Так что сделайте это левым ребенком. (iii) 6 больше 5, но также менее 7. Поэтому сделайте его правильным ребенком 5. и т. Д.

Нам нужно будет отслеживать каждый корень (узел) в дереве ,