树的可视化

如何「画」一棵树？作为不可或缺的一种数据结构，树的重要性不言而喻。而当我们想向别人展示某种算法流程，或者自己在写程序调试的过程中，可视化又是重要的数据结构展示手段。将两者叠加在一起，「如何可视化一棵树」这个问题就摆在了我们眼前。

你之前一定见过各种树的可视化，样式可能五花八门，而现如今也有大量的针对各种特殊树结构设计的可视化算法。本文中介绍的是其中最为通用的算法 —— Reingold-Tilford 算法，它不局限于某一种二叉树或 N 叉树，只要是符合树基础定义的结构都能被它画出来。它画出的树紧凑、对称又美观，经常被排版进各种文章中。紧凑、对称倒还好说，「美观」这样一个相当主观的概念是如何量化到算法中的呢？我们先从它的绘制目标说起。

首先，作为一棵树，起码需要在可视化的过程中反应它的层次结构。因此：

1. 结点的所有孩子都相邻地处在下方的同一高度上

注意这里的「相邻」，这就避免了结点间的交叉：

同属于 B 子树的 C 和 D 必须要相邻，否则就不合法。

光避免交叉还不够，我们不应该让结点重叠：

2. 同一高度的相邻结点间应该存在一定的最小间距

除以上两点之外，我们还想让整棵树看上去美观。对称的结构往往比较美观，然而这是由树的结点结构决定的，并不是我们说了算。不过退一步来讲，我们可以让它满足：

3. 结点应该相对所有子结点居中（如果有的话）

「居中」的意思是结点的横坐标应该等于最左侧的孩子和最右侧的孩子横坐标的平均值。如果只有一个子结点，那它应该位于孩子的正上方：

在二叉树中，因为需要区分左孩子和右孩子，所以当某个结点只有一个孩子时往往不应该绘制在正中间，而应该偏移一定的距离来表示孩子的相对位置。如果有上述需求，可以在实际渲染绘制一个「空结点」作为占位符，即在二叉树向一般树转化的过程中添加一个特殊的空结点标记：

4. 如果同一子树两结点间必须要留出一定空隙，则应该平均分配给它们中间的所有结点

比如这里，因为结点 B 和 G 的子树有一定体积，所以它们彼此之间需要间隔一段距离，而这段距离需要平均分配到 BF 和 FG 之间。这也算是对称性的一种体现。

如果只有上述四条规则，我们完全可以让每个结点之间都分得很开，留出足够的距离以防子树之间位置冲突，但这样显然不切实际。因此：

5. 在满足上述所有条件的基础上，每棵子树的宽度都应该尽可能小（画面应该尽量紧凑）

在许多其它的绘制算法中，即使一个结点没有孩子，也需要保留与其它兄弟结点同样的体积（像右侧图中一样），而这会在画面上留下大片空白，占用很大一部分面积，不利于其它内容的排版。有些人可能会觉得像右面那样画面看上去比较美观，但 Reingold-Tilford 算法坚持以实用性为主，因此抛弃了右面的画法。

在以上五条限制下，整棵树的形状已经大致确定。如果让你手画一棵满足这些条件的树，你准备从哪落笔？单单几个结点可能还比较简单，但当树的结构复杂起来，你可能就需要画画擦擦频繁调整结点的位置了。算法是追求时间效率的，它可不能像你那样调整来调整去。我们来看 Reingold-Tilford 算法是如何解决这个问题的。

在正式开始绘制之前，让我们先完成一些准备工作。因为是一个展示项目，所以这里就用 Typescript 来写，绘制好的树结构可以直接用 canvas 显示在前端界面上。

Typescript 首先要先准备好一些类型声明：

type Node = {
  id: string | number;
  children: Node[];
};

一个结点由 ID 和孩子结点列表构成：这里的 ID 其实并不是最后绘制在节点上的文字，只是代表结点的唯一标识（做动画可能会用到），而结点的内容（data）是可重复的，应该由别的字段来表示。不过在绘制过程中 ID 和 data 其实都用不到，我们只关心结点的层次结构（也就是这里的 children 列表），同时为了方便起见就直接用 ID 标识结点内容了。

这只是结点最基本的属性，在实际算法流程中属性应该有所扩展，比如绘制算法会输出带有位置属性的结点。要想表示带有位置属性结点的类型，我们不能简单地用 Node & {x: number, y: number} 来表示，因为这样结点的孩子们仍然是 Node 类型而非像它自身一样的 Node & {x: number, y: number} ，因此访问 node.children.x 会被 Typescript 拦下。要解决这个问题，我们可以这样写：

type NodeWithProperties<T> = Omit<Node, "children"> &
  T & {
    children: NodeWithProperties<T>[];
  };

这相当于修改了原本 children 的类型值，改为了与自身相同的带有附加属性的新类型。我们也可以用类似的方法获取某一结点的属性类型：

type PropertiesOf<T extends Node> = Omit<T, "children">;

const getProperties = <T extends Node>(node: T): PropertiesOf<T> => {
  const { ["children"]: _, ...properties } = node;
  return properties;
};

所谓「绘制」并不是「渲染」，我们只是给所有结点添加一个位置属性，包含有它所在的 X 和 Y 坐标，方便后面的渲染流程将这个点印在 canvas 上。这个过程并不会添加任何结点样式、间距之类的信息，只以 1 作为单位长度，后续渲染过程中再对这些位置坐标进行变换即可。这个过程可以叫做「绘制草图（drafting）」。

在绘制之初，我们应该先将所有结点的位置属性初始化，给它们分配默认的起始坐标：

type Position = {
  x: number;
  y: number;
};

type DeltaPosition = Position & {
  delta: number;
};

const initialize = (node: Node): NodeWithProperties<DeltaPosition> => ({
  ...getProperties(node),
  x: 0,
  y: 0,
  delta: 0,
  children: node.children.map(initialize),
});

这里的 delta 属性我们后面会用到，在后文中会详细介绍。

Y 坐标的计算过程非常简单，根据上面的绘制规则 1，它就等于结点的深度（即所处的层数，到根节点的路径距离）。我们可以直接用一次遍历计算得到所有节点的 Y 坐标信息：

const assignY = (
  node: NodeWithProperties<Position>,
  depth: number = 0
): void => {
  node.y = depth;
  node.children.forEach((child) => assignY(child, depth + 1));
};

这里使用了一个小技巧，我们在外层调用时可以直接使用 assignY(root) ，而不需要提供任何的深度参数。

计算 X 坐标的过程比计算 Y 坐标复杂一些，但我们仍然可以使用类似的方法。假设我们仍像之前一样，在计算某个节点之前先确定好了它子树上的所有节点的 X 坐标，那么我们在访问到它的时候，只需要把它的几棵内部已经排好位置的子树安排到互相之间不重叠的位置上就可以了。如下图，对于 A 来说，它的子树 B、E、H 已经在之前的递归中计算好了内部的位置排布，只需要让它们互相之间错开就可以了。

于是我们的任务就分解成了对于同一层的子树的安排。因为一颗子树的内部是已经排好位置的，我们不希望再对子树内部做相对位置的调整，而是应该整颗子树一起移动到我们想要的位置。

但是，如果我们每一次整体移动的时候都依次遍历子树上的所有节点，把它们的 X 坐标加上或减去某个值，那就太费时间了。如果你以前学过「线段树」之类的数据结构，你应该记得线段树有一种「lazy」标记，它代表它自身和它的子树上的每个结点都做了 lazy 这个操作。我们并不需要把这个操作真正应用到子节点上，只是什么时候真的需要用到子节点的值，再把 lazy 标记顺路下放就可以了。

在这里我们也可以借鉴这种思想：当某个结点和它的子树需要整体平移一段距离时，我们也可以给它一个标记——就叫「delta」。因为我们只需要做横向上的调整，所以 delta 可以只用一个数字储存横坐标的移动量。到最后全部调整完，我们再从头到尾通过一次遍历将所有的 delta 标记全部应用下去，就能得到最终的位置值了。

在不同的资料上，这个标记的名称也可能有所不同，有叫 mod（modify）的，有叫 tag 的，总之五花八门叫什么的都有。但无论叫什么，它们表示的都是相同的含义。

那对于两个相邻的孩子结点，它们之间应该相距多少才合适呢？通俗地说，这取决于它们的各自的子树有多「胖」。假如说它们两个都有非常臃肿的子树，它们之间就必须离得很远来防止子树挤在一起；而如果它们都孤零零的没有子树，那只需要让他们两个互相之间不撞上就可以了。

我们用一个新的量——子树的「轮廓」，来衡量一棵子树有多胖。轮廓并不是一个一维量，它记录了子树在每一层中最左侧和最右侧结点的 X 坐标值。

type Contour = {
  left: number;
  right: number;
};

type SubtreeContour = Contour[];

以上图为例，B 子树的轮廓为（这些都是 X 坐标值，单位为 1）：

[
    { left: 1, right: 1 },		// B - B
    { left: 0.5, right: 1.5 },	// C - F
    { left: 0, right: 1 },		// D - E
]

而 G 子树的轮廓则为：

[
    { left: 4, right: 4 },		// G - G
    { left: 3, right: 5 },		// H - M
    { left: 2, right: 5 },		// I - N
]

我们先不去管这个量应该如何计算得到，假设我们现在已经有了两棵子树的「轮廓」值，我们怎样利用轮廓计算它们之间最小间距呢？

这应该比较容易，我们可以一层一层来看，比较「左侧节点的右轮廓」和「右侧结点的左轮廓」的间隔，取其中那个最小值（这个值有可能是负数，代表它们已经重叠了），然后让右侧子树向右移开这么多距离保证它们之间每层都不重叠。

顺着这个思路，我们可以写出这部分的代码逻辑。代码中 childContour 指的是右边子树的轮廓，prevContour 是左边子树的轮廓。这本质上是用 reduce 函数计算最大值的过程，得到的 conflict 为两棵子树重叠的距离。若为负值则表示两棵子树分开过大，需要紧凑一下。需要注意的是这里的负值确实可能出现，所以 return 语句中做的初值判断不能省略。

// assume that the prevContour and the childContour has already been calculated
const conflict = childContour.reduce((maxConflict, contour, depth) => {
  const conflict = prevContour[depth].right - contour.left + 1;
  return depth === 0 ? conflict : Math.max(conflict, maxConflict);
}, 0);

child.delta += conflict;

这两棵子树解决了，但树并不一定只是二叉树，可能同一个结点的右侧还有其它孩子。现在它第三个孩子来了，它不能只考虑它的二哥，因为如果二哥比较矮，它可能会越过二哥踩到大哥的脚，这显然也不合理。

我们应该将前两棵子树合在一起考虑，将它们的轮廓「合并」，然后用这个结合后的轮廓与第三个孩子的子树一层层比较，得到第三个孩子的偏移量。那接下来的问题就变成了：如何合并两颗子树的轮廓？

这其实也不难，同样也是在每一层，我们只需要取左子树的左轮廓和右子树的右轮廓，把它们合成一个大轮廓就行了。如下图所示：

需要注意的是这两颗子树可能不一样高，我们需要在合并完两棵子树的公共部分之后再将高的那棵子树的剩余部分拼接上，就像归并排序的「归并」过程一样。

合并两个轮廓的代码逻辑如下：

prevContour = childContour
  .concat(prevContour.slice(childContour.length))
  .map((contour, depth) => ({
    left:
      depth >= prevContour.length
        ? contour.left + child.delta
        : prevContour[depth].left,
    right:
      depth >= childContour.length
        ? prevContour[depth].right
        : contour.right + child.delta,
  }));

开头的 childContour.concat(prevContour.slice(childContour.length)) 是拼成一个长度为 childContour 和 prevContour 两者长度最大值的数组。需要注意的是，因为右面 child 的子树已经整体右移了 delta 的距离，因此 child 的轮廓也应该右移同样的距离，用到 childContour 的地方都需要加上 child.delta 。

我们每次使用两棵子树合并的结果去更新左边子树轮廓 prevContour，并将新的子树作为右侧 childCountour。例如对于第四棵子树我们只需要将第三棵与之前两棵合并，再与第四棵比较；然后再将第四棵合并然后与第五棵比较，以此类推，直到安排好所有子树的位置。

进行到这里，已经不会出现位置上冲突的结点了。不过当处理完结点的所有子树的位置排布后，按照规则 3，要记得把它自己放置在子节点的正中间。

实现这部分的逻辑非常简单，前面已经说过，就是把最左侧的孩子和最右侧的孩子的 X 坐标相加除以二即可。就算它只有一个孩子，按照这样的算法它的 X 坐标就等于它唯一孩子的 X 坐标，即处在它孩子的正上方，依然符合我们的要求。仅当它没有孩子的时候，我们才需要特殊判断跳过这块的逻辑。

// centralize the parent node among all children
if (node.children.length > 0) {
  const lastChild = node.children[node.children.length - 1];
  node.x = (node.children[0].x + lastChild.x + lastChild.delta) / 2;
}

看上去这块代码比较简单，但仍有一些要注意的地方：首先我们移动的是这个结点的绝对坐标，而不是像之前一样带着它的整棵子树一起移动，所以这里应该修改 node.x 而不是 node.delta；其次，delta 只会因为与之前的子树相冲突而产生，而结点的最左侧孩子就是它的第一棵子树，因此它不会改变 delta 值，node.children[0].delta 这一项可以从代码中省略。

你可能会有疑问，如果我们就直接更改结点的 X 坐标值，不会与同一层结点位置产生冲突吗？实际上我们前面已经说过，我们在计算某个结点位置之前先计算的是它子树上的结点，遍历顺序是从下向上的，所以在某一次递归循环中处理当前结点时，它的祖先结点一定是还没有被处理到的，此时祖先们的 X 和 delta 值都还只是初始值。而它自身的位置信息只会在它的父节点排布它自己这棵子树时用到，这个过程还没有开始执行，所以结点修改自己的 X 坐标和 delta 并不会有任何的问题。

当我们安排好这一整层结点的位置后，最终的轮廓就是所有子树合在一起的轮廓，我们只需要在它的最上层附加上父亲结点（即上图中 A 结点）的轮廓，就能得到整棵子树的轮廓值，从而返回给上层递归参与上一层的子树位置排布。所以我们会在一次递归的结尾加上返回语句，这样整个递归过程就串联起来了。

return [
  { left: node.x + node.delta, right: node.x + node.delta },
].concat(contour);

还记得之前提过的第四条规则吗？如果某棵子树与之前的子树之间留出了空隙，则应该平均分配给它们中间的所有节点，以保证中间的悬垂结点不会偏向一侧。这里需要注意的是，被平均分配的应该是多余的空隙，而不是它们中间的整段空隙，否则就会打乱之前分配好的子树位置。举例来说：

为了看得清楚，这里我直接把结点的 X 坐标值写在节点上。上图的这棵树正在排布第二层的结点，其中第二层的 10.0 结点因为子树体积较大，必须要与前一个 8.0 结点中间留出 2.0 的空隙（如箭头所示）。按照规则，这 2.0 的空隙应该平均分配给 3.0 到 10.0 之间的所有结点（3.0 结点是导致空隙产生的原因，所以应该从它算起）。但是如果把 3.0 到 10.0 之间的整整 7.0 的空隙分配到中间所有结点间的 5 段间距中，也就是将每段间距改为 1.4，则会导致中间的两个节点的子树产生冲突：

正确的做法应该是：在这 2.0 的空隙中，分出必要的 1.0 空隙留下，将多余的 1.0 空隙平均分成五份添加到五段间距中，使得每段间距比之前增加了 0.2。因为每段间距都在增加，原本不会冲突的排布放宽后更不会冲突，因此这样就不会打乱之前安排好的子树位置。

接下来的问题是：我们应该如何得知分配区间的起始节点？就上图中的例子来说，这个 3.0 结点我们应该如何获知？

通过前面的分析我们已经知道，冲突值的大小是由当前子树与之前的右轮廓比较时得到的，而右轮廓又是每次由子树与之前的轮廓合并而来。如果我们能够记录一棵子树在合并的过程中更新了哪些层的右轮廓，我们就能在一层层比较以获取最大冲突层的同时，得知这一层轮廓的右侧节点属于哪棵子树，也就是分配空隙时的起始节点。这样说可能比较难以理解，看下图中的例子：

当 B 子树与 E 子树合并时，所有 E 子树高度范围内的右侧轮廓都被 E 子树所更新，而超过 E 子树高度的 D 结点未被更新，因此只有 E 和 F 两个右侧轮廓属于 E 子树。同样的，当 G 子树被合并进来时，它的高度只够更新自己这一层的轮廓，因此只有 G 这个轮廓属于 G 子树。图片中的 0、1、2 表示子树的编号（第几棵子树）。

有了右轮廓归属的子树这个信息，我们在一棵新子树加入进来时就能得知与它冲突的子树根结点是谁了。如果新来的子树与第三层的冲突最大，我们查找第三层的右轮廓，发现它对应的子树是 E，那么我们就应该将多余的空隙平均分到 E 到 H 之间的所有间距中。

这里还有一个小问题，如果当两层的冲突距离相同（同为最大值），那冲突结点应该选谁呢？如果只是取冲突值的大小，那取谁肯定都一样；但我们还需要获取冲突的子树编号时情况就有所不同了。看下面这棵树：

当 H 子树加入后，第三层和第四层的冲突值同为最大。此时 B 和 E 都成为了冲突结点；如果我们选取 B，将空隙平均分到 B 到 H 之间，因为 B 和 E 之间的间距变大，相应的 E 到 H 之间的间距就会缩小，这就会使得本来就是冲突节点的 E 距离 H 更近，从而它们的子树就有可能发生碰撞。

因此，在冲突值大小相同的结点中，我们应该选择层数更浅的冲突结点（也就是更靠右的结点，二者是等价的）。上图中，如果我们选择 E 结点，因为 B 与 E 之间的间距不受影响，也就不会有结点与 H 的子树发生碰撞。

调整一下之前的代码，让它不止统计冲突值，还额外添加一个 conflictIndex 用于记录冲突结点的编号：

const { conflict, conflictIndex } = childContour
  .slice(1, prevContour.length)
  .reduce(
    (max, item, depth) => {
      const conflict = prevContour[depth + 1].right - item.left + 1;
      return conflict > max.conflict
        ? { conflict, conflictIndex: prevContour[depth + 1].childIndex }
        : max;
    }, {
      conflict:
        prevContour.length > 0
          ? prevContour[0].right - childContour[0].left + 1
          : 0,
      conflictIndex: prevContour.length > 0 ? prevContour[0].childIndex : 0,
    }
  );
child.delta += conflict;

if (childIndex > 0) {
  // the excess gap should be divided equally among all intermediate nodes
  const gap = child.delta + child.x -
    (node.children[childIndex - 1].delta + node.children[childIndex - 1].x) - 1;
  for (let i = conflictIndex + 1; i < childIndex; ++i) {
    node.children[i].delta +=
      (gap * (i - conflictIndex)) / (childIndex - conflictIndex);
  }
}

其中第 1 到 17 行与之前差不多，由原来的 conflict 变为了 {conflict, conflictIndex} 的形式来同时统计两个量；同时为了简化之前的初始值比较逻辑，这里直接把初值写在了 reduce 的初值（第二个参数）里，并且使用 slice(1, length) 使函数从第二层开始比较（这里要注意用到 depth 的地方要变为 depth + 1）。

第 19 行之后是将多余的空隙平均分配的过程。gap 表示多余空隙的大小，通过循环将 gap 平分给 conflictIndex 到 childIndex 之间的所有结点，让它们连通子树一起移动得到的长度。

到此为止，我们的整棵树就已经符合了上述所有规则。One more thing，还记得我们之前用于表示整棵子树整体移动的 delta 值吗？它还没有下放到子树上的每个结点身上呢。我们还需要最后一步处理，通过一次遍历将所有标记应用到结点的 X 坐标上，确定结点的最终位置。

const pushDownDelta = (node: NodeWithProperties<DeltaPosition>): void => {
  node.x += node.delta;
  node.children.forEach((child) => {
    child.delta += node.delta;
    pushDownDelta(child);
  });
  node.delta = 0;
};

pushDownDelta(root);

需要注意的是，因为我们在前面的过程中存在将整棵子树向左移动的操作，因此 delta 可能为负值，最终可能会产生 X 坐标为负的结点。这其实无伤大雅，但如果你在渲染的过程中需要让结点坐标都为非负数，可以在 pushdown 的过程中顺带统计 X 坐标最小的结点，然后通过二次 pushdown 将整棵树对齐 X 坐标的 0 位置：

const pushDownDelta = (node: NodeWithProperties<DeltaPosition>): number => {
  node.x += node.delta;

  const min = node.children.reduce((prevMin, child) => {
    child.delta += node.delta;
    const childMin = pushDownDelta(child);
    return Math.min(prevMin, childMin);
  }, node.x);
  node.delta = 0;

  return min;
};

// pushdown twice to resolve negative coordinates
positionedRoot.delta -= pushDownDelta(positionedRoot);
pushDownDelta(positionedRoot);

完工！这就是 Reingold-Tilford 算法的全部内容。你可以试着修改下面树的结构，来看看 Reingold-Tilford 是如何对各种情况下的树进行排版的。

也许它不完全符合你的审美，但它绝对清晰且简洁。如果你想了解这个算法的更详细内容，你可以直接去翻这篇算法提出的原始论文，也可以看看这篇 blog 对它的描述。

完整代码在我的 GitHub 仓库，代码核心部分都已经贴在这里了。实现这个绘制算法其实是一些有关树的数据结构算法演示的子项目，因为觉得这个算法比较有趣（而且国内好像并没有关于它的太多资料），所以就单独写成一篇 blog 发出来。