Как работает рекурсивный обход дерева?

Основная идея рекурсивного обхода дерева

Рекурсивный обход дерева — это способ последовательного посещения всех узлов дерева, при котором функция вызывает саму себя для обработки поддеревьев. Дерево состоит из корневого узла и поддеревьев, каждое из которых само является деревом. Именно эта самоподобная структура делает рекурсию идеальным инструментом для обхода.

Типы обходов

Существует несколько вариантов рекурсивного обхода в зависимости от порядка обработки узлов:

• Прямой (pre-order): сначала обрабатывается текущий узел, затем рекурсивно обходятся дочерние узлы.
• Симметричный (in-order): сначала обходится левое поддерево, затем текущий узел, затем правое поддерево (актуально для бинарных деревьев).
• Обратный (post-order): сначала рекурсивно обходятся дочерние узлы, затем обрабатывается текущий узел.

Пример на JavaScript

Рассмотрим обход бинарного дерева поиска с выводом значений в порядке возрастания (симметричный обход):

function inOrderTraversal(node) {
  if (node === null) return;
  inOrderTraversal(node.left);   // обход левого поддерева
  console.log(node.value);       // обработка текущего узла
  inOrderTraversal(node.right);  // обход правого поддерева
}

Для дерева с корнем 10, левым потомком 5 и правым 15, вызов inOrderTraversal(root) выведет: 5, 10, 15.

Где применяется

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

• Работе с DOM-деревом (например, поиск элементов по классу).
• Файловых системах (рекурсивное копирование или удаление папок).
• Алгоритмах на графах (поиск в глубину).
• Компиляторах (обход абстрактного синтаксического дерева).

Вывод

Рекурсивный обход дерева — это простой и выразительный способ обработки иерархических данных. Его стоит применять, когда структура данных естественно рекурсивна, а глубина дерева не превышает допустимый размер стека вызовов (обычно до нескольких тысяч уровней).