Преобразовать предварительный порядок двоичного дерева в обратный и наоборот

Не предполагая, что узлы в дереве имеют поле, которое идентифицирует себя как внутреннее или листовое, вы не сможете найти уникальный ответ на свой вопрос. Это предположение или упорядоченный список должны быть доступны для поиска уникального дерева. В этом случае, чтобы найти один возможный ответ, вы можете построить дерево формы, показанной ниже, чтобы соответствовать любому данному листингу в обратном порядке: (предположим, что список в обратном порядке: 1 2 3 4 5 6 7 8 9)

9[7[5[3[1,2],4],6],8]

Теперь вы можете сделать предварительный заказ, используя это дерево.

Предполагая, что узлы в дереве имеют поле, которое идентифицирует себя как внутреннее или листовое, мы можем создать уникальное дерево из листинга в обратном порядке для этого типа деревьев с помощью следующего алгоритма:

1. Проведите сканирование с начала списка обратного порядка и найдите первый внутренний узел. У этого узла будет ровно два дочерних листа, которые предшествуют этому узлу в листинге в обратном порядке.
2. В вашей древовидной структуре добавьте этот внутренний узел и сделайте два предыдущих узла в списке его дочерними элементами.
3. Удалите этих двух дочерних элементов из списка и сделайте этот внутренний узел листом.
4. Перейдите к шагу 1 и повторяйте, пока список не станет пустым.

Рассмотрим рекурсивную структуру обхода предварительного порядка:

T(r) = [r, T(r->left), T(r->right)]
where T(r) is the preorder traversal of tree rooted at node r

Тогда мы знаем, что корень дерева, описываемого T(r), всегда является первым узлом в обходе.

Зная это и зная, что корень всегда выше в дереве, чем его поддеревья, подумайте, как бы вы использовали эту информацию для перестроения дерева. Думайте рекурсивно.

Предостережение: это можно сделать только в том случае, если это бинарное дерево поиска, которое ограничивает число узлов таким образом, что left-child < root < right-child. Как правило, деревья не могут быть восстановлены за один проход. См. этот превосходный ресурс для получения более подробной информации. .

Неоднозначность все еще существует независимо от правила об 0 или 2 дочерних элементах:

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

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

Оба имеют предварительный обход [4 2 1 3 5 6 7]

Например: вам необходимо преобразовать форму постзаказа в форму предзаказа. Это можно сделать следующим образом. почтовый заказ: DEBBCA предварительный заказ: ABDECF мы видим, что A является корнем. и из предварительного порядка мы можем определить, что узел B остается для A. Поэтому мы создаем два подкласса, которые являются (BED) (CF). Теперь, когда мы пересекаем B, мы берем его как корень, и мы видим, что после B, D ПРИСУТСТВУЕТ , это означает, что D находится слева от B, а E справа от B. Теперь мы пересекаем C. Примем его за корень. Тогда F присутствует после C, поэтому он считается левым.