Реконструировать дерево из своих предзаказов и списков ордеров

Ответ 1

Вы не можете использовать только один список, потому что вы не почувствуете глубину дерева. Таким образом, вам определенно требуется два или более списков.

Здесь моя попытка решения:

Используйте обход предлога, чтобы узнать порядок заказа данных. Это имеет смысл, потому что вы знаете, что первый node является вершиной, и вы знаете, что данные, расположенные слева от обхода, принадлежат левому краю дерева и т.д.

Ваш обход по порядку может определять глубину дерева. Например, допустим, у меня есть такая структура:

      1
  2   5   6
 3 4  7

Where 2 is the parent of 3 and 4, and 5 is the parent of 7.

Preorder: 1 2 3 4 5 7 6
Postorder: 3 4 2 7 5 6 1

Мы знаем, что мы начинаем с 1, потому что это первый node в обходе предзаказов. Затем мы посмотрим на следующее число. 2. В почтовом порядке, потому что число 2 идет до node 1, мы знаем, что 2 должно быть дочерним числом 1. Далее мы смотрим на 3. 3 приходит до 2 и таким образом, 3 - это ребенок из 2. 4 - до 2, но после 3, поэтому мы знаем, что 4 - это ребенок 2, но НЕ ребенок из 3. Etc.

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

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

Edit2:. Здесь может быть доказательство: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber%3D17225&authDecision=-203

Я думаю, вам нужно купить документ, однако...

Здесь представлено письменное доказательство как решение:

http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf

Ответ 2

Предзаказ и почтовый заказ не определяют однозначно дерево.

В общем случае обход одного дерева не однозначно определяет структура дерева. Например, как мы видели, для обоих следующие деревья, обход прохода [1,2,3,4,5,6].

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

Такая же двусмысленность присутствует для предзаказов и порядка обходы. Обход предварительного порядка для первого дерева выше [4,2,1,3,5,6]. Вот другое дерево с тем же предзаказом ВТП.

    4
   / \
  2   1
     / \
    3   6
     \
      5

Аналогично, мы можем легко построить другое дерево, чей постформер обход [1,3,2,6,5,4] совпадает с обходом первого дерева.

Ответ 3

Рассмотрим произвольное дерево T как четверку (A, B, C, D), где A - корень node, B - корень node первого ребенка, C - это вектор любых непустых детей из B, а D - вектор любых непустых братьев из B. Элементы C и D сами являются деревьями.

Любой из A, B, C и D может быть пустым. Если B пусто, то должно быть C и D; если A, то все.

Поскольку узлы уникальны, множества узлов, содержащиеся где-либо внутри C и D, не пересекаются, и ни один из них не содержит A или B.

Функции pre() и post() генерируют упорядоченные последовательности вида:

pre (T) = [A, B, pre (C), pre ( D)]

post (T) = [post (C), B, post ( D), A]

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

Теперь рассмотрим случаи:

• если A пуст, вывод обеих функций - это пустая последовательность []
• если B пуст, вывод обеих функций - это просто [A]
• если C и D пусты, pre (T) = [A, B] и post (T) = [B, A]
• если только C пуст, pre (T) = [A, B, D '] и post (T) = [B, D' ', A] (где простые числа указывают на некоторую перестановку узлов, содержащихся в D)
• если только D пуст, pre (T) = [A, B, C '] и post (T) = [ C' ', B, A]
• если ни один не пуст, pre (T) = [A, B, C ', D'] и post (T) = [ C ' ', B, D' ', A]

Во всех случаях мы можем однозначно разбивать элементы двух выходных последовательностей на соответствующие подпоследовательности, используя A и B (если они есть) в качестве разделителей.

Тогда возникает вопрос: можем ли мы также разбивать векторные последовательности? Если можно, то каждый может быть рекурсивно обработан, и мы закончили.

Так как результат pre() всегда будет цепочкой последовательностей, начиная с узлов A, а результат post() всегда будет цепочкой последовательностей, заканчивающихся узлами A, мы действительно можем разделить их, при условии, что узлы A никогда не пусты.

Здесь процесс падает в случае двоичных (или даже любых) деревьев с фиксированными дочерними элементами, которые могут быть независимо пустыми. Однако в нашем случае мы определили C и D, чтобы содержать только непустые узлы, и, следовательно, восстановление будет работать.

Ум, я так думаю. Очевидно, это просто аргумент, а не формальное доказательство!

Ответ 4

Создайте двоичное дерево с этим ограничением, имеющим хотя бы один node, что этот node имеет только один дочерний элемент (справа или слева, нет разницы).

Теперь напишите его списки Предзаказ и Записи. затем попытайтесь восстановить дерево из этих списков. и вы понимаете, что на этом node вы не можете решить, что его ребенок прав или левый.

Ответ 5

Как уже указывалось другими, двоичное дерево не может быть восстановлено с использованием только обхода pre и post order. Один дочерний элемент node имеет неоднозначные обходы, которые не могут определить, является ли он левым или правым дочерним элементом, например. рассмотрите следующие предписания и постображивания: предзаказ: a, b postorder b, a

Он может создавать обе следующие деревья

a a  \/ b b Просто невозможно узнать, является ли b левым или правым ребенком без какой-либо дополнительной информации, такой как обход по порядку.

Ответ 6

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

X является предком Y, если X предшествует Y в предзаказе и находится после Y в postorder.

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

Существует также реализация на основе стека, которая выполняет итерацию через узлы предзапуска и удерживает в стеке любые узлы, которые являются кандидатами, как прямой родитель следующего предварительного порядка node. Для каждого предзаказа node повторно выворачивайте все узлы из стека, которые не являются родителями следующего предзаказа node. Сделайте этот node дочерний элемент верхнего node в стеке и вставьте его в стек.

Ответ 7

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

Рассмотрим два заданных массива как pre [] = {1, 2, 4, 8, 9, 5, 3, 6, 7} и post [] = {8, 9, 4, 5, 2, 6, 7, 3, 1}; В pre [] самый левый элемент - это корень дерева. Поскольку дерево заполнено и размер массива больше 1. Значение рядом с 1 в pre [] должно быть оставлено дочерним по отношению к корню. Итак, мы знаем, что 1 - корень, а 2 - оставшийся ребенок. Как найти все узлы в левом поддереве? Мы знаем, что 2 является корнем всех узлов в левом поддереве. Все узлы до 2 в столбце [] должны находиться в левом поддереве. Теперь мы знаем, что 1 является корнем, элементы {8, 9, 4, 5, 2} находятся в левом поддереве, а элементы {6, 7, 3} находятся в правом поддереве.

              1
            /   \
           /      \
 {8, 9, 4, 5, 2}     {6, 7, 3}

Мы рекурсивно следуем приведенному выше подходу и получаем следующее дерево.

      1
    /   \
  2       3
/  \     /  \

4 5 6 7 /\
 8 9