Обход дерева
В информатике обход дерева ( также известный как поиск по дереву и обход дерева ) является формой обхода графа и относится к процессу посещения (например, извлечения, обновления или удаления) каждого узла в древовидной структуре данных ровно один раз. Такие обходы классифицируются по порядку посещения узлов. Следующие алгоритмы описаны для бинарного дерева , но они могут быть обобщены и на другие деревья.
В отличие от связанных списков , одномерных массивов и других линейных структур данных , которые канонически обходят в линейном порядке, деревья можно обходить несколькими способами. Их можно пройти в порядке «сначала в глубину » или «сначала в ширину» . Есть три распространенных способа обхода их в порядке глубины: по порядку, предварительному порядку и последующему порядку. [1] Помимо этих базовых обходов, возможны различные более сложные или гибридные схемы, такие как поиск с ограничением по глубине, например итеративный поиск в глубину . Последний, как и поиск в ширину, также можно использовать для обхода бесконечных деревьев, см . ниже .
Обход дерева включает в себя итерацию по всем узлам тем или иным образом. Поскольку от заданного узла существует более одного возможного следующего узла (это нелинейная структура данных), то, предполагая последовательные вычисления (не параллельные), некоторые узлы должны быть отложены — каким-то образом сохранены для последующего посещения. Часто это делается через стек (LIFO) или очередь (FIFO). Поскольку дерево является самореферентной (рекурсивно определяемой) структурой данных, обход может быть определен рекурсией или, более тонко, корекурсией естественным и ясным образом; в этих случаях отложенные узлы неявно сохраняются в стеке вызовов .
Поиск в глубину легко реализуется через стек, в том числе рекурсивно (через стек вызовов), а поиск в ширину легко реализуется через очередь, в том числе корекурсивно. [2] : 45−61
При поиске в глубину (DFS) дерево поиска максимально углубляется перед переходом к следующему брату.
Для обхода бинарных деревьев с поиском в глубину выполните следующие операции в каждом узле: [3] [4]
- Предварительный заказ (узел посещается в позиции красного цвета ● ) :
F, B, A, D, C, E, G, I, H; - По порядку (узел посещается в позиции зеленого ● ) :
A, B, C, D, E, F, G, H, I; - Пост-заказ (узел посещается в позиции синего цвета ● ) :
A, C, E, D, B, H, I, G, F.
