Конвертировать Preorder листинг бинарного дерева в postorder и наоборот

Question

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

РЕДАКТИРОВАТЬ: Другое данное предположение заключается в том, что метка каждого узла является уникальной и имеет поле, которое будет идентифицировать его как внутренний узел или лист. Я думаю, что это должно избавить от неоднозначности одного предварительного заказа или почтового заказа, способного однозначно идентифицировать дерево.

Answer 1

Не предполагая, что узлы в дереве имеют поле, которое идентифицирует себя как внутреннее или конечное, вы не сможете найти уникальный ответ на свой вопрос. Это предположение или список заказа должен быть доступен, чтобы найти уникальное дерево. В этом случае, чтобы найти один из возможных ответов, вы можете построить дерево в форме, показанной ниже, чтобы соответствовать любому заданному списку почтового заказа:

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

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

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

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

Answer 2

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

Answer 3

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

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]