大一棵树的画法（绘制一棵漂亮的树）

ps.本文是对https://llimllib.github.io/pymag-trees/文章的翻译，原文使用的是python语言，译者改用JavaScript实现，并在文章的最后加上了译者详细的解析，有思维导图等树形结构绘制需求的朋友千万别错过。

当我需要为我的项目绘制一些树的时候，我觉得肯定会有一种经典又简单的算法，但最终我发现了一些有意思的事情：树的布局不仅仅是一个NP完全问题，在树的绘制算法背后有一段漫长而有趣的历史。接下来，我会逐一介绍历史中出现的树绘制算法，尝试其中的每一种，并最终实现一个完全O(n)复杂度的树绘制算法。

问题是什么？

img

给我们一棵树T，我们要做的就是试着把它画出来，让别人一眼就能理解它，本篇文章中的每个算法都会给树节点一个(x,y)坐标，所以在算法运行之后它能在屏幕中绘制出来，或者打印出来。

为了存储树绘制算法的结果，我们会创建一个DrawTree数据结构来镜像我们绘制的树，我们唯一要假设的事情就是每个树节点都可以迭代其子节点，DrawTree的基本实现如下：

// 代码1 class DrawTree { constructor(tree, depth = 0) { this.x = -1 this.y = depth this.tree = tree this.children = tree.children.map((child) => { return new DrawTree(child, depth 1) }) } }

随着我们的方法越来越复杂，DrawTree的复杂度也会随之增加，现在来说，它只是把每个节点的x坐标赋值为-1，y坐标赋值为它在树中的深度，以及存储对树节点的引用。然后，它会递归的为每个节点创建一个DrawTree，从而构建该节点的子节点列表。这样一来，我们就构建了一个DrawTree来表示将要绘制的树，并给每个节点添加了特定的绘制信息。

随着我们在本文中实现更好的算法，我们将利用每个人的经历总结成的原则来帮助我们构建下一个更好算法，尽管生成一个“漂亮”的树形图是一个品味问题，但是这些原则还是会帮助我们优化程序输出。

故事是从Knuth开始的

我们要画的是一种根节点在顶部的特殊类型，它的子节点在它下面，以此类推，这类图形，以及这类问题的解决，在很大程度上归功于Donald Knuth，我们会从他这里得出前两个原则：

原则1：树的边不应该交叉

原则2：相同深度的节点应该绘制在同一水平线，这能让树的结构更清晰

Knuth的算法简单快速，但它只适用于二叉树，以及会生成一些相当畸形的图形，它是一个简单的树的中序遍历，设置一个全局的计数变量，用来作为x坐标，计数器会随着节点递增，代码如下：

// 代码2 let i = 0 const knuth_layout = (tree, depth) => { if (tree.left_child) { knuth_layout(tree.left_child, depth 1) } tree.x = i tree.y = depth i = 1 if (tree.right_child) { knuth_layout(tree.right_child, depth 1) } }

img

如上图所示，这个算法生成的树满足原则1，但它不是很美观，你可以看到Knuth的图会迅速横向扩展，因为它没有重用x坐标，即使这会使树明显更窄一点，为了避免像这样浪费空间，我们可以得出第三个原则：

原则3：树应该尽可能画的紧凑一点

一个简短的回顾

在我们继续学习更高级的算法之前，先让我们停下来了解一些术语，首先，在描述我们的数据节点之间的关系时，我们将使用家族树的比喻，节点的下面可以有子节点，左边或右边可以有兄弟节点，以及上面会有父节点。

我们已经讨论了树的中序遍历，接下来我们还会看到前序遍历和后序遍历，你可能在很久以前的“数据结构”课程上看到过这三个术语，但除非你最近一直在和树打交道，否则你可能已经对它们有点模糊了。

遍历方式只是决定我们在给定的节点上进行处理的时机，中序遍历，也就是上面的Knuth算法，只接受一个二叉树，意味着我们会先处理左子节点，然后是当前节点，然后是右子节点，前序遍历，意味着我们先处理当前节点，然后处理它的所有子节点，后序遍历则刚好和它相反。

最后，你可能已经了解了大写的O符号的概念，用来表示算法的时间复杂度，在本文中，我们会时不时的提起它，用它来作为一个简单的工具来判断一个算法在运行时间上能不能被接受。如果一个算法在它的主循环中频繁的遍历它的一个节点的所有子节点，我们称它的时间复杂度为O(n^2)，其他情况则为O(n)，如果你想了解更多细节，本文最后引用的论文中包含了大量关于这些算法时间复杂度的内容。

自下而上

Charles Wetherell和Alfred Shannon这两个人在1979年出现了，也就是在Knuth提出了树的布局算法的8年后，他们引入了一些创新技术，首先，他们展示了如何生成满足前面三个原则的尽可能紧凑的树，通过后序遍历，只需要维护同一深度的下一个节点的位置：

// 代码3 const nexts = [] const minimum_ws = (tree, depth = 0) => { if (nexts[depth] === undefined) { nexts[depth] = 0 } tree.x = nexts[depth] tree.y = depth nexts[depth] = 1 tree.children.forEach((child) => { minimum_ws(child, depth 1) }) }

img

尽管这个算法生成的树满足我们所有的原则，但是你可能也会同意实际绘制出来是很丑的，即使是在上图这样一个简单的树中，也很难快速的确定树节点之间的关系，而且整个树看着似乎都被挤在一起了。现在是时候引入下一个原则了，它会帮助优化Knuth树和最小宽度树：

原则4：父节点应该位于子节点中间

到目前为止，我们能使用非常简单的算法去绘制树是因为我们没有真正的考虑每个节点自身，我们依赖全局的计数器来防止节点重叠，为了满足父节点位于子节点中间的原则，我们需要考虑每个节点的自身上下文状态，那么需要一些新的策略。

Wetherell和Shannon介绍的第一个策略是通过树的后序遍历从底部开始构建树，而不是像代码2那样从上到下，或者像代码3一样从中间穿过，只要你以这种方式看待这棵树，那么让父节点居中是一个很简单的操作，只要把它子节点的x坐标分成两半。

img

但是我们必须记住，在构建树的右侧时，要注意树的左侧，如上图所示，树的右侧被推到右边为了容纳左侧，为了实现这一分离，Wetherell和Shannon在代码2的基础上通过数组维护下一个可用点，但只有在将父树居中会导致树的右侧与左侧重叠时，才使用下一个可用的位置。

Mods和Rockers

在我们看更多代码之前，让我们仔细看看自下而上构建树的结果，如果节点是叶子节点，我们会给它下一个可用的x坐标，如果它是一个分支，则把它居中在它的子节点之上，然而，如果将分支居中会导致它与树的另一部分发生冲突，我们就需要正确的把它移动足够的距离来避免冲突。

当我们把分支移动正确时，我们需要移动它的所有子节点，否则我们将失去我们一直在努力维护的中心父节点，写一个将分支及其子树移动正确的函数是很容易的：

// 代码4 const move_right = (branch, n) => { branch.x = n branch.children.forEach((child) => { move_right(child, n) }) }

上面这个函数可以工作，但是存在一个问题，如果我们使用这个函数来向右移动一个子树，我们将在递归（放置树节点）中进行递归（移动树），这意味着我们的算法效率很低，时间复杂度为O(n²)。

为了解决这个问题，我们将为每个节点添加一个mod属性，当我们到达一个分支时我们需要正确的移动n个空间，我们会把x坐标加上n，并赋值给mod属性，然后愉快的继续执行布局算法，因为我们是自下而上移动，所以不需要担心树的底部发生冲突（我们已经证明了它们不会），我们等一会再把它们移动正确。

一旦执行完了第一个树的遍历，我们就开始进行第二个遍历过程，将需要正确移动的分支进行移动，因为我们只遍历了每个节点一次，并且执行的只是算术运算，我们可以确定它的时间复杂度和第一次一样，都为O(n)，所以两次合起来还是O(n)。

下面的代码演示了父节点居中和使用mod属性来提高代码的效率：

// 代码5 class DrawTree { constructor(tree, depth = 0) { this.x = -1; this.y = depth; this.tree = tree; this.children = tree.children.map((child) => { return new DrawTree(child, depth 1); }); this.mod = 0; } } const setup = (tree, depth = 0, nexts = {}, offset = {}) => { tree.children.forEach((child) => { setup(child, depth 1, nexts, offset); }); tree.y = depth; let place; let childrenLength = tree.children.length if (childrenLength <= 0) { place = nexts[depth] || 0; tree.x = place; } else if (childrenLength === 1) { place = tree.children[0].x - 1; } else { let s = tree.children[0].x tree.children[1].x; place = s / 2; } offset[depth] = Math.max(offset[depth] || 0, (nexts[depth] || 0) - place); if (childrenLength > 0) { tree.x = place offset[depth]; } if (nexts[depth] === undefined) { nexts[depth] = 0; } nexts[depth] = 2; tree.mod = offset[depth]; }; const addmods = (tree, modsum = 0) => { tree.x = tree.x modsum; modsum = tree.mod; tree.children.forEach((child) => { addmods(child, modsum); }); }; const layout = (tree) => { setup(tree); addmods(tree); return tree; };

树作为Block块

虽然在很多情况下它确实产生了不错的效果，但是代码5也会产生一些奇怪的树，就像上图（抱歉，图已丢失在岁月的长河中），Wetherell-Shannon算法的另一个理解上的困难是，相同的树结构，当放在树的不同位置时，可能会绘制出不同的结构。为了解决这个问题，我们会从Edward Reingold和John Tilford的论文中借鉴一个原则：

原则5：同一个子树无论在树的哪个位置，绘制的结果都应该相同

尽管这会扩大我们的绘制宽度，但是这个原则会有助于它们传达更多信息。它还有助于简化自下而上的遍历，比如，一旦我们计算出一个子树的x坐标，我们只需要将它作为一个单位向左或向右移动。

下面是代码6的算法大致过程：

• 对树进行后序遍历
• 如果一个节点是叶子节点，那么给它一个值为0的x坐标
• 否则，在不产生冲突的情况下，将它的右子树尽可能靠近左子树 使用与前面相同的mod方式，在O(n)时间内移动树
• 将节点放置在其子节点中间
• 再遍历一次树，将累积的mode值加到x坐标上

这个算法很简单，但是要执行它，我们需要引入一些复杂性。

轮廓

img

树的轮廓是指树的一边最大或最小的坐标组成的列表，如上图，有两棵树，它们重叠在一起，如果我们沿着左边树的左边，取每层的最小x坐标，我们可以得到[1, 1, 0]，我们把它叫做树的左轮廓，如果我们沿着右边，取每一层最右边的x坐标，可以得到[1, 1, 2]，也就是树的右轮廓。

为了找出右边树的左轮廓，我们同样取每一层最左边节点的x坐标，可以得到[1, 0, 1]，此时，可以看到轮廓有一个有趣的特性，就是并非所有节点都以父子关系连接，第二层的0不是第三层的1的父节点。

如果我要根据代码6连接这两个树，我们可以找到左边树的右轮廓，以及右边树的左轮廓，然后我们就可以轻松的找到我们需要的将右边的树推到右边使它不会和左边树重叠的最小值，下面的代码是一个简单的实现：

// 代码7 const lt = (a, b) => { return a < b } const gt = (a, b) => { return a > b } // [a, b, c],[d, e, f] => [[a, d], [b, e], [c, f]] const zip = (a, b) => { let len = Math.min(a.length, b.length) let arr = [] for(let i = 0; i < len; i ) { arr.push([a[i], b[i]]) } return arr } const push_right = (left, right) => { // 左边树的右轮廓 let wl = contour(left, lt) // 右边树的左轮廓 let wr = contour(right, gt) let res = zip(wl, wr) let arr = res.map((item) => { return item[0] - item[1] }) return Math.max(...arr) 1 } // 获取一棵树的轮廓 const contour = (tree, comp, level = 0, cont = null) => { // 根节点只有一个，所以直接添加 if (cont === null) { cont = [tree.x] } else if (cont.length < level 1) {// 该层级尚未添加，直接添加 cont.push(tree.x) } else if (comp(cont[level], tree.x)) {// 该层级已经有值，所以进行比较 cont[level] = tree.x } tree.children.forEach((child) => { contour(child, comp, level 1, cont) }) return cont }

如果我们用上图的两棵树运行push_right方法，我们可以得到左边树的右轮廓[1, 1, 2]和右边树的左轮廓[1, 0, 1]，然后比较这些列表，找出它们之间的最大空间，并添加一个空格填充。对于上图的两棵树，将右边的树向右推两个空格将能防止它与左边的树重叠。

新线程

使用代码7，我们可以正确的找到需要把右边树推多远的值，但是为了做到这个，我们需要扫描两个子树的每个节点去得到我们需要的轮廓，因为它需要的时间复杂度很可能是O(n^2)，Reingold和Tilford为此引入了一个令人困惑的概念，叫做线程，它们与用于并行执行的线程意义完全不同。

img

线程是一种方法，它通过在轮廓上的节点之间创建链接（如果其中一个节点已经不是另一个节点的子节点）来减少扫描子树轮廓所需要的时间，如上图所示，虚线表示一个线程，而实线表示父子关系。

我们也可以利用这个事实，如果一棵树比另一棵树深，我们只需要往下走到较矮的那棵树。任何更深的内容都不需要这两棵树再进行分离，因为它们之间不可能会有冲突。

使用线程以及遍历到较矮的树，我们可以得到一个树的轮廓，并使用下面的代码在线性的时间复杂度内设置线程。

// 代码8 const nextright = (tree) => { if (tree.thread) { return tree.thread } else if (tree.children.length > 0) { return tree.children[tree.children.length - 1] } else { return null } } const nextleft = (tree) => { if (tree.thread) { return tree.thread } else if (tree.children.length > 0) { return tree.children[0] } else { return null } } const contour = (left, right, max_offset = 0, left_outer = null, right_outer = null) => { if (left_outer === null) { left_outer = left } if (right_outer === null) { right_outer = right } if (left.x - right.x > max_offset) { max_offset = left.x - right.x } let lo = nextleft(left) let li = nextright(left) let ri = nextleft(right) let ro = nextright(right) if (li && ri) { return contour(li, ri, max_offset, lo, ro) } return max_offset }

很明显可以看到，这个过程只访问被扫描的子树中每一层的两个节点。

把它们组合起来

代码8计算轮廓的过程简洁且快速，但它不能和我们更早的时候讨论的mod方式一起工作，因为一个节点实际的x坐标是该节点的x值加上从它到根节点路径上的所有mod值之和。为了解决这个问题，我们需要给轮廓算法增加一些复杂度。

我们要做的第一件事就是需要维护两个额外的变量，左子树上的mod值之和以及右子树的mod值之和，这些对于计算轮廓上的每个节点实际的位置来说是必需的，这样我们就可以检查它是否与另一侧的节点发生冲突：

// 代码9 const contour = (left, right, max_offset = null, loffset = 0, roffset = 0, left_outer = null, right_outer = null) => { let delta = left.x loffset - (right.x roffset) if (max_offset === null || delta > max_offset) { max_offset = delta } if (left_outer === null) { left_outer = left } if (right_outer === null) { right_outer = right } let lo = nextleft(left_outer) let li = nextright(left) let ri = nextleft(right) let ro = nextright(right_outer) if (li && ri) { loffset = left.mod roffset = right.mod return contour(li, ri, max_offset, loffset, roffset, lo, ro) } return [li, ri, max_offset, loffset, roffset, left_outer, right_outer] }

我们要做的另外一件事是在退出的时候返回函数的当前状态，这样我们就可以在线程节点上设置适当的偏移量。有了这些信息，我们就可以看看这个函数，它使用代码8去让两个树尽可能的靠在一起：,

// 代码10 const fix_subtrees = (left, right) => { let [li, ri, diff, loffset, roffset, lo, ro] = contour(left, right) diff = 1 diff = (right.x diff left.x) % 2 right.mod = diff right.x = diff if (right.children.length > 0) { roffset = diff } if (ri && !li) { lo.thread = ri lo.mod = roffset - loffset } else if (li && !ri) { ro.thread = li ro.mod = loffset - roffset } return (left.x right.x) / 2 }

等我们运行完轮廓的过程，我们将左树和右树之间的最大差加1，这样他们就不会发生冲突，如果中间点是奇数，那么就再加1，这让我们测试更方便 - 所有的节点都有整数x坐标，不会损失精度。

然后我们将右边的树向右移动相应的距离，请记住，我们在x坐标上加上diff并且也把diff保存到mod属性上的原因是mod值只用于当前节点下面的节点。如果右子树有超过一个子节点，我们将差异添加到roffset，因为右节点的所有子节点都要向右移动那么远。

如果树的左边比右边深，或反过来，我们需要设置一个线程。我们只是检查一侧的节点指针是否比另一侧的节点指针前进得更远，如果是的话，将线程从浅的树的外侧设置到深的树的内侧。

为了正确处理我们之前提到的mod值，我们需要在线程节点上设置一个特殊的mod值，因为我们已经更新了我们右侧偏移值来反应右侧树的移动量，我们需要做的就是将线程节点的mod值设置为更深层次树的偏移量与它本身的差值。

现在我们就已经有了合适的代码来找到树的轮廓，并将两棵树尽可能近的放在一起，我们可以很容易的实现上面描述的算法。我将不加注释地呈现其余的代码：

// 代码11 const layout = (tree) => { return addmods(setup(tree)) } const addmods = (tree, mod = 0) => { tree.x = mod tree.children.forEach((child) => { addmods(child, mod tree.mod) }) return tree } const setup = (tree, depth = 0) => { if (tree.children.length === 0) { tree.x = 0 return tree } else if (tree.children.length === 1) { tree.x = setup(tree.children[0], depth 1).x return tree } left = setup(tree.children[0], depth 1) right = setup(tree.children[1], depth 1) tree.x = fix_subtrees(left, right) return tree }

扩展到N叉树

现在我们终于得到一个画二叉树的算法，并且满足我们所有的原则，在大部分情况下看起来都不错，并且为线性时间复杂度，那么很自然的就会想到如何把它扩展为支持任意多个子节点的树。如果你一直看到这里，你可能会想，我们是不是只需要把刚定义的美妙的算法应用到节点的所有子节点上即可。

扩展前面的算法使之能在多叉树上工作：

• 对树进行后序遍历
• 如果节点是叶子节点，那么给它一个值为0的x坐标
• 否则，遍历它的子节点，将其子节点放置在尽可能靠近其左边兄弟节点的位置
• 将父节点放置在其最左边和最右边子节点的中间

img

这个算法可以工作，并且很快，但是会有一个问题，它把节点的所有子树都尽可能填到左边，如果最右边的节点与最左边的节点发生冲突，那么中间的树都将被填充到右边。让我们采用绘制树的最后一个原则来解决这个问题：

原则6：同一个父节点的子节点应该间隔均匀

为了对称且快速地画出N叉树，我们需要用到目前为止我们学到的所有技巧，并且还要再加上一些新技巧，这要感谢Christoph Buchheim等人最近发表的一篇论文，我们已经有了所有的知识储备来做这些并且仍然能够在线性时间内完成。

对上述算法进行修改，使其满足原则6，我们需要一个方法来分隔两棵冲突的大树之间的树，最简单的方法是，每当两棵树发生冲突时，将可用空间除以树的数量，然后移动每棵树，使它的和它相邻的树分隔那个距离。举个例子，在上图，右边和左边的大树之间存在一个距离n，在它们之间存在3棵树，如果我们把第一棵树和最左边的间隔n/3距离，下一个又和这个间隔n/3，以此类推，就会得到满足原则6的树。

到目前为止，我们在本文中看到的每一个简单的算法，我们都会发现它的不足之处，这个也不例外，如果我们必须在每两棵有冲突的树之间移动所有的树，我们又会在算法中引入一个O(n^2)复杂度的运算。

这个问题的解决方式和前面我们解决移位问题类似，我们引入mod，而不是每次有冲突时都在中间移动每个子树，我们把我们在中间需要移动的树的值保存起来，在放置完所有节点后再应用。

为了正确的求出我们需要移动中间节点的距离，我们需要能够找到两个冲突节点之间的树的数量，当我们只有两棵树时，很明显，所有的冲突都发生在左树和右树之间，当有任意棵树时，找出是哪棵树引起了冲突就成为了一个挑战。

为了应对这个挑战，我们将引入一个默认的祖先变量，并向树的数据结构中添加另一个成员，我们称之为ancestor，ancestor要么指向自身，要么指向它所属树的根，当我们需要找到一个节点属于哪一棵树的时候，如果这个属性设置了就使用它，否则使用default_ancestor。

当我们放置一个节点的第一个子树，我们把default_ancestor指向这个子树，假设如果下一棵树发生了冲突，那么一定是与第一棵树发生的，当我们放置好了第二棵树后，我们区分两种情况，如果第二棵子树没有第一棵深，我们遍历它的右轮廓，将ancestor 属性设置为第二棵树的根，否则，第二棵树就是比第一棵树深，这意味着与下一棵树冲突的任何内容都将被放置在第二棵树中，因此我们只需设置default_ancestor 来指向它。

话不多说，我们来看看由Buchheim提出的一个时间复杂度为O(n)的树绘制算法：

请看下下下节: ）

总结

在本文中，我略去了一些东西，因为我觉得为了最终算法尝试并呈现一个逻辑进展更重要，而不是用纯代码重载文章。如果你想要查看更多细节，或者想知道在各个代码清单中使用的树的数据结构，你可以去https://github.com/llimllib/pymag-trees/这个仓库下载每个算法的源代码、一些基本的测试、以及用于生成本文的树图片的代码。

引用

1 K. Marriott, NP-Completeness of Minimal Width Unordered Tree Layout, Journal of Graph Algorithms and Applications, vol. 8, no. 3, pp. 295-312 (2004). http://www.emis.de/journals/JGAA/accepted/2004/MarriottStuckey2004.8.3.pdf

2 D. E. Knuth, Optimum binary search trees, Acta Informatica 1 (1971)

3 C. Wetherell, A. Shannon, Tidy Drawings of Trees, IEEE Transactions on Software Engineering. Volume 5, Issue 5

4 E. M. Reingold, J. S Tilford, Tidier Drawings of Trees, IEEE Transactions on Software Engineering. Volume 7, Issue 2

5 C. Buchheim, M. J Unger, and S. Leipert. Improving Walker's algorithm to run in linear time. In Proc. Graph Drawing (GD), 2002. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.8757

译者的个人发挥算法详细分解

虽然作者已经花了这么大篇幅来引出最后的算法，但是直接放出来，大概率还是看不懂的，所以译者尝试分解一下，想直接看原版的可以点此listing12.py。

节点类如下，请务必仔细看一下right()和left()方法：

// 树节点类 class DrawTree { constructor(tree, parent = null, depth = 0, number = 1) { // 节点名称 this.name = tree.name; // 坐标 this.x = -1; this.y = depth; // 子节点 this.children = tree.children.map((child, index) => { return new DrawTree(child, this, depth 1, index 1); }); // 父节点 this.parent = parent; // 线程节点，也就是指向下一个轮廓节点 this.thread = null; // 根据左兄弟定位的x与根据子节点中间定位的x之差 this.mod = 0; // 要么指向自身，要么指向所属树的根 this.ancestor = this; // 记录分摊偏移量 this.change = this.shift = 0; // 最左侧的兄弟节点 this._lmost_sibling = null; // 这是它在兄弟节点中的位置索引 1...n this.number = number; } // 关联了线程则返回线程节点，否则返回最右侧的子节点，也就是树的右轮廓的下一个节点 right() { return ( this.thread || (this.children.length > 0 ? this.children[this.children.length - 1] : null) ); } // 关联了线程则返回线程节点，否则返回最左侧的子节点，也就是树的左轮廓的下一个节点 left() { return ( this.thread || (this.children.length > 0 ? this.children[0] : null) ); } // 获取前一个兄弟节点 left_brother() { let n = null; if (this.parent) { for (let i = 0; i < this.parent.children.length; i ) { let node = this.parent.children[i]; if (node === this) { return n; } else { n = node; } } } return n; } // 获取同一层级第一个兄弟节点，如果第一个是自身，那么返回null get_lmost_sibling() { if ( !this._lmost_sibling && this.parent && this !== this.parent.children[0] ) { this._lmost_sibling = this.parent.children[0]; } return this._lmost_sibling; } // 同一层级第一个兄弟节点 get leftmost_sibling() { return this.get_lmost_sibling(); } }

进入第一次递归，处理如下：

1.当前节点是叶子节点且无左兄弟，x设为0

2.当前节点是叶子节点且有左兄弟，x为左兄弟的x加上间距，即根据左兄弟定位

3.当前节点非叶子节点且无左兄弟，x为第一个子节点的x加上最后一个子节点的x除以2，即根据子节点定位

4.当前节点非叶子节点且有左兄弟，x为左兄弟的x加上间距，mod设为x相对子节点定位的差值

// 第一次递归 const firstwalk = (v, distance = 1) => { if (v.children.length === 0) { // 当前节点是叶子节点且存在左兄弟节点，则其x坐标等于其左兄弟的x坐标加上间距distance if (v.leftmost_sibling) { v.x = v.left_brother().x distance; } else { // 当前节点是叶节点无左兄弟，那么x坐标为0 v.x = 0; } } else { // 后序遍历，先递归子节点 v.children.forEach((child) => { firstwalk(child); }); // 子节点的中点 let midpoint = (v.children[0].x v.children[v.children.length - 1].x) / 2; // 左兄弟 let w = v.left_brother(); if (w) { // 有左兄弟节点，x坐标设为其左兄弟的x坐标加上间距distance v.x = w.x distance; // 同时记录下偏移量（x坐标与子节点的中点之差） v.mod = v.x - midpoint; } else { // 没有左兄弟节点，x坐标直接是子节点的中点 v.x = midpoint; } } return v; };

第二次递归将mod值加到x上，使父节点仍旧居中于子节点：

// 第二次遍历 const second_walk = (v, m = 0, depth = 0) => { // 初始x值加上所有祖宗节点的mod值（不包括自身的mod） v.x = m; v.y = depth; v.children.forEach((child) => { second_walk(child, m v.mod, depth 1); }); };

整个过程也就是两次递归：

const buchheim = (tree) => { let dt = firstwalk(tree); second_walk(dt); return dt; };

第一次递归后的节点位置：

image-20220318102931215.png

第二次递归后的节点位置：

image-20220318102949466.png

明显存在冲突的子树可以看到是G和P两棵子树，子树P需要向右移动一定的距离才行，这个距离怎么算呢？

1.进入子树G和P的第二层，找到子树G在这一层中的最右侧子节点，为F，找到子树P在这一层的最左侧子节点，为I，比较它们的x坐标，原始x值加上它们祖先节点的mod值之和，比较后发现没有交叉，于是进入下一层。

2.进入第三层，同样找到子树G在这一层中的最右侧子节点，为E，子树P在这一层的最左侧子节点，为J，比较它们的x，发现存在交叉，这个差值再加上节点的间隔distance就是子树P需要向右移动的距离

3.重复以上，直到最底层。

那么怎么最快速的找到每一层的最左侧或最右侧节点呢，当然可以直接递归，但是时间复杂度就非线性了，所以就引入了前面所说的线程的概念。

以上图中的G节点为例介绍线程的连接过程，从它的子节点C回来后因为C没有左兄弟，所以不处理，进入F节点递归，从F节点回来之后紧接着处理F节点，它存在左兄弟C，因为每棵树都有内侧和外侧，所以我们设置四个指针：

image-20220318104203798.png

vInnerLeft为当前节点的左兄弟节点，vOuterLeft为当前节点的最左侧的兄弟节点，当然对于F节点来说，这两个指针都指向C节点，vInnerRight和vOuterRight初始都指向当前节点。

接下来我们就将线程从浅的树的外侧设置到深的树的内侧：

1.因为C和F节点都存在子节点，所以这一层还无法判断哪棵树深哪棵树浅，所以就下移一层，同时更新四个指针，这里就会用到节点的left()或right()方法：

image-20220318105921843.png

这里存在四个指针，怎么判断是否还有下一层呢，因为我们要检查节点冲突是根据两棵树的内侧节点进行比较，所以这里也只需要检查两个内侧节点指针来判断是否还有下一层，我们只需走到较浅的树即可停止，另一棵树更深的节点不会发生冲突，所以判断vInnerLeft.right()和vInnerRight.left()是否都存在即可。

2.下移一层后发现已经达到F的叶子节点了，那么接下来就进行判断，重复一下我们的原则：

将线程从浅的树的外侧设置到深的树的内侧

浅的树为F子树，深的树为C子树，那么从F的外侧设置到C的内侧，也就是要将E节点和A节点通过线程连接起来。

具体的判断规则为：

2.1.如果vInnerLeft.right()节点（也就是B节点所在树的右侧轮廓的下一个节点，这里是存在的，为A节点）存在，且vOuterRight.right()节点（也就是E节点所在树的右侧轮廓的下一个节点，这里是不存在的）不存在，那么就在vOuterRight节点上设置线程thread属性指向vInnerLeft.right()节点，这里刚好满足这个条件，所以E.thread指向了A节点。

2.2.否则如果vOuterLeft.left()节点（也就是B节点所在树的左轮廓的下一个节点，这里是存在的，为A节点）不存在，且vInnerRight.left()节点（也就是D节点所在树的左轮廓的下一个节点，这里是不存在的）存在，那么就在vOuterLeft节点上设置线程thread属性指向vInnerRight.left()节点，显然这里不满足条件。

对于其他所有节点，都用这种方法判断，最终这棵树上线程节点连接为：

image-20220318112225285.png

因为我们是后序遍历树，所以越下层的节点线程连接的越早，比如处理O节点时候就会把I和J节点连接起来了，那么在后面处理P节点时，虽然也走到了I节点，但是I节点因为有了线程节点，所以一定程度上它就不是“叶子节点”了，所以I不会再被连接到其他节点上。

// 第一次递归 const firstwalk = (v, distance = 1) => { if (v.children.length === 0) { // ... } else { v.children.forEach((child) => { firstwalk(child); apportion(child);// }); // ... } // ... } const apportion = (v) => { let leftBrother = v.left_brother(); // 存在左兄弟才处理 if (leftBrother) { // 四个节点指针 let vInnerRight = v;// 右子树左轮廓 let vOuterRight = v;// 右子树右轮廓 let vInnerLeft = leftBrother;// 当前节点的左兄弟节点，左子树右轮廓 let vOuterLeft = v.leftmost_sibling;// 当前节点的最左侧的兄弟节点，左子树左轮廓 // 一直遍历到叶子节点 while(vInnerLeft.right() && vInnerRight.left()) { // 更新指针 vInnerLeft = vInnerLeft.right() vInnerRight = vInnerRight.left() vOuterLeft = vOuterLeft.left() vOuterRight = vOuterRight.right() } // 将线程从浅的树的外侧设置到深的树的内侧 if (vInnerLeft.right() && !vOuterRight.right()) { vOuterRight.thread = vInnerLeft.right(); } else { if (vInnerRight.left() && !vOuterLeft.left()) { vOuterLeft.thread = vInnerRight.left(); } } } };

线程节点连接好了，接下来就可以根据轮廓判断两棵树是否存在交叉，同样因为我们是后序遍历，所以判断某个子树是否存在冲突时它下面的节点线程肯定已经连接完成了，可以直接使用。

根据轮廓判断的逻辑同样也放在apportion方法里：

// 第一次递归 const firstwalk = (v, distance = 1) => { if (v.children.length === 0) { // ... } else { v.children.forEach((child) => { firstwalk(child); apportion(child, distance);// distance }); // ... } // ... } const apportion = (v, distance) => { let leftBrother = v.left_brother(); if (leftBrother) { // ... // 从当前节点依次往下走，判断是否和左侧的子树发生冲突 while(vInnerLeft.right() && vInnerRight.left()) { // ... // 左侧节点减右侧节点 let shift = vInnerLeft.x distance - vInnerRight.x if (shift > 0) { // 大于0说明存在交叉，那么右侧的树要向右移动 move_subtree(v, shift) } } // ... } } // 移动子树 const move_subtree = (v, shift) => { v.x = shift// 自身移动 v.mod = shift// 后代节点移动 }

以节点P为例，过程如下：

image-20220318154717319.png

vInnerLeft.right()存在（H.right()=F），vInnerRight.left()存在（P.left()=I），所以下移一层：

image-20220318154901212.png

比较F和I节点的x坐标之差可以发现它们不存在冲突，于是继续下一层：

image-20220318155104532.png

这一次比较会发现E和J节点发生冲突，那么子树P需要整体向右移动一定距离。

当然，上述代码是有问题的，因为一个节点真正的最终x坐标是还要加上它所有祖宗节点的mod值，所以我们新增四个变量来累加mod值：

const apportion = (v, distance) => { if (leftBrother) { // 四个节点指针 // ... // 累加mod值，它们的父节点是同一个，所以往上它们要加的mod值也是一样的，那么在后面shift值计算时vInnerLeft.x 父节点.mod - (vInnerRight.x 父节点.mod)，父节点.mod可以直接消掉，所以不加上面的祖先节点的mod也没关系 let sInnerRight = vInnerRight.mod; let sOuterRight = vOuterRight.mod; let sInnerLeft = vInnerLeft.mod; let sOuterLeft = vOuterLeft.mod; // 从当前节点依次往下走，判断是否和左侧的子树发生冲突 while (vInnerLeft.right() && vInnerRight.left()) { // ... // 左侧节点减右侧节点，需要累加上mod值 let shift = vInnerLeft.x sInnerLeft distance - (vInnerRight.x sInnerRight); if (shift > 0) { // ... // v.mod，也就是节点P.mod增加了shift，sInnerRight、sOuterRight当然也要同步增加 sInnerRight = shift; sOuterRight = shift; } // 累加当前层节点mod sInnerRight = vInnerRight.mod; sOuterRight = vOuterRight.mod; sInnerLeft = vInnerLeft.mod; sOuterLeft = vOuterLeft.mod; } // ... } };

效果如下：

image-20220318155814623.png

但是这样依然是有问题的，为啥呢，比如对于节点E来说，它累加上了节点F、H的mod值，但问题是H节点并不是E节点的祖先，它们只是通过一根线程虚线产生了连接而已，实际要加上的应该是节点F、G的mod值才对，这咋办呢，还是以例子来看，我们假设部分节点的mod值如下：

image.png

那么对于节点A真正要累加的mod值应该为：

B.mod C.mod G.mod = 1 2 3 = 6

但是因为线程连接，实际累加的mod值变成了：

E.mod F.mod H.mod = 0 4 0 = 4

少了2，如果能在线程节点E和H上设置一个特殊的mod值上，来弥补上这相差的值岂不美哉，反正因为它们两个下面也没有子节点了，所以无论给它们设置什么mod值都不会有影响。那么这个特殊的mod值又怎么计算呢？很简单，比如在第一次处理F节点时，它存在左节点C，所以进行它们下面的节点的线程连接判断，因为它们都存在子级，所以下移一层，此时F子树到头了，C子树没有，此时满足vInnerLeft.right() && !vOuterRight.right()的条件，会把E连接到A，对于C和F来说，它们的祖先节点都是一样的，所以祖先节点的mod值不用管，那么对于A节点来说，它真正要累加的mod值为B.mod C.mod，而根据线程连接它会加上的mod值为E.mod F.mod，两个式子的运算结果要相同，那么求E.mod显然等于B.mod C.mod - F.mod，也就是sInnerLeft - sOuterRight，修改代码如下：

// 将线程从浅的树的外侧设置到深的树的内侧 if (vInnerLeft.right() && !vOuterRight.right()) { vOuterRight.thread = vInnerLeft.right(); // 修正因为线程影响导致mod累加出错的问题，深的树减浅的树 vOuterRight.mod = sInnerLeft - sOuterRight// } else { if (vInnerRight.left() && !vOuterLeft.left()) { vOuterLeft.thread = vInnerRight.left(); vOuterLeft.mod = sInnerRight - sOuterLeft// } }

此时效果如下：

image.png

到这里冲突是没有了，但是H的位置应该居中才对，显然是要向右移动，移动多少呢，子树P向右移动了shift距离，那么这个距离需要平分到G、H、P三个节点之间的间距上，假设两个冲突子树之间的子树数量为n，那么就是shift / (n 1)，子树H向右移动这个距离即可。

换言之，我们先要找到是哪两棵子树发生了冲突，才能修正它们之间的树，上图可以看到发生冲突的是E和J节点，对于J节点，我们肯定知道它属于当前的顶层子树P，那么只要能找出E节点所属的树即可，我们可以一眼就看出来是G节点，但是代码没有眼，可以直接通过向上递归来找，但是为了线性时间复杂度我们也不能这么做。

我们给每个节点都设置一个ancestor属性，初始都指向自身，对于E节点，虽然在冲突判断时它属于vInnerLeft节点，但是在它所属的树上，它属于vOuterRight节点，所以在线程连接阶段，我们可以顺便设置一下每层的vOuterRight节点的ancestor，让它指向当前的顶层节点v，但是这个指向有时不一定满足我们的要求，比如上图的N节点，它的ancestor成功的指向了P节点，但是对于E节点来说，它的ancestor指向的是它的父节点F，而我们需要的是G，所以我们再设置一个变量default_ancestor，当一个节点的ancestor指向不满足我们的要求时就使用default_ancestor指向的节点，default_ancestor初始指向一个节点的第一个子节点，然后从每个子节点回来时都更新该指针，如果前一个子节点没有后一个子节点深，那么default_ancestor就更新为指向后一个子节点，因为如果右侧有子树和左侧发生冲突，那么一定是和较深的那一棵。

const firstwalk = (v, distance = 1) => { if (v.children.length === 0) { // ... } else { let default_ancestor = v.children[0]// 初始指向第一个子节点 v.children.forEach((child) => { firstwalk(child); default_ancestor = apportion(child, distance, default_ancestor);// 递归完每一个子节点都更新default_ancestor }); } } const apportion = (v, distance, default_ancestor) => { let leftBrother = v.left_brother(); if (leftBrother) { // ... while (vInnerLeft.right() && vInnerRight.left()) { // ... // 节点v下面的每一层右轮廓节点都关联v vOuterRight.ancestor = v;// // ... } // ... if (vInnerLeft.right() && !vOuterRight.right()) { // ... } else { // ... default_ancestor = v// ，前面的节点没有当前节点深，那么default_ancestor指向当前节点 } } return default_ancestor;// }

然后我们就可以找出左侧树发生冲突的节点所属的根节点：

const apportion = (v, distance, default_ancestor) => { let leftBrother = v.left_brother(); if (leftBrother) { // ... while (vInnerLeft.right() && vInnerRight.left()) { // ... let shift = vInnerLeft.x sInnerLeft distance - (vInnerRight.x sInnerRight); if (shift > 0) { // 找出vInnerLeft节点所属的根节点 let _ancestor = ancestor(vInnerLeft, v, default_ancestor)// move_subtree(v, shift); // ... } // ... } // ... } return default_ancestor;// } // 找出节点所属的根节点 const ancestor = (vInnerLeft, v, default_ancestor) => { // 如果vInnerLeft节点的ancestor指向的节点是v节点的兄弟，那么符合要求 if (v.parent.children.includes(vInnerLeft.ancestor)) { return vInnerLeft.ancestor; } else { // 否则使用default_ancestor指向的节点 return default_ancestor } }

找出了是哪两棵树发生冲突后我们就能找到这两棵树之间的子树，然后把shift分摊给它们即可，不过我们还是不能直接遍历它们进行修正，没错，还是为了保持线性时间复杂度，所以只能先把分摊数据保存到这两棵冲突的树根节点上，然后等它们的所有兄弟节点都递归完成了再一次性设置。

const firstwalk = (v, distance = 1) => { if (v.children.length === 0) { // ... } else { let default_ancestor = v.children[0] v.children.forEach((child) => { firstwalk(child); default_ancestor = apportion(child, distance, default_ancestor); }); // 将shift分摊添加到中间节点的x及mod值上 execute_shifts(v)// // ... } } const apportion = (v, distance, default_ancestor) => { let leftBrother = v.left_brother(); if (leftBrother) { // ... while (vInnerLeft.right() && vInnerRight.left()) { // ... if (shift > 0) { let _ancestor = ancestor(vInnerLeft, v, default_ancestor) move_subtree(_ancestor, v, shift);// // ... } // ... } // ... } return default_ancestor;// } const execute_shifts = (v) => { let change = 0 let shift = 0 // 从后往前遍历子节点 for(let i = v.children.length - 1; i >= 0; i--) { let node = v.children[i] node.x = shift node.mod = shift change = node.change// change一般为负值 shift = node.shift change// 越往左，节点添加的shift值越小 } } const move_subtree = (leftV, v, shift) => { let subTrees = v.number - leftV.number// 索引相减，得到节点之间被分隔的数量 let average = shift / subTrees// 平分偏移量 v.shift = shift// 完整的shift值添加到v节点的shift属性上 v.change -= average// v左边的节点从右往左要添加的偏移量是递减的，所以是加上负的average leftV.change = average// v.change减了average，为了不影响leftV左侧的节点，这里需要恢复 // ... };

接下来以下图为例来看一下这个过程，假设P节点最终计算出来的shift = 3，那么P.number - G.number = 4 - 1 = 3，中间节点分摊的值3 / 3 = 1，节点G到P之间的节点要距离相等的话，H需要向右移动1，H2要移动1 1，这样它们的坐标为1,3,5,7，等差数列，间距相等，如果还有更多节点，以此类推，因为越右边的节点移动了本身的1后，还被前面的n个节点向右推了n * 1，我们把这两个值保存到节点G和P上：

image.png

然后执行execute_shifts方法从后往前遍历Q的子节点：

1.change=0，shift=0，首先更新最后一个节点P2：P2.x和P2.mod加上shift，即加0，更新change：change P2.change = 0 0 = 0，更新shift：shift P2.shift change = 0 0 0 = 0

2.更新P节点：P.x和P.mod加上shift，即加0，更新change：change P.change = 0 (-1) = -1，更新shift：shift P.shift change = 0 3 (-1) = 2

3.更新H2节点：H2.x和H2.mod加上shift，即加2，更新change：change H2.change = -1 0 = -1，更新shift：shift H2.shift change = 2 0 (-1) = 1

4.更新H节点：H.x和H.mod加上shift，即加1，更新change：change H.change = -1 0 = -1，更新shift：shift H.shift change = 1 0 (-1) = 0

5.更新G节点：G.x和G.mod加上shift，即加0，更新change：change G.change = -1 1 = 0，更新shift：shift G.shift change = 0 0 0 = 0

6.更新G0节点：G0.x和G0.mod加上shift，即加0，更新change：change G0.change = 0 0 = 0，更新shift：shift G0.shift change = 0 0 0 = 0

以上就是译者马后炮式的理解，最终效果：

image.png

x和y交换一下：

image.png

实现思维导图

上述算法还是不能直接应用于思维导图的，因为前面考虑的树每个节点的大小都是一样的，而思维导图每个节点的宽高都是有可能不同的，需要在上述算法的基础上进行一定修改，因为本文已经很长了，所以就不细说了，在线示例https://wanglin2.github.io/tree_layout_demo/，完整代码在https://github.com/wanglin2/tree_layout.

image.png

参考链接

1.原生javascript实现树布局算法

2.树型界面绘制算法（二）简单明了的First-Second

3.树型界面绘制算法（三） 磨人的apportion

4.树形界面绘制算法（小结）

5.A Node-positioning Algorithm for General Trees

,