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

Question

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

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

Answer 1

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

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

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

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

<Ол>

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

В своей древовидной структуре добавьте этот внутренний узел и сделайте два предыдущих узла в списке его дочерними.

Удалите этих двух дочерних элементов из списка и сделайте этот внутренний узел листом.

Перейдите к шагу 1 и повторяйте, пока список не станет пустым.

Answer 2

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

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]

Answer 3

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