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

Могу ли я восстановить все двоичное дерево (count (vertices) = 2 ^ n-1) только из массива, который отсортирован так, как если бы я выполнял обратный обход?

Алгоритм, который я предлагаю, очень прост, просто для обхода после порядка:

  1. идите налево
  2. Иди направо
  3. current_vertex = массив [i ++]; // инициализировано i = 0

это должно сработать, не так ли?


binary-tree binary-search-tree postorder
person Avenger    schedule 24.03.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Нет, вы не можете, поскольку post order array из binary tree можно преобразовать в несколько двоичных деревьев, которые не совпадают, из которых невозможно узнать, какое из них было оригинальным.

Пример-

Массив почтовых заказов 2 3 5 может быть преобразован во многие деревья, например:

2        // 3 is right child of 2 and 5 of 5
  3
    5

or

  5     //2 is left child and 3 is right child of 5
2   3
person monster    schedule 25.03.2017
comment
первое дерево невозможно, потому что это целое (полное) двоичное дерево, поэтому есть только одно такое. - person Avenger; 25.03.2017