Какие алгоритмы обхода деревьев существуют

Что проверяют

Знаете ли вы четыре порядка обхода и понимаете ли, зачем нужен каждый.

Как отвечать

Обходы делятся на две группы.

В глубину, три варианта, различающиеся моментом обработки узла:

• прямой (корень, левое, правое): узел обрабатывается до потомков. Используется для копирования дерева и сериализации, потому что структура восстанавливается в том же порядке;
• симметричный (левое, корень, правое): для дерева поиска даёт отсортированную последовательность. Это его главное применение;
• обратный (левое, правое, корень): узел обрабатывается после потомков. Нужен там, где результат зависит от детей: вычисление высоты, размеров поддеревьев, освобождение памяти.

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

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

• обход в глубину рекурсией тратит O(h) на стек, где h это высота. Для сбалансированного дерева это логарифм, для вырожденного в список это n, и на глубоком дереве получается переполнение стека;
• обход в ширину тратит O(w), где w это максимальная ширина уровня. У полного дерева нижний уровень содержит около половины узлов, поэтому память сопоставима с n.

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

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

Как продвинутое дополнение можно упомянуть обход Морриса, который проходит дерево за постоянную дополнительную память, временно перевешивая ссылки.

Где спотыкаются

Помнят названия, но не могут сказать, какой порядок даёт отсортированный вывод.

Реализуют обход в ширину рекурсией.

Не учитывают риск переполнения стека на вырожденном дереве.

Считают, что обход в ширину всегда экономнее по памяти.