Как реализовать обход дерева через рекурсию?

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

Рекурсивный обход дерева — это способ последовательного посещения всех узлов дерева, при котором функция вызывает саму себя для обработки каждого дочернего узла. Это естественный способ работы с иерархическими структурами, такими как файловая система, DOM-дерево или JSON-объекты.

Как это работает?

Основная идея заключается в том, что для каждого узла мы сначала выполняем некоторое действие (например, выводим значение), а затем рекурсивно вызываем ту же функцию для каждого его потомка. Базовый случай — когда у узла нет детей (лист), тогда рекурсия прекращается.

Пример кода на JavaScript

const tree = {
  value: 1,
  children: [
    { value: 2, children: [] },
    {
      value: 3,
      children: [
        { value: 4, children: [] },
        { value: 5, children: [] }
      ]
    }
  ]
};

function traverse(node) {
  console.log(node.value); // Обработка узла
  for (let child of node.children) {
    traverse(child); // Рекурсивный вызов
  }
}

traverse(tree);
// Вывод: 1, 2, 3, 4, 5

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

• Обход DOM-дерева для поиска элементов
• Сериализация и десериализация JSON
• Алгоритмы на графах (DFS)
• Парсинг выражений (AST)

Вывод

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