ps.本文是对llimllib.github.io/pymag-trees…文章的翻译，原文使用的是python语言，译者改用JavaScript实现，并在文章的最后加上了译者详细的解析，有思维导图等树形结构绘制需求的朋友千万别错过。
当我需要为我的项目绘制一些树的时候，我觉得肯定会有一种经典又简单的算法，但最终我发现了一些有意思的事情：树的布局不仅仅是一个NP完全问题，在树的绘制算法背后有一段漫长而有趣的历史。接下来，我会逐一介绍历史中出现的树绘制算法，尝试其中的每一种，并最终实现一个完全
O(n)复杂度的树绘制算法。
问题是什么？
给我们一棵树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) } }
如上图所示，这个算法生成的树满足原则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) }) }
尽管这个算法生成的树满足我们所有的原则，但是你可能也会同意实际绘制出来是很丑的，即使是在上图这样一个简单的树中，也很难快速的确定树节点之间的关系，而且整个树看着似乎都被挤在一起了。现在是时候引入下一个原则了，它会帮助优化Knuth树和最小宽度树：
原则4：父节点应该位于子节点中间
到目前为止，我们能使用非常简单的算法去绘制树是因为我们没有真正的考虑每个节点自身，我们依赖全局的计数器来防止节点重叠，为了满足父节点位于子节点中间的原则，我们需要考虑每个节点的自身上下文状态，那么需要一些新的策略。
Wetherell和Shannon介绍的第一个策略是通过树的后序遍历从底部开始构建树，而不是像代码2那样从上到下，或者像代码3一样从中间穿过，只要你以这种方式看待这棵树，那么让父节点居中是一个很简单的操作，只要把它子节点的x坐标分成两半。
但是我们必须记住，在构建树的右侧时，要注意树的左侧，如上图所示，树的右侧被推到右边为了容纳左侧，为了实现这一分离，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坐标上
这个算法很简单，但是要执行它，我们需要引入一些复杂性。
轮廓
树的轮廓是指树的一边最大或最小的坐标组成的列表，如上图，有两棵树，它们重叠在一起，如果我们沿着左边树的左边，取每层的最小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为此引入了一个令人困惑的概念，叫做线程，它们与用于并行执行的线程意义完全不同。
线程是一种方法，它通过在轮廓上的节点之间创建链接（如果其中一个节点已经不是另一个节点的子节点）来减少扫描子树轮廓所需要的时间，如上图所示，虚线表示一个线程，而实线表示父子关系。
我们也可以利用这个事实，如果一棵树比另一棵树深，我们只需要往下走到较矮的那棵树。任何更深的内容都不需要这两棵树再进行分离，因为它们之间不可能会有冲突。
使用线程以及遍历到较矮的树，我们可以得到一个树的轮廓，并使用下面的代码在线性的时间复杂度内设置线程。
// 代码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坐标
- 否则，遍历它的子节点，将其子节点放置在尽可能靠近其左边兄弟节点的位置
- 将父节点放置在其最左边和最右边子节点的中间
这个算法可以工作，并且很快，但是会有一个问题，它把节点的所有子树都尽可能填到左边，如果最右边的节点与最左边的节点发生冲突，那么中间的树都将被填充到右边。让我们采用绘制树的最后一个原则来解决这个问题：
原则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)的树绘制算法：
// 树节点类 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(); } } // 第一次递归 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 { // default_ancestor默认为第一个子节点 let default_ancestor = v.children[0]; v.children.forEach((child) => { firstwalk(child); default_ancestor = apportion(child, default_ancestor, distance); }); execute_shifts(v); // 子节点的中点 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; }; // 修正子孙节点定位 const apportion = (v, default_ancestor, distance) => { let leftBrother = v.left_brother(); if (leftBrother) { // 四个节点指针 let vInnerRight = v;// 右子树左轮廓 let vOuterRight = v;// 右子树右轮廓 let vInnerLeft = leftBrother;// 当前节点的左兄弟节点，左子树右轮廓 let vOuterLeft = v.leftmost_sibling;// 当前节点的最左侧的兄弟节点，左子树左轮廓 // 四个累加mod值的变量 let sInnerRight = v.mod; let sOuterRight = v.mod; let sInnerLeft = vInnerLeft.mod; let sOuterLeft = vOuterLeft.mod; while (vInnerLeft.right() && vInnerRight.left()) { vInnerLeft = vInnerLeft.right(); vInnerRight = vInnerRight.left(); vOuterLeft = vOuterLeft.left(); vOuterRight = vOuterRight.right(); vOuterRight.ancestor = v; let shift = vInnerLeft.x + sInnerLeft - (vInnerRight.x + sInnerRight) + distance; if (shift > 0) { let _ancestor = ancestor(vInnerLeft, v, default_ancestor); move_subtree(_ancestor, v, shift); sInnerRight = sInnerRight + shift; sOuterRight = sOuterRight + shift; } sInnerLeft += vInnerLeft.mod; sInnerRight += vInnerRight.mod; sOuterLeft += vOuterLeft.mod; sOuterRight += vOuterRight.mod; } // 将线程从浅的树的外侧设置到深的树的内侧 if (vInnerLeft.right() && !vOuterRight.right()) { vOuterRight.thread = vInnerLeft.right(); vOuterRight.mod += sInnerLeft - sOuterRight; } else { if (vInnerRight.left() && !vOuterLeft.left()) { vOuterLeft.thread = vInnerRight.left(); vOuterLeft.mod += sInnerRight - sOuterLeft; } default_ancestor = v; } } return default_ancestor; }; const move_subtree = (wl, wr, shift) => { // 两棵冲突的树的间隔被之间的树分成多少分 let subtrees = wr.number - wl.number; wr.change -= shift / subtrees; wr.shift += shift; wl.change += shift / subtrees; // 自身移动 wr.x += shift; // 后代节点移动 wr.mod += shift; }; const execute_shifts = (v) => { let shift = 0; let change = 0; for (let i = v.children.length - 1; i >= 0; i--) { let w = v.children[i]; w.x += shift; w.mod += shift; change += w.change; shift += w.shift + change; } }; // 如果vil节点的祖先节点在v节点的兄弟节点中，那么返回vil的祖先节点，否则返回default_ancestor const ancestor = (vInnerLeft, v, default_ancestor) => { if (v.parent.children.includes(vInnerLeft.ancestor)) { return vInnerLeft.ancestor; } else { return default_ancestor; } }; // 第二次遍历 const second_walk = (v, m = 0, depth = 0, min = null) => { // 初始x值加上所有祖宗节点的mod修正值 v.x += m; v.y = depth; if (min === null || v.x < min) { min = v.x; } v.children.forEach((child) => { min = second_walk(child, m + v.mod, depth + 1, min); }); return min; }; const third_walk = (tree, n) => { tree.x += n; tree.children.forEach((child) => { third_walk(child, n); }); }; const buchheim = (tree) => { let dt = firstwalk(tree); let min = second_walk(dt); if (min < 0) { third_walk(dt, -min); } return dt; };
总结
在本文中，我略去了一些东西，因为我觉得为了最终算法尝试并呈现一个逻辑进展更重要，而不是用纯代码重载文章。如果你想要查看更多细节，或者想知道在各个代码清单中使用的树的数据结构，你可以去github.com/llimllib/py…这个仓库下载每个算法的源代码、一些基本的测试、以及用于生成本文的树图片的代码。
引用
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). www.emis.de/journals/JG…
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. citeseerx.ist.psu.edu/viewdoc/dow…
