восстановление дерева по спискам предзаказа и порядка

Question

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

Я считаю, что можно восстановить дерево именно из этих двух списков, и я думаю, что у меня есть алгоритм для этого, но я не доказал это. Поскольку это будет частью магистерского проекта, я должен быть абсолютно уверен, что это возможно и правильно (математически доказано). Однако он не будет в центре внимания проекта, поэтому мне было интересно, есть ли какой-нибудь источник (то есть бумага или книга), который я мог бы привести в качестве доказательства. (Может быть, в TAOCP? Кто-нибудь знает раздел возможно?)

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

---

Примечание: рассматриваемое дерево, вероятно, не будет двоичным, или сбалансированным, или чем-то, что сделало бы его слишком легким.

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

Примечание 3: узел может иметь любое количество дочерних элементов.

Примечание 4: Я забочусь только о порядке братьев и сестер. Левый или правый не имеет значения, когда есть только один ребенок.

Answer 1

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

Как правило, обход одного дерева однозначно не определяет структура дерева. Например, как мы видели, для обоих следующие деревья, прохождение обхода дает [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] совпадает с обходом первого дерева выше.

Answer 2

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

Вот моя попытка найти решение:

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

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

      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, потому что это первый узел в обходе предзаказа. Затем мы смотрим на следующее число 2. В почтовом порядке, поскольку число 2 приходит ДО узла 1, мы знаем, что 2 должно быть потомком 1. Затем мы смотрим на 3. 3 предшествует 2, и, таким образом, 3 является ребенком 2. 4 - до 2, но после 3, поэтому мы знаем, что 4 - ребенок 2, но НЕ ребенок 3 и т. д.

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

Редактировать: Порядок потомков сохраняется с этим решением, просто из-за знания упорядочения узлов через обход предзаказа, а затем знания структуры через обход пост-порядка.

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 / фа-CSE / учебники / tutorial09-solutions.pdf

Answer 3

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

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

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

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

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

сообщение (T) = [ сообщение ( C ) , B, сообщение ( 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 , чтобы они содержали только непустые узлы, поэтому реконструкция гарантированно сработает.

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

Answer 4

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

Может производить оба следующих дерева

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

Answer 5

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

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

Answer 6

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

Давайте рассмотрим два данных массива как 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 в post [] должны быть в левом поддереве. Теперь мы знаем, что 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

Answer 7

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

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

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

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