Обход дерева в глубину (DFS)

1. Обход в глубину (DFS) можно реализовать двумя основными способами: рекурсивно или итеративно с использованием стека.
2. Рекурсивный подход:
   • Создайте массив для хранения результатов.
   • Напишите вспомогательную рекурсивную функцию, которая принимает узел (объект).
   • В этой функции сначала добавьте свойство value текущего узла в массив результатов.
   • Затем для каждого дочернего узла из массива children рекурсивно вызовите эту же функцию.
   • Начальный вызов будет с корневым объектом дерева.
3. Итеративный подход (со стеком):
   • Создайте массив для результатов и стек для узлов (объектов), которые нужно посетить.
   • Поместите корневой узел в стек.
   • Пока стек не пуст:
     • Извлеките узел из стека.
     • Добавьте его свойство value в массив результатов.
     • Поместите всех его дочерних узлов (из массива children) в стек. Важно: чтобы сохранить правильный порядок обхода (слева направо), дочерние узлы нужно добавлять в стек в обратном порядке (справа налево).
4. Не забудьте обработать случай, когда на вход подается null (пустое дерево).

Решение 1: Рекурсивный подход

Этот подход является наиболее интуитивным для древовидных структур, поскольку сама структура дерева рекурсивна.

Код с комментариями:

const depthFirstSearch = (tree) => {
  // 1. Обрабатываем крайний случай: если дерево пустое (null), возвращаем пустой массив.
  if (!tree) {
    return [];
  }
 
  // 2. Создаем массив для хранения результата обхода.
  const result = [];
 
  // 3. Определяем вложенную рекурсивную функцию `traverse` (обход).
  //    Она будет вызываться для каждого узла (объекта) в дереве.
  function traverse(node) {
    // 4. Добавляем значение текущего узла в массив результатов.
    //    Это "посещение" узла.
    result.push(node.value);
 
    // 5. Перебираем всех дочерних элементов текущего узла.
    //    Убеждаемся, что у узла есть дочерние элементы, прежде чем их перебирать.
    if (node.children) {
      for (const child of node.children) {
        // 6. Для каждого дочернего узла рекурсивно вызываем ту же функцию `traverse`.
        //    Это погружение "вглубь" дерева.
        traverse(child);
      }
    }
  }
 
  // 7. Начинаем обход, вызывая `traverse` для корневого узла дерева.
  traverse(tree);
 
  // 8. Возвращаем массив с результатами обхода.
  return result;
};

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

1. Базовый случай: Функция сначала проверяет, не является ли дерево null. Если да, то обход невозможен, и она возвращает пустой массив.
2. Инициализация: Создается пустой массив result, в который будут собираться значения узлов.
3. Рекурсивная функция traverse:
   • При вызове для какого-либо узла node, она немедленно добавляет значение этого узла (node.value) в массив result.
   • Затем она последовательно перебирает всех детей из массива children этого узла.
   • Для каждого дочернего узла она вызывает саму себя (traverse(child)). Этот шаг является ключевым в рекурсии.
4. Начало обхода: Первоначальный вызов traverse(tree) запускает рекурсивный процесс с корневого узла.
5. Завершение: Когда самый первый вызов traverse(tree) завершит свою работу, массив result будет содержать все значения узлов в правильном порядке.

Решение 2: Итеративный подход (со стеком)

Этот подход использует структуру данных “стек” (Stack) для отслеживания узлов, которые нужно посетить. Он позволяет избежать глубокой рекурсии, которая может привести к переполнению стека вызовов.

Код с комментариями:

const depthFirstSearch = (tree) => {
  // 1. Обрабатываем крайний случай: если дерево пустое, возвращаем пустой массив.
  if (!tree) {
    return [];
  }
 
  // 2. Создаем массив для хранения результата.
  const result = [];
  // 3. Создаем стек и сразу помещаем в него корневой узел (объект).
  const stack = [tree];
 
  // 4. Запускаем цикл, который продолжается, пока в стеке есть узлы.
  while (stack.length > 0) {
    // 5. Извлекаем последний узел из стека (принцип LIFO — Last-In, First-Out).
    const node = stack.pop();
 
    // 6. "Посещаем" узел: добавляем его значение в массив результатов.
    result.push(node.value);
 
    // 7. Перебираем дочерние узлы текущего узла В ОБРАТНОМ ПОРЯДКЕ.
    //    Это ключевой момент для правильного порядка обхода.
    if (node.children) {
      for (let i = node.children.length - 1; i >= 0; i--) {
        // 8. Помещаем каждого дочернего узла в стек.
        stack.push(node.children[i]);
      }
    }
  }
 
  // 9. Возвращаем массив с результатами.
  return result;
};

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

1. Инициализация: Проверяется null и создается массив result. Также создается stack и в него сразу помещается корневой объект tree.
2. Цикл while: Цикл продолжается, пока стек не опустеет.
3. Извлечение узла: На каждой итерации из стека извлекается верхний элемент с помощью stack.pop().
4. Посещение узла: Значение текущего узла (node.value) добавляется в result.
5. Добавление детей в стек: Мы перебираем дочерние узлы справа налево и добавляем их в стек. Это гарантирует, что левые дочерние узлы будут обработаны раньше правых, что соответствует классическому порядку DFS.
6. Завершение: Когда цикл while заканчивается, все узлы были обработаны, и функция возвращает result.