Как реализовать поиск по дереву данных?

Основные подходы к поиску по дереву

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

Пример реализации на JavaScript

// Дерево: { value: 1, children: [ { value: 2, children: [] }, { value: 3, children: [ { value: 4, children: [] } ] } ] }

// DFS (рекурсивно)
function dfs(node, target) {
  if (node.value === target) return node;
  for (let child of node.children) {
    const result = dfs(child, target);
    if (result) return result;
  }
  return null;
}

// BFS (итеративно с очередью)
function bfs(root, target) {
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    if (node.value === target) return node;
    queue.push(...node.children);
  }
  return null;
}

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

• Поиск элементов в DOM-дереве (например, querySelector использует DFS).
• Навигация по файловой системе.
• Алгоритмы на графах (социальные сети, маршрутизация).

Вывод: DFS эффективен для глубоких деревьев с ограниченной памятью, BFS — для поиска ближайшего узла или при равномерной структуре. Выбор алгоритма зависит от формы дерева и цели поиска.