Постфиксный обход¶

Постфиксный обход (также известный как обратный обход, обход в порядке «левый — правый — корень», или LRN — Left-Right-Node) — это один из способов обхода бинарного дерева, при котором сначала рекурсивно посещаются все узлы левого поддерева, затем — все узлы правого поддерева, и только после этого обрабатывается корневой узел. Данный метод относится к классу алгоритмов обхода деревьев в глубину (DFS, Depth-First Search) и широко применяется в информатике для вычисления выражений, освобождения памяти и решения задач, требующих обработки дочерних узлов перед родительским.

¶Принцип работы

Постфиксный обход реализуется рекурсивно или с использованием стека. Алгоритм для каждого узла выполняет три шага:

1. Рекурсивно обойти левое поддерево.
2. Рекурсивно обойти правое поддерево.
3. Посетить (обработать) текущий узел.

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

¶Пример

Рассмотрим бинарное дерево с корнем +, левым потомком 2 и правым потомком , который, в свою очередь, имеет левого потомка 3 и правого потомка 4. Дерево представляет выражение 2 + 3 4.

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

¶Итеративная реализация

Хотя рекурсивная реализация проста и интуитивна, она может привести к переполнению стека при глубоких деревьях. Итеративный алгоритм постфиксного обхода требует использования двух стеков (или одного стека с дополнительной логикой). Один из распространённых методов:

1. Создать пустой стек stack и поместить в него корневой узел.
2. Создать второй стек output для хранения результата.
3. Пока stack не пуст:

• Извлечь узел из stack и поместить его в output.
• Если у узла есть левый потомок, поместить его в stack.
• Если у узла есть правый потомок, поместить его в stack.

1. После завершения цикла извлечь узлы из output — это и будет постфиксный порядок.

Данный метод использует тот факт, что порядок извлечения из output обратен порядку добавления, что даёт последовательность LRN.

¶Применение

¶Вычисление арифметических выражений

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

¶Освобождение памяти

В языках программирования с ручным управлением памятью (например, C++) постфиксный обход применяется для рекурсивного удаления узлов бинарного дерева. Поскольку сначала удаляются дочерние узлы, а затем родительский, это предотвращает потерю ссылок на поддеревья. Рекурсивная функция delete_tree(node) может выглядеть так: `` delete_tree(node): if node is not null: delete_tree(node.left) delete_tree(node.right) delete node ``

¶Построение синтаксических деревьев

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

¶Решение задач на деревьях

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

• Определение высоты дерева: высота узла вычисляется как максимум высот левого и правого поддеревьев плюс один.
• Проверка сбалансированности дерева (AVL-деревья).
• Подсчёт количества узлов, суммы значений или поиск максимального элемента.

¶Сравнение с другими обходами

Постфиксный обход отличается от префиксного (NLR) и инфиксного (LNR) порядков. В префиксном обходе сначала обрабатывается корень, затем левое и правое поддеревья. В инфиксном обходе для бинарного дерева поиска (BST) посещение узлов в порядке «левый — корень — правый» даёт отсортированную последовательность. Постфиксный обход, в отличие от них, не гарантирует упорядоченности значений, но обеспечивает обработку дочерних узлов перед родителем, что критично для ряда алгоритмов.

¶Интересные факты

• Постфиксный обход тесно связан с обратной польской записью, которая была предложена польским логиком Яном Лукасевичем в 1920-х годах. Однако сам термин «постфиксный обход» закрепился в теории алгоритмов позже, с развитием структур данных.
• В некоторых языках программирования, таких как Forth и PostScript, постфиксная нотация используется как основной способ записи выражений, что делает постфиксный обход естественным для их интерпретаторов.
• Алгоритм постфиксного обхода может быть реализован без рекурсии с использованием одного стека, если хранить в нём пары «узел, флаг посещения», что позволяет эмулировать рекурсивный вызов.

¶Источники

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание.
• Дональд Кнут. «Искусство программирования», том 1: «Основные алгоритмы».
• Никлаус Вирт. «Алгоритмы и структуры данных».
• Материалы курса «Структуры данных и алгоритмы» (Computer Science, ведущие университеты).