Обход дерева: .each(), .eachBefore(), .eachAfter(), .descendants(), .links()

Иерархические структуры в d3-hierarchy представлены в виде узлов, где каждый элемент дерева содержит ссылки на родителя и потомков, а также набор методов для обхода и трансформации структуры. Внутреннее представление строится на объектах HierarchyNode, которые обеспечивают единый интерфейс навигации по дереву независимо от источника данных.

Обход иерархии в D3 основан на двух классических стратегиях: pre-order (прямой обход) и post-order (обратный обход). Эти стратегии определяют порядок, в котором узлы посещаются при рекурсивном проходе по дереву.

  • Pre-order: сначала посещается текущий узел, затем его потомки
  • Post-order: сначала обрабатываются потомки, затем родительский узел

Эти принципы лежат в основе методов each, eachBefore и eachAfter.

.each()

Метод each выполняет обход дерева в прямом порядке (pre-order), начиная с текущего узла и рекурсивно переходя к потомкам слева направо.

Сигнатура:

node.each(function(d) {
  // d — текущий узел
});

Особенности поведения:

  • сначала обрабатывается корневой узел
  • затем рекурсивно обходятся дети
  • порядок обхода фиксирован и детерминирован
  • функция вызывается для каждого узла ровно один раз

Пример применения:

root.each(function(d) {
  d.depth = d.depth || 0;
});

Внутренне each эквивалентен eachBefore, но исторически используется как более короткая форма для pre-order обхода.

.eachBefore()

Метод eachBefore реализует явный pre-order обход, полностью эквивалентный логике “сначала родитель, затем дети”, но с более строгой семантикой и предсказуемостью реализации.

Сигнатура:

node.eachBefore(function(d) {
  // обработка узла
});

Ключевые характеристики:

  • гарантированный top-down обход
  • родитель всегда обрабатывается раньше потомков
  • удобен для вычислений, зависящих от предков
  • часто используется для расчёта накопительных значений

Пример вычисления суммы значений в поддереве:

root.eachBefore(function(d) {
  if (d.children) {
    d.value = d.children.reduce((sum, c) => sum + c.value, 0);
  }
});

Типичный сценарий использования eachBefore — агрегация данных, где результат родителя зависит от уже обработанных потомков.

.eachAfter()

Метод eachAfter реализует post-order обход, при котором сначала обрабатываются все потомки, и только затем текущий узел.

Сигнатура:

node.eachAfter(function(d) {
  // обработка узла после детей
});

Характерные свойства:

  • обход снизу вверх
  • дети гарантированно обработаны до родителя
  • удобен для свёртки данных и вычислений агрегаций
  • часто используется в алгоритмах динамического программирования на деревьях

Пример вычисления глубины поддерева:

root.eachAfter(function(d) {
  d.height = d.children
    ? 1 + Math.max(...d.children.map(c => c.height))
    : 0;
});

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

.descendants()

Метод descendants возвращает плоский массив всех узлов дерева, включая сам корневой узел, в порядке pre-order обхода.

Сигнатура:

const nodes = root.descendants();

Особенности:

  • не модифицирует исходную структуру
  • возвращает новый массив
  • порядок соответствует eachBefore
  • удобно для линейной обработки дерева

Пример:

const allNodes = root.descendants();

allNodes.forEach(d => {
  console.log(d.data.name);
});

Практическое значение метода заключается в преобразовании иерархии в линейную структуру, пригодную для фильтрации, сортировки или визуализации без вложенности.

Часто используется в сочетании с масштабированием или вычислением координат:

const nodes = root.descendants();

nodes.forEach((d, i) => {
  d.index = i;
});

Метод links преобразует дерево в список связей между узлами, возвращая массив объектов вида:

{
  source: parentNode,
  target: childNode
}

Сигнатура:

const links = root.links();

Структурные особенности:

  • каждая связь соответствует ребру дерева
  • корневой узел не имеет входящих связей
  • результат используется для построения графов
  • порядок соответствует обходу дерева

Пример результата:

[
  { source: root, target: child1 },
  { source: root, target: child2 },
  { source: child1, target: grandchild }
]

Типичные сценарии применения:

  • построение диаграмм связей (tree layout, cluster layout)
  • визуализация в виде графа с линиями
  • передача данных в d3.linkHorizontal или d3.linkVertical

Пример использования в визуализации:

svg.selectAll("path")
  .data(root.links())
  .enter()
  .append("path")
  .attr("d", d3.linkHorizontal()
    .x(d => d.x)
    .y(d => d.y)
  );

Метод links фактически переводит древовидную структуру в формат графа, сохраняя при этом иерархическую семантику через направление source → target.

Сравнение стратегий обхода

Различия между методами проявляются в порядке обхода и назначении:

  • each / eachBefore — сверху вниз, родитель до потомков
  • eachAfter — снизу вверх, потомки до родителя
  • descendants — линейное представление узлов
  • links — преобразование дерева в список рёбер

Эти методы формируют основу для любых алгоритмов работы с иерархиями в d3-hierarchy, от вычислений агрегированных значений до подготовки данных для визуализации графов и деревьев.

Оглавление