Обход дерева в глубину и ширину

Что такое обход дерева

Дерево — это иерархическая структура данных, состоящая из узлов, соединённых рёбрами без циклов. У дерева есть корень, а у каждого узла — потомки. Обход дерева — это посещение всех его узлов по определённому правилу ровно один раз.

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

Обходы в глубину

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

• Прямой (корень → левое → правое);
• Симметричный (левое → корень → правое);
• Обратный (левое → правое → корень).

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

обход(узел): если узел пуст: выход напечатать(узел.значение) обход(узел.левый) обход(узел.правый)

Обход в ширину

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

Обход	Структура	Порядок
В глубину	стек / рекурсия	по ветвям
В ширину	очередь	по уровням

Разбор примера

Пусть дерево: корень 5, его дети 3 и 8, у узла 3 дети 1 и 4. Тогда обходы дадут:

Прямой: 5 3 1 4 8 Симметричный: 1 3 4 5 8 Обратный: 1 4 3 8 5 В ширину: 5 3 8 1 4

Симметричный обход двоичного дерева поиска выводит значения в порядке возрастания — это его важное практическое свойство.

Где применяют обходы

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

Глубина рекурсии

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

Частые ошибки. Путают порядок при симметричном и обратном обходах. Забывают условие выхода из рекурсии для пустого узла — это приводит к бесконечному спуску. Используют стек вместо очереди для обхода в ширину и получают обход в глубину.

Кратко о главном

• Обход дерева — посещение всех узлов ровно один раз по правилу.
• Обходы в глубину: прямой, симметричный и обратный.
• Обход в ширину идёт по уровням и использует очередь.
• Симметричный обход дерева поиска даёт значения по возрастанию.
• Обходы в глубину удобно записывать рекурсивно.