Как востановить бинарное дерево?

Question

[click_f]

Допустим у нас имеется линейная безскобочная запись бинарного дерева, которую мы получили префиксным/инфиксным/постфиксным обходом. Как можно востановить структуру бинарного дерева?
Пример вывода, вершины: abcdef...
Правильно ли я понимаю, что вточности востановить дерево не удастся?

Answer 1

[Mercury13]

Если одним префиксным/инфиксным/постфиксным — то, разумеется, нет. А если двумя — дело уже интереснее (при условии, разумеется, что все узлы разные).
Ну, например, как восстановить дерево, которое было пройдено сначала префиксно, потом постфиксно (самый сложный и интересный случай). Признаюсь сразу: полное восстановление невозможно, ведь ситуации «без левых сыновей» и «без правых сыновей» различить нельзя.

Если длины не совпадают, СТОП: некорректные данные.
В префиксном обходе корень в начале, в постфиксном — в конце. Если они не одинаковы, СТОП: некорректные данные.
Если в обходе один элемент — с этим всё понятно.
Второй элемент префиксного обхода — левый сын. Ищем его в постфиксном обходе. Если он предпоследний — перед нами та самая ситуация «у дерева один сын», и рекурсивно запускаем алгоритм на обходах без корня.
В противном случае выкусываем подстроки нужной длины (реально или виртуально), дважды запускаем алгоритм рекурсивно.

Пример: у нас дерево.

     a
  b    c
d  e   f

Префиксный обход abdecf, постфиксный debfca. Корень a, левый сын b, он в постфиксном обходе на третьей позиции. Рекурсивно запускаем алгоритм на парах bde/deb и cf/fc.