跳到主要内容

Hierarchies

import { hierarchy } from 'd3-hierarchy'

const root = hierarchy(data, (d) => d.children)

hierarchy(data, children)​

构造分层数据根节点，返回节点对象。data 为根节点，children 为子节点访问器函数。

interface Node {
  data: any
  depth: number
  height: number
  parent: Node | null // 根节点为 null
  children?: Node[] // 叶子节点为 undefined
  value?: number
}
  • data: 节点的数据
  • depth: 根节点为 0，每个后代加 1
  • height: 叶子节点为 0
  • parent: 父节点，根节点为 null
  • children: 子节点数组，叶子节点为 undefined
  • value: 节点的值

默认的 children 访问器函数：

function children(d) {
  return d.children
}

node.ancestors()​

node.ancestors(): Node[]

返回祖先节点数组，从此节点开始，然后是每个父节点，直到根节点。

node.descendants()​

node.descendants(): Node[]

返回后代节点数组，从此节点开始，然后是按拓扑顺序的每个子节点。

node.leaves()​

node.leaves(): Node[]

以遍历顺序返回叶节点数组。节点有子节点，则返回节点的叶子节点；节点无子节点，则返回包含节点本身的数组。

node.find(filter)​

node.find((node: Node) => boolean): Node | undefined

返回第一个匹配过滤器的后代节点，否则返回 undefined。

const found = root.find((node) => {
  return node.data.name === 'Awan'
})

node.path(target)​

返回从此 node 到指定 target 节点的层次结构的最短路径。返回一个节点数组。

返回节点下的链接数组。每个链接包含来源（父节点）和目标（子节点）。叶子节点为空数组。

interface Link {
  source: Node
  target: Node
}

树的遍历​

常见的树遍历方法有以下几种：

  • 深度优先遍历（Depth-First Traversals）：
    • 前序遍历（Pre-order Traversal）：先访问节点，然后再递归地访问左子树和右子树。对于所遍历的每个节点，其顺序为：<节点自身 → 左子节点 → 右子节点>。
    • 中序遍历（In-order Traversal）：先递归地访问左子树，然后访问节点，之后再递归地访问右子树。对二叉搜索树而言，中序遍历的结果是得到有序的升序序列，其顺序为：<左子节点 → 节点自身 → 右子节点>。
    • 后序遍历（Post-order Traversal）：先递归地访问左子树与右子树，最后访问节点。其顺序为：<左子节点 → 右子节点 → 节点自身>。

深度优先遍历可以使用递归来实现，也可以通过栈（Stack）来实现非递归版本。

  • 广度优先遍历（Breadth-First Traversal）：
    • 通常被称为层序遍历（Level-order Traversal）：逐层从上到下、从左至右访问每个节点。这个过程通常使用队列（Queue）来实现，每次队列出队一个节点时，将其子节点入队，保证每个节点都会按照层次的顺序被访问。

下面是一个二叉树的示例以及其前序、中序、后序和层序的遍历结果：

    1
   / \
  2   3
 /|   |\
4 5   6 7
  • 前序遍历结果：1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
  • 中序遍历结果：4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
  • 后序遍历结果：4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
  • 层序遍历结果：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

node.sum(value)​

危险

在调用分层布局方法之前必须调用 node.sum() 或者 node.count() 方法。

在后序遍历中对此 node 和每个后代的指定 value 函数求值，并返回此 node。每个节点的 node.value 属性设置为由指定函数返回的数值加上所有后代的组合值。该函数接收传入的节点数据，并且必须返回一个非负数。value accessor 用于对节点和每一个后代求值，包括内部节点；如果你只希望叶节点具有内部值，则对于有子节点的任何节点返回 0。

root.sum((d) => d.value || 0)

node.count()​

计算此 node 下叶节点的数量并将其分配给 node.value。叶子节点算 1，其余的算 0。

node.sort(compare)​

在前序遍历中使用指定的 compare 函数对此 node 的子节点（如果有）以及此节点的每个子节点的子节点进行排序，并返回此 node。指定的函数将传入两个节点 a 和 b 进行比较。如果 a 应该在 b 之前，该函数必须返回一个小于 0 的值；如果 b 应该在 a 之前，则该函数必须返回大于 0 的值；否则，不指定 a 和 b 的相对顺序。有关更多信息，另请参阅 array.sort。

与 node.sum 不同，向 compare 函数传入的是两个节点而不是两个节点的数据。例如，如果数据具有值属性，则通过递减节点及其所有子节点的降序聚合值对节点进行排序，这也是 circle-packing 的推荐方法。

警告

如果需要按照指定顺序进行分层排序，那么在调用分层布局方法之前必须调用 node.sort() 方法。

node[Symbol.iterator]()​

层序遍历节点树。

for (const descendant of node) {
  // descendant 类型为 Node
  console.log(descendant)
}

node.each(function, that)​

在广度优先中为 node 及其每个后代调用指定的 function，以便只有在深度较小的所有节点都已访问的情况下才会访问给定 node，以及具有相同深度的所有先前节点。向指定的函数传入当前 node。

node.eachAfter(function, that)​

在后序遍历中为 node 及其每个后代调用的指定 function，以便只有在其所有后代已被访问后才访问给定 node。向指定的函数传入当前 node。

node.eachBefore(function, that)​

在前序遍历中为 node 及其每个后代调用指定的 function，以便只有在访问完所有祖先节点之后才访问给定 node。向指定的函数传入当前 node。

node.copy()​

返回节点子树的深拷贝。node 是返回树的根节点，node 的父节点永远是 null，深度永远为 0。