Найти двоичное дерево, указанное только в порядке прохождения

Question

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

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

спасибо.

Answer 1

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

В качестве примера, если ваш ход в порядке [1,2,3,4,5,6,7,8], то даже если дерево сбалансировано, существует множество возможностей для корневого узла (а именно 4 или 5). Если дерево не должно быть сбалансированным, вы можете выбрать любой из них в качестве корневого узла.

Вот пример несбалансированным дерева можно построить после произвольно выбирая 4 в качестве корневого узла:

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

Предзаказ обхода для этого дерева даст 4,3,2,1,6,5,7,8. Опять же, если только требования, что вы просто найти в бинарное дерево, это так же действует как установка 1 в качестве корневого узла и делает все остальное, правый узел:

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

Предварительный заказ обход для это дерево будет 1,2,3,4,5,6,7,8. Поскольку эти деревья генерируют один и тот же обход в порядке, но разные предзаказные обходы, не гарантируется ни одно уникальное дерево, ни один единственный уникальный предварительный обход для данного обхода в порядке.

Answer 2

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

Но если вы хотите дерево, а затем просто выполнить произвольный перетасовка последовательности заказовМои, а затем вставить полученный рандомизированное последовательность в бинарном дереве поиска