Обход дерева¶

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

¶История

Понятие обхода дерева возникло одновременно с развитием теории графов и структур данных в середине XX века. Первые алгоритмы обхода были разработаны для бинарных деревьев поиска, которые активно использовались в компиляторах (например, для обхода синтаксического дерева) и базах данных. В 1960-х годах Дональд Кнут в своей работе «Искусство программирования» систематизировал методы обхода, введя термины «префиксный», «инфиксный» и «постфиксный» обходы. С развитием вычислительной техники алгоритмы обхода стали применяться для обработки XML/HTML-документов, графов социальных сетей, файловых систем и нейронных сетей.

¶Классификация обходов

Обходы деревьев делятся на два основных класса: обход в глубину (Depth-First Search, DFS) и обход в ширину (Breadth-First Search, BFS). Внутри каждого класса существуют вариации, зависящие от порядка обработки узлов.

¶Обход в глубину (DFS)

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

• Прямой обход (Pre-order): сначала посещается корень, затем левое поддерево, затем правое поддерево. Используется для копирования дерева или создания префиксной записи выражений.
• Симметричный обход (In-order): сначала посещается левое поддерево, затем корень, затем правое поддерево. Для бинарного дерева поиска (BST) этот обход выдаёт узлы в отсортированном порядке.
• Обратный обход (Post-order): сначала посещается левое поддерево, затем правое поддерево, затем корень. Применяется для удаления дерева (сначала удаляются листья, затем корень) или вычисления постфиксной записи.

¶Обход в ширину (BFS)

Обход в ширину, также известный как уровневый обход (Level-order), посещает узлы по уровням: сначала корень, затем все узлы первого уровня, затем второго и так далее. Реализуется с помощью очереди. BFS используется для поиска кратчайшего пути в невзвешенных графах, а также для печати дерева по уровням.

¶Реализация обходов

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

Рекурсивные алгоритмы обхода наиболее просты и интуитивно понятны. Псевдокод для бинарного дерева:

``` // Прямой обход function preorder(node): if node is not null: visit(node) preorder(node.left) preorder(node.right)

// Симметричный обход function inorder(node): if node is not null: inorder(node.left) visit(node) inorder(node.right)

// Обратный обход function postorder(node): if node is not null: postorder(node.left) postorder(node.right) visit(node) ```

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

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

`` function iterativePreorder(root): stack = [root] while stack is not empty: node = stack.pop() if node is not null: visit(node) stack.push(node.right) // правый узел кладётся первым, чтобы левый обрабатывался раньше stack.push(node.left) ``

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

`` function levelOrder(root): queue = [root] while queue is not empty: node = queue.dequeue() if node is not null: visit(node) queue.enqueue(node.left) queue.enqueue(node.right) ``

¶Применение обходов

Обходы деревьев лежат в основе многих алгоритмов и систем:

• Компиляторы и интерпретаторы: обход синтаксического дерева (AST) для генерации кода, оптимизации и анализа.
• Базы данных: обход индексов (например, B-деревьев) для поиска и сортировки записей.
• Файловые системы: рекурсивный обход каталогов для поиска, копирования или удаления файлов.
• Искусственный интеллект: обход дерева решений в алгоритмах машинного обучения (например, Random Forest).
• Веб-разработка: обход DOM-дерева для манипуляции элементами страницы (например, в JavaScript).
• Графика и игры: обход деревьев сцены (scene graph) для рендеринга и обработки коллизий.

¶Сложность и память

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

• Рекурсивные обходы в глубину требуют O(h) дополнительной памяти для стека вызовов, где h — высота дерева (в худшем случае h = n для вырожденного дерева).
• Итеративные обходы с явным стеком также требуют O(h) памяти.
• Обход в ширину требует O(w) памяти, где w — максимальная ширина дерева (количество узлов на одном уровне). В худшем случае w = n/2 для полного бинарного дерева.

¶Особые случаи

¶Обход N-арных деревьев

Для деревьев, где каждый узел может иметь произвольное количество дочерних элементов (например, в файловой системе), обход в глубину выполняется аналогично, но с перебором всех дочерних узлов. Прямой обход N-арного дерева:

`` function preorderNary(node): if node is not null: visit(node) for child in node.children: preorderNary(child) ``

¶Обход с возвратом (Backtracking)

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

¶Моррисов обход (Morris traversal)

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

¶Критика и ограничения

• Рекурсивные обходы могут привести к переполнению стека при глубоких деревьях (например, в языках с ограниченной глубиной рекурсии, таких как Python).
• Итеративные обходы сложнее в реализации и менее читаемы.
• Обход в ширину требует больше памяти для широких деревьев.
• Моррисов обход изменяет структуру дерева, что может быть недопустимо в многопоточных средах или при неизменяемых данных.

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

• В компиляторах обход AST в прямом порядке используется для генерации кода, а в обратном — для вычисления значений.
• В языке Lisp обход списков (которые являются бинарными деревьями) лежит в основе всего синтаксиса.
• Алгоритм обхода в ширину впервые был описан в 1959 году Эдсгером Дейкстрой для поиска кратчайшего пути в графе.

¶Источники

• Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. — М.: Вильямс, 2010.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
• Седжвик Р., Уэйн К. Алгоритмы на Java. — М.: Вильямс, 2016.
• Aho A. V., Hopcroft J. E., Ullman J. D. Data Structures and Algorithms. — Addison-Wesley, 1983.