восстановление дерева из его списков предварительного и последующего порядков

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

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

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

X является предком Y тогда и только тогда, когда X предшествует Y в предварительном порядке и находится после Y в последующем.

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

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

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

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

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

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

Давайте рассмотрим два заданных массива как pre [] = {1, 2, 4, 8, 9, 5, 3, 6, 7} и post [] = {8, 9, 4, 5, 2, 6, 7 , 3, 1}; В pre [] крайний левый элемент является корнем дерева. Поскольку дерево заполнено, а размер массива больше 1. Значение рядом с 1 в pre [] должно быть левым потомком root. Итак, мы знаем, что 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