Как реализовать дерево в JavaScript и обойти его через DFS и BFS

Дерево в JavaScript хранит данные с вложенными связями: меню, категории, комментарии, DOM и AST. Чтобы реализовать такую структуру, достаточно связать узел с родителем и массивом детей. В статье вы создадите классы Node и Tree, добавите обходы DFS и BFS, поиск, вставку, удаление и сборку дерева из плоского массива.

Как устроено дерево в JavaScript

Дерево состоит из узлов, соединенных отношениями «родитель – ребенок». Один узел считают корнем, а узлы без детей называют листьями.

Узел Node и дерево Tree

Узел хранит значение, ссылку на родителя и массив дочерних узлов. Ссылка на родителя помогает подняться вверх, а массив children – пройти вниз.

class Node {
  constructor(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
  }
}

class Tree {
  constructor(data) {
    this._root = new Node(data);
  }
}

Корень дерева хранится в свойстве _root. У корневого узла parent равен null, у остальных узлов он ссылается на объект Node.

Пример структуры

Добавьте детей вручную, чтобы увидеть связи между объектами. Родителем каждого нового узла становится tree._root.

const tree = new Tree('one');
const two = new Node('two');
const three = new Node('three');

tree._root.children.push(two, three);
two.parent = tree._root;
three.parent = tree._root;

Такая структура содержит корень one и двух его детей: two и three.

В практическом коде узлы удобнее добавлять методом add.

Обход дерева: DFS и BFS

Обход посещает каждый узел и передает его в callback. DFS идет по ветке вглубь, а BFS обрабатывает узлы уровнями слева направо.

Фрагменты методов помещайте внутрь класса Tree, после конструктора. Отдельно такие объявления не запускаются; итоговый класс содержит все методы вместе.

DFS: поиск в глубину

Рекурсивный DFS сначала выбирает порядок вызова callback. В режиме pre-order callback получает узел до его детей. В режиме post-order callback срабатывает после всех дочерних узлов.

traverseDF(callback, order = 'pre-order') {
  const visit = (node) => {
    if (order === 'pre-order' && callback(node) === true) {
      return true;
    }

    for (const child of node.children) {
      if (visit(child)) {
        return true;
      }
    }

    return order === 'post-order' && callback(node) === true;
  };

  visit(this._root);
}

Рекурсия вызывает ту же функцию для каждого ребенка. Ветка заканчивается, когда текущий узел больше не содержит детей.

Глубокое дерево может превысить глубину стека вызовов, поэтому для неизвестной глубины выбирайте итеративный вариант.

Итеративный DFS на стеке

Явный стек хранит узлы, которые еще предстоит посетить. Метод подходит для pre-order и не зависит от глубины стека вызовов JavaScript.

traverseDFIterative(callback) {
  const stack = [this._root];

  while (stack.length > 0) {
    const node = stack.pop();

    if (callback(node) === true) {
      return;
    }

    for (let i = node.children.length - 1; i >= 0; i -= 1) {
      stack.push(node.children[i]);
    }
  }
}

Дети добавляются в обратном порядке, поэтому стек посещает их слева направо. Если callback вернет true, обход остановится сразу.

BFS: поиск в ширину

BFS использует очередь из массива и индекса head. Индекс движется вперед, поэтому извлечение узла не требует shift().

traverseBF(callback) {
  const queue = [this._root];
  let head = 0;

  while (head < queue.length) {
    const currentNode = queue[head];
    head += 1;

    if (callback(currentNode) === true) {
      return;
    }

    for (const child of currentNode.children) {
      queue.push(child);
    }
  }
}

Сначала callback получает корень, затем всех его детей и после этого узлы следующего уровня. Такой порядок удобен для поиска ближайшего подходящего узла и вывода меню по уровням.

DFS и BFS: когда что выбирать

Все три реализации посещают каждый доступный узел за O(n). Выбирайте способ по порядку обработки и доступной памяти.

Здесь n – количество узлов, h – глубина дерева. Если корень содержит n − 1 ребенка, итеративный DFS сразу положит их в стек.

Поэтому память итеративного DFS нельзя оценивать только через глубину. BFS с очередью, которая освобождает обработанные элементы, требует O(w), где w – максимальное число узлов на одном уровне.

Поиск узла по значению

Метод contains принимает значение и функцию обхода. Он возвращает первый найденный узел или null, а после совпадения прекращает обход.

Добавьте метод внутрь класса Tree. При отсутствии значения метод вернет null, поэтому результат можно безопасно проверить перед обращением к его свойствам.

contains(data, traversal = this.traverseBF) {
  let found = null;

  traversal.call(this, (node) => {
    if (node.data === data) {
      found = node;
      return true;
    }

    return false;
  });

  return found;
}

Функция передается в выбранный обход через traversal.call(this, callback). Для BFS первым вернется ближайший по глубине узел.

При одинаковых значениях метод выбирает первое совпадение в порядке выбранного обхода.

const node = tree.contains('three', tree.traverseBF);
console.log(node ? node.data : 'Не найдено');

Добавление и удаление узлов

Методы меняют две стороны связи: массив детей родителя и свойство parent нового или удаленного узла. Оба метода используют ранний выход поиска, поэтому при дубликатах работают с первым совпадением.

Поместите объявления add и remove внутрь класса Tree.

Метод add(data, parentData, traversal)

Метод создает узел, ищет родителя по значению и добавляет ребенка в его массив children. Если родитель отсутствует, метод выбрасывает ошибку.

add(data, parentData, traversal = this.traverseBF) {
  const parent = this.contains(parentData, traversal);

  if (!parent) {
    throw new Error('Cannot add node to a non-existent parent.');
  }

  const child = new Node(data);
  child.parent = parent;
  parent.children.push(child);

  return child;
}

Три вызова add создают 3 уровня подчиненности ниже CEO. В третьем вызове родителем становится Director of Puppies.

Узел Manager of Puppies находится непосредственно под ним.

const tree = new Tree('CEO');

tree.add('VP of Finance', 'CEO');
tree.add('Director of Puppies', 'VP of Finance');
tree.add('Manager of Puppies', 'Director of Puppies');

Метод remove(data, parentData, traversal)

Метод находит родителя, берет первый дочерний узел с нужным значением и удаляет его через splice. Вместе с узлом от дерева отделяется все его поддерево.

remove(data, parentData, traversal = this.traverseBF) {
  const parent = this.contains(parentData, traversal);

  if (!parent) {
    throw new Error('Parent does not exist.');
  }

  const index = parent.children.findIndex((child) => child.data === data);

  if (index === -1) {
    throw new Error('Node to remove does not exist.');
  }

  const removedNode = parent.children[index];
  parent.children.splice(index, 1);
  removedNode.parent = null;

  return removedNode;
}

Метод возвращает удаленный объект Node. Его свойство parent получает значение null, а связи с детьми сохраняются.

Сам splice возвращает массив удаленных элементов, который здесь не используется. Поиск, add и remove занимают O(n) в худшем случае.

Добавление в конец children через push занимает амортизированное O(1) после поиска родителя. Удаление через splice может сдвинуть оставшихся детей и требует O(k), где k – число детей родителя.

Как собрать дерево из плоского массива с parentId

API часто возвращает список категорий или комментариев с полями id и parentId. Сначала создайте узел для каждой записи, затем свяжите его с родителем через Map. Два прохода дают сложность O(n) при обычной оценке операций Map за O(1).

Функция рассчитана на записи, которые уже описывают корректное дерево:

• Каждая запись содержит уникальный id.
• Ровно 1 запись содержит parentId: null и задает корень.
• У остальных записей parentId указывает на существующий id.
• Связи не содержат циклов, включая ссылку записи на себя.
• Цепочка родителей каждой записи заканчивается в единственном корне.

Функция проверяет наличие корня, лишние корни и отсутствующих родителей. Повторяющиеся id, циклы и отдельные компоненты она не выявляет.

Используйте ее для входных данных, которые удовлетворяют всем перечисленным условиям.

function treeFromFlat(records) {
  const nodes = new Map();
  let root = null;

  for (const record of records) {
    nodes.set(record.id, new Node(record));
  }

  for (const record of records) {
    const node = nodes.get(record.id);

    if (record.parentId === null) {
      if (root) {
        throw new Error('Tree must have one root.');
      }

      root = node;
      continue;
    }

    const parent = nodes.get(record.parentId);

    if (!parent) {
      throw new Error('Parent record does not exist.');
    }

    node.parent = parent;
    parent.children.push(node);
  }

  if (!root) {
    throw new Error('Root record does not exist.');
  }

  return root;
}

Функция возвращает корневой Node. Поле data сохраняет всю исходную запись, поэтому рендер меню сможет взять из нее название, ссылку и другие поля.

const records = [
  { id: 1, parentId: null, title: 'Каталог' },
  { id: 2, parentId: 1, title: 'Книги' },
  { id: 3, parentId: 1, title: 'Курсы' },
  { id: 4, parentId: 2, title: 'JavaScript' }
];

const root = treeFromFlat(records);
console.log(root.children[0].children[0].data.title); // JavaScript

Полная реализация дерева

В итоговом классе собраны узел, корневое значение, обходы, поиск, добавление и удаление. Код использует class, const и let, а поиск останавливается после первого совпадения.

Для запуска скопируйте итоговые классы и пример использования в один JavaScript-файл. Промежуточные объявления классов и переменных повторно добавлять не нужно.

class Node {
  constructor(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
  }
}

class Tree {
  constructor(data) {
    this._root = new Node(data);
  }

  traverseDF(callback, order = 'pre-order') {
    const visit = (node) => {
      if (order === 'pre-order' && callback(node) === true) {
        return true;
      }

      for (const child of node.children) {
        if (visit(child)) {
          return true;
        }
      }

      return order === 'post-order' && callback(node) === true;
    };

    visit(this._root);
  }

  traverseDFIterative(callback) {
    const stack = [this._root];

    while (stack.length > 0) {
      const node = stack.pop();

      if (callback(node) === true) {
        return;
      }

      for (let i = node.children.length - 1; i >= 0; i -= 1) {
        stack.push(node.children[i]);
      }
    }
  }

  traverseBF(callback) {
    const queue = [this._root];
    let head = 0;

    while (head < queue.length) {
      const currentNode = queue[head];
      head += 1;

      if (callback(currentNode) === true) {
        return;
      }

      for (const child of currentNode.children) {
        queue.push(child);
      }
    }
  }

  contains(data, traversal = this.traverseBF) {
    let found = null;

    traversal.call(this, (node) => {
      if (node.data === data) {
        found = node;
        return true;
      }

      return false;
    });

    return found;
  }

  add(data, parentData, traversal = this.traverseBF) {
    const parent = this.contains(parentData, traversal);

    if (!parent) {
      throw new Error('Cannot add node to a non-existent parent.');
    }

    const child = new Node(data);
    child.parent = parent;
    parent.children.push(child);
    return child;
  }

  remove(data, parentData, traversal = this.traverseBF) {
    const parent = this.contains(parentData, traversal);

    if (!parent) {
      throw new Error('Parent does not exist.');
    }

    const index = parent.children.findIndex((child) => child.data === data);

    if (index === -1) {
      throw new Error('Node to remove does not exist.');
    }

    const removedNode = parent.children[index];
    parent.children.splice(index, 1);
    removedNode.parent = null;
    return removedNode;
  }
}

Для pre-order вызовите tree.traverseDF(callback). Для post-order передайте второй аргумент 'post-order'. Если нужен ближайший по глубине подходящий узел, используйте BFS.

Пример обходов, поиска и удаления поддерева

Пример создает 5 узлов и собирает результаты обходов в строки. Запустите его после итоговых классов; комментарии показывают ожидаемый вывод консоли.

(() => {
  const tree = new Tree('one');
  tree.add('two', 'one');
  tree.add('three', 'one');
  tree.add('four', 'two');
  tree.add('five', 'two');

  const preOrder = [];
  tree.traverseDF((node) => {
    preOrder.push(node.data);
  });
  console.log(preOrder.join(', ')); // one, two, four, five, three

  const postOrder = [];
  tree.traverseDF((node) => {
    postOrder.push(node.data);
  }, 'post-order');
  console.log(postOrder.join(', ')); // four, five, two, three, one

  const iterative = [];
  tree.traverseDFIterative((node) => {
    iterative.push(node.data);
  });
  console.log(iterative.join(', ')); // one, two, four, five, three

  const breadthFirst = [];
  tree.traverseBF((node) => {
    breadthFirst.push(node.data);
  });
  console.log(breadthFirst.join(', ')); // one, two, three, four, five

  const found = tree.contains('four');
  console.log(found.data, found.parent.data); // four two
  console.log(tree.contains('missing')); // null

  const removed = tree.remove('two', 'one');
  console.log(removed.data, removed.parent); // two null
  console.log(removed.children.map((node) => node.data).join(', '));
  // four, five
  console.log(tree.contains('four')); // null

  const remaining = [];
  tree.traverseBF((node) => {
    remaining.push(node.data);
  });
  console.log(remaining.join(', ')); // one, three
})();

После удаления узла two дерево содержит только one и three. Переменная removed сохраняет отделенное поддерево вместе с его детьми.

Где применяют деревья в JavaScript

DOM браузера хранит элементы как иерархию, JSON часто содержит вложенные объекты, а компиляторы строят AST из исходного кода. Такой же подход подходит для меню сайта, каталогов, файловых систем и комментариев с ответами.

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

При выводе вложенного меню выбирайте pre-order DFS: родитель обрабатывается перед детьми. Если нужны ближайшие по глубине совпадения, выбирайте BFS.

При поиске одного результата возвращайте true из callback сразу после совпадения. Полный обход для вывода всех узлов останавливать не нужно.