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

Префиксный обход (также известный как прямой обход, обход в прямом порядке, англ. pre-order traversal) — это один из способов обхода бинарного дерева, при котором сначала посещается корневой узел (вершина), затем рекурсивно обходится левое поддерево, и только после этого — правое поддерево. Префиксный обход относится к классу алгоритмов поиска в глубину (DFS, Depth-First Search) и широко применяется в информатике для сериализации деревьев, копирования структур данных и построения выражений в префиксной (польской) записи.

¶Определение и порядок обхода

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

1. Посетить корень (выполнить некоторое действие с данными узла, например, вывести его значение).
2. Рекурсивно выполнить префиксный обход левого поддерева.
3. Рекурсивно выполнить префиксный обход правого поддерева.

Для небинарных деревьев (например, n-арных) порядок сохраняется: сначала корень, затем последовательно все поддеревья слева направо.

¶Пример

Рассмотрим бинарное дерево со следующей структурой:

`` A / \ B C / \ \ D E F ``

Префиксный обход даст последовательность: A, B, D, E, C, F.

Порядок обхода:

• Посещаем корень A.
• Переходим в левое поддерево (B). Посещаем B.
• Переходим в левое поддерево B (D). Посещаем D.
• Возвращаемся к B, переходим в правое поддерево B (E). Посещаем E.
• Возвращаемся к A, переходим в правое поддерево (C). Посещаем C.
• Переходим в правое поддерево C (F). Посещаем F.

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

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

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

¶Реализация

¶Рекурсивная реализация

Рекурсивная версия алгоритма на псевдокоде:

`` function preorder(node): if node is null: return visit(node) // обработка корня preorder(node.left) // обход левого поддерева preorder(node.right) // обход правого поддерева ``

На языке Python:

```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

def preorder_traversal(root): result = [] def dfs(node): if not node: return result.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return result ```

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

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

`` function preorder_iterative(root): if root is null: return [] stack = [root] result = [] while stack is not empty: node = stack.pop() result.append(node.val) if node.right is not null: stack.push(node.right) if node.left is not null: stack.push(node.left) return result ``

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

¶Применение

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

• Сериализация и десериализация деревьев: последовательность префиксного обхода позволяет однозначно восстановить структуру дерева, если дополнительно сохранять информацию о пустых узлах (например, с помощью маркеров null). Этот подход применяется в форматах хранения данных, таких как JSON или XML, при передаче иерархических структур.
• Копирование (клонирование) дерева: при создании точной копии дерева префиксный обход позволяет сначала создать корень, а затем рекурсивно скопировать его поддеревья.
• Построение префиксной записи (польской нотации): в математических выражениях, представленных в виде дерева разбора, префиксный обход даёт выражение в префиксной форме, где оператор предшествует операндам. Например, выражение (a + b) c в виде дерева с корнем и левым поддеревом + даёт префиксную запись * + a b c.
• Вывод иерархических структур: префиксный обход используется для отображения файловой системы, каталогов или оглавлений, где сначала выводится родительский элемент, а затем его содержимое.
• Алгоритмы на графах: в задачах поиска в глубину на деревьях и ациклических графах префиксный обход применяется для топологической сортировки (в сочетании с постфиксным обходом) и для проверки изоморфизма деревьев.

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

• Префиксный обход лежит в основе алгоритма «обхода в прямом порядке» (preorder traversal) в теории графов, который является частным случаем DFS.
• В компиляторах префиксный обход используется для генерации кода в трехадресной форме, когда операция должна быть выполнена до вычисления операндов.
• Для полных бинарных деревьев (например, куч) префиксный обход не имеет практического смысла, так как структура таких деревьев обычно задаётся массивом, а не указателями.
• В некоторых языках программирования (например, в Lisp) префиксная запись является стандартной формой записи выражений, что напрямую связано с префиксным обходом синтаксического дерева.

¶Источники

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — Глава 12: Бинарные деревья поиска.
2. Седжвик Р. Фундаментальные алгоритмы на C++. — М.: ДиаСофт, 2002. — Часть 5: Деревья.
3. Кнут Д. Искусство программирования. Том 1: Основные алгоритмы. — 3-е изд. — М.: Вильямс, 2006. — Раздел 2.3: Обход деревьев.
4. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Вильямс, 2001. — Глава 4: Деревья.