大一棵樹的畫法（繪制一棵漂亮的樹）

發布時間：2024-09-16閱讀(17)

導讀ps.本文是對https://llimllib.github.io/pymag-trees/文章的翻譯，原文使用的是python語言，譯者改用JavaScr....

ps.本文是對https://llimllib.github.io/pymag-trees/文章的翻譯，原文使用的是python語言，譯者改用JavaScript實現，并在文章的最后加上了譯者詳細的解析，有思維導圖等樹形結構繪制需求的朋友千萬別錯過。

當我需要為我的項目繪制一些樹的時候，我覺得肯定會有一種經典又簡單的算法，但最終我發現了一些有意思的事情：樹的布局不僅僅是一個NP完全問題，在樹的繪制算法背后有一段漫長而有趣的歷史。接下來，我會逐一介紹歷史中出現的樹繪制算法，嘗試其中的每一種，并最終實現一個完全O(n)復雜度的樹繪制算法。

問題是什么？

img

給我們一棵樹T，我們要做的就是試著把它畫出來，讓別人一眼就能理解它，本篇文章中的每個算法都會給樹節點一個(x,y)坐標，所以在算法運行之后它能在屏幕中繪制出來，或者打印出來。

為了存儲樹繪制算法的結果，我們會創建一個DrawTree數據結構來鏡像我們繪制的樹，我們唯一要假設的事情就是每個樹節點都可以迭代其子節點，DrawTree的基本實現如下：

// 代碼1class 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坐標，計數器會隨著節點遞增，代碼如下：

// 代碼2let i = 0const 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年后，他們引入了一些創新技術，首先，他們展示了如何生成滿足前面三個原則的盡可能緊湊的樹，通過后序遍歷，只需要維護同一深度的下一個節點的位置：

// 代碼3const 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坐標，如果它是一個分支，則把它居中在它的子節點之上，然而，如果將分支居中會導致它與樹的另一部分發生沖突，我們就需要正確的把它移動足夠的距離來避免沖突。

當我們把分支移動正確時，我們需要移動它的所有子節點，否則我們將失去我們一直在努力維護的中心父節點，寫一個將分支及其子樹移動正確的函數是很容易的：

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

上面這個函數可以工作，但是存在一個問題，如果我們使用這個函數來向右移動一個子樹，我們將在遞歸（放置樹節點）中進行遞歸（移動樹），這意味著我們的算法效率很低，時間復雜度為O(n2)。

為了解決這個問題，我們將為每個節點添加一個mod屬性，當我們到達一個分支時我們需要正確的移動n個空間，我們會把x坐標加上n，并賦值給mod屬性，然后愉快的繼續執行布局算法，因為我們是自下而上移動，所以不需要擔心樹的底部發生沖突（我們已經證明了它們不會），我們等一會再把它們移動正確。

一旦執行完了第一個樹的遍歷，我們就開始進行第二個遍歷過程，將需要正確移動的分支進行移動，因為我們只遍歷了每個節點一次，并且執行的只是算術運算，我們可以確定它的時間復雜度和第一次一樣，都為O(n)，所以兩次合起來還是O(n)。

下面的代碼演示了父節點居中和使用mod屬性來提高代碼的效率：

// 代碼5class 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連接這兩個樹，我們可以找到左邊樹的右輪廓，以及右邊樹的左輪廓，然后我們就可以輕松的找到我們需要的將右邊的樹推到右邊使它不會和左邊樹重疊的最小值，下面的代碼是一個簡單的實現：

// 代碼7const 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

線程是一種方法，它通過在輪廓上的節點之間創建鏈接（如果其中一個節點已經不是另一個節點的子節點）來減少掃描子樹輪廓所需要的時間，如上圖所示，虛線表示一個線程，而實線表示父子關系。

我們也可以利用這個事實，如果一棵樹比另一棵樹深，我們只需要往下走到較矮的那棵樹。任何更深的內容都不需要這兩棵樹再進行分離，因為它們之間不可能會有沖突。

使用線程以及遍歷到較矮的樹，我們可以得到一個樹的輪廓，并使用下面的代碼在線性的時間復雜度內設置線程。

// 代碼8const 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值之和，這些對于計算輪廓上的每個節點實際的位置來說是必需的，這樣我們就可以檢查它是否與另一側的節點發生沖突：

// 代碼9const 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去讓兩個樹盡可能的靠在一起：,

// 代碼10const 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值設置為更深層次樹的偏移量與它本身的差值。

現在我們就已經有了合適的代碼來找到樹的輪廓，并將兩棵樹盡可能近的放在一起，我們可以很容易的實現上面描述的算法。我將不加注釋地呈現其余的代碼：

// 代碼11const 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 Walkers 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值：

效果如下：

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就更新為指向后一個子節點，因為如果右側有子樹和左側發生沖突，那么一定是和較深的那一棵。

然后我們就可以找出左側樹發生沖突的節點所屬的根節點：

找出了是哪兩棵樹發生沖突后我們就能找到這兩棵樹之間的子樹，然后把shift分攤給它們即可，不過我們還是不能直接遍歷它們進行修正，沒錯，還是為了保持線性時間復雜度，所以只能先把分攤數據保存到這兩棵沖突的樹根節點上，然后等它們的所有兄弟節點都遞歸完成了再一次性設置。

接下來以下圖為例來看一下這個過程，假設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.