ps.本文是對https://llimllib.github.io/pymag-trees/文章的翻譯，原文使用的是python語言，譯者改用JavaScript實現(xiàn)，并在文章的最后加上了譯者詳細的解析，有思維導(dǎo)圖等樹形結(jié)構(gòu)繪制需求的朋友千萬別錯過。
當(dāng)我需要為我的項目繪制一些樹的時候，我覺得肯定會有一種經(jīng)典又簡單的算法，但最終我發(fā)現(xiàn)了一些有意思的事情：樹的布局不僅僅是一個NP完全問題，在樹的繪制算法背后有一段漫長而有趣的歷史。接下來，我會逐一介紹歷史中出現(xiàn)的樹繪制算法，嘗試其中的每一種，并最終實現(xiàn)一個完全O(n)復(fù)雜度的樹繪制算法。
問題是什么？
給我們一棵樹T，我們要做的就是試著把它畫出來，讓別人一眼就能理解它，本篇文章中的每個算法都會給樹節(jié)點一個(x,y)坐標，所以在算法運行之后它能在屏幕中繪制出來，或者打印出來。
為了存儲樹繪制算法的結(jié)果，我們會創(chuàng)建一個DrawTree數(shù)據(jù)結(jié)構(gòu)來鏡像我們繪制的樹，我們唯一要假設(shè)的事情就是每個樹節(jié)點都可以迭代其子節(jié)點，DrawTree的基本實現(xiàn)如下：
// 代碼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)
})
}
}
隨著我們的方法越來越復(fù)雜，DrawTree的復(fù)雜度也會隨之增加，現(xiàn)在來說，它只是把每個節(jié)點的x坐標賦值為-1，y坐標賦值為它在樹中的深度，以及存儲對樹節(jié)點的引用。然后，它會遞歸的為每個節(jié)點創(chuàng)建一個DrawTree，從而構(gòu)建該節(jié)點的子節(jié)點列表。這樣一來，我們就構(gòu)建了一個DrawTree來表示將要繪制的樹，并給每個節(jié)點添加了特定的繪制信息。
隨著我們在本文中實現(xiàn)更好的算法，我們將利用每個人的經(jīng)歷總結(jié)成的原則來幫助我們構(gòu)建下一個更好算法，盡管生成一個“漂亮”的樹形圖是一個品味問題，但是這些原則還是會幫助我們優(yōu)化程序輸出。
故事是從Knuth開始的
我們要畫的是一種根節(jié)點在頂部的特殊類型，它的子節(jié)點在它下面，以此類推，這類圖形，以及這類問題的解決，在很大程度上歸功于Donald Knuth，我們會從他這里得出前兩個原則：
原則1：樹的邊不應(yīng)該交叉
原則2：相同深度的節(jié)點應(yīng)該繪制在同一水平線，這能讓樹的結(jié)構(gòu)更清晰
Knuth的算法簡單快速，但它只適用于二叉樹，以及會生成一些相當(dāng)畸形的圖形，它是一個簡單的樹的中序遍歷，設(shè)置一個全局的計數(shù)變量，用來作為x坐標，計數(shù)器會隨著節(jié)點遞增，代碼如下：
// 代碼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：樹應(yīng)該盡可能畫的緊湊一點
一個簡短的回顧
在我們繼續(xù)學(xué)習(xí)更高級的算法之前，先讓我們停下來了解一些術(shù)語，首先，在描述我們的數(shù)據(jù)節(jié)點之間的關(guān)系時，我們將使用家族樹的比喻，節(jié)點的下面可以有子節(jié)點，左邊或右邊可以有兄弟節(jié)點，以及上面會有父節(jié)點。
我們已經(jīng)討論了樹的中序遍歷，接下來我們還會看到前序遍歷和后序遍歷，你可能在很久以前的“數(shù)據(jù)結(jié)構(gòu)”課程上看到過這三個術(shù)語，但除非你最近一直在和樹打交道，否則你可能已經(jīng)對它們有點模糊了。
遍歷方式只是決定我們在給定的節(jié)點上進行處理的時機，中序遍歷，也就是上面的Knuth算法，只接受一個二叉樹，意味著我們會先處理左子節(jié)點，然后是當(dāng)前節(jié)點，然后是右子節(jié)點，前序遍歷，意味著我們先處理當(dāng)前節(jié)點，然后處理它的所有子節(jié)點，后序遍歷則剛好和它相反。
最后，你可能已經(jīng)了解了大寫的O符號的概念，用來表示算法的時間復(fù)雜度，在本文中，我們會時不時的提起它，用它來作為一個簡單的工具來判斷一個算法在運行時間上能不能被接受。如果一個算法在它的主循環(huán)中頻繁的遍歷它的一個節(jié)點的所有子節(jié)點，我們稱它的時間復(fù)雜度為O(n^2)，其他情況則為O(n)，如果你想了解更多細節(jié)，本文最后引用的論文中包含了大量關(guān)于這些算法時間復(fù)雜度的內(nèi)容。
自下而上
Charles Wetherell和Alfred Shannon這兩個人在1979年出現(xiàn)了，也就是在Knuth提出了樹的布局算法的8年后，他們引入了一些創(chuàng)新技術(shù)，首先，他們展示了如何生成滿足前面三個原則的盡可能緊湊的樹，通過后序遍歷，只需要維護同一深度的下一個節(jié)點的位置：
// 代碼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)
})
}
盡管這個算法生成的樹滿足我們所有的原則，但是你可能也會同意實際繪制出來是很丑的，即使是在上圖這樣一個簡單的樹中，也很難快速的確定樹節(jié)點之間的關(guān)系，而且整個樹看著似乎都被擠在一起了?，F(xiàn)在是時候引入下一個原則了，它會幫助優(yōu)化Knuth樹和最小寬度樹：
原則4：父節(jié)點應(yīng)該位于子節(jié)點中間
到目前為止，我們能使用非常簡單的算法去繪制樹是因為我們沒有真正的考慮每個節(jié)點自身，我們依賴全局的計數(shù)器來防止節(jié)點重疊，為了滿足父節(jié)點位于子節(jié)點中間的原則，我們需要考慮每個節(jié)點的自身上下文狀態(tài)，那么需要一些新的策略。
Wetherell和Shannon介紹的第一個策略是通過樹的后序遍歷從底部開始構(gòu)建樹，而不是像代碼2那樣從上到下，或者像代碼3一樣從中間穿過，只要你以這種方式看待這棵樹，那么讓父節(jié)點居中是一個很簡單的操作，只要把它子節(jié)點的x坐標分成兩半。
但是我們必須記住，在構(gòu)建樹的右側(cè)時，要注意樹的左側(cè)，如上圖所示，樹的右側(cè)被推到右邊為了容納左側(cè)，為了實現(xiàn)這一分離，Wetherell和Shannon在代碼2的基礎(chǔ)上通過數(shù)組維護下一個可用點，但只有在將父樹居中會導(dǎo)致樹的右側(cè)與左側(cè)重疊時，才使用下一個可用的位置。
Mods和Rockers
在我們看更多代碼之前，讓我們仔細看看自下而上構(gòu)建樹的結(jié)果，如果節(jié)點是葉子節(jié)點，我們會給它下一個可用的x坐標，如果它是一個分支，則把它居中在它的子節(jié)點之上，然而，如果將分支居中會導(dǎo)致它與樹的另一部分發(fā)生沖突，我們就需要正確的把它移動足夠的距離來避免沖突。
當(dāng)我們把分支移動正確時，我們需要移動它的所有子節(jié)點，否則我們將失去我們一直在努力維護的中心父節(jié)點，寫一個將分支及其子樹移動正確的函數(shù)是很容易的：
// 代碼4
const move_right = (branch, n) => {
branch.x += n
branch.children.forEach((child) => {
move_right(child, n)
})
}
上面這個函數(shù)可以工作，但是存在一個問題，如果我們使用這個函數(shù)來向右移動一個子樹，我們將在遞歸（放置樹節(jié)點）中進行遞歸（移動樹），這意味著我們的算法效率很低，時間復(fù)雜度為O(n2)。
為了解決這個問題，我們將為每個節(jié)點添加一個mod屬性，當(dāng)我們到達一個分支時我們需要正確的移動n個空間，我們會把x坐標加上n，并賦值給mod屬性，然后愉快的繼續(xù)執(zhí)行布局算法，因為我們是自下而上移動，所以不需要擔(dān)心樹的底部發(fā)生沖突（我們已經(jīng)證明了它們不會），我們等一會再把它們移動正確。
一旦執(zhí)行完了第一個樹的遍歷，我們就開始進行第二個遍歷過程，將需要正確移動的分支進行移動，因為我們只遍歷了每個節(jié)點一次，并且執(zhí)行的只是算術(shù)運算，我們可以確定它的時間復(fù)雜度和第一次一樣，都為O(n)，所以兩次合起來還是O(n)。
下面的代碼演示了父節(jié)點居中和使用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塊
雖然在很多情況下它確實產(chǎn)生了不錯的效果，但是代碼5也會產(chǎn)生一些奇怪的樹，就像上圖（抱歉，圖已丟失在歲月的長河中），Wetherell-Shannon算法的另一個理解上的困難是，相同的樹結(jié)構(gòu)，當(dāng)放在樹的不同位置時，可能會繪制出不同的結(jié)構(gòu)。為了解決這個問題，我們會從Edward Reingold和John Tilford的論文中借鑒一個原則：
原則5：同一個子樹無論在樹的哪個位置，繪制的結(jié)果都應(yīng)該相同
盡管這會擴大我們的繪制寬度，但是這個原則會有助于它們傳達更多信息。它還有助于簡化自下而上的遍歷，比如，一旦我們計算出一個子樹的x坐標，我們只需要將它作為一個單位向左或向右移動。
下面是代碼6的算法大致過程：
- 對樹進行后序遍歷
- 如果一個節(jié)點是葉子節(jié)點，那么給它一個值為
0的x坐標 - 否則，在不產(chǎn)生沖突的情況下，將它的右子樹盡可能靠近左子樹
- 使用與前面相同的
mod方式，在O(n)時間內(nèi)移動樹
- 使用與前面相同的
- 將節(jié)點放置在其子節(jié)點中間
- 再遍歷一次樹，將累積的
mode值加到x坐標上
這個算法很簡單，但是要執(zhí)行它，我們需要引入一些復(fù)雜性。
輪廓
樹的輪廓是指樹的一邊最大或最小的坐標組成的列表，如上圖，有兩棵樹，它們重疊在一起，如果我們沿著左邊樹的左邊，取每層的最小x坐標，我們可以得到[1, 1, 0]，我們把它叫做樹的左輪廓，如果我們沿著右邊，取每一層最右邊的x坐標，可以得到[1, 1, 2]，也就是樹的右輪廓。
為了找出右邊樹的左輪廓，我們同樣取每一層最左邊節(jié)點的x坐標，可以得到[1, 0, 1]，此時，可以看到輪廓有一個有趣的特性，就是并非所有節(jié)點都以父子關(guān)系連接，第二層的0不是第三層的1的父節(jié)點。
如果我要根據(jù)代碼6連接這兩個樹，我們可以找到左邊樹的右輪廓，以及右邊樹的左輪廓，然后我們就可以輕松的找到我們需要的將右邊的樹推到右邊使它不會和左邊樹重疊的最小值，下面的代碼是一個簡單的實現(xiàn)：
// 代碼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) => {
// 根節(jié)點只有一個，所以直接添加
if (cont === null) {
cont = [tree.x]
} else if (cont.length < level + 1) {// 該層級尚未添加，直接添加
cont.push(tree.x)
} else if (comp(cont[level], tree.x)) {// 該層級已經(jīng)有值，所以進行比較
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，我們可以正確的找到需要把右邊樹推多遠的值，但是為了做到這個，我們需要掃描兩個子樹的每個節(jié)點去得到我們需要的輪廓，因為它需要的時間復(fù)雜度很可能是O(n^2)，Reingold和Tilford為此引入了一個令人困惑的概念，叫做線程，它們與用于并行執(zhí)行的線程意義完全不同。
線程是一種方法，它通過在輪廓上的節(jié)點之間創(chuàng)建鏈接（如果其中一個節(jié)點已經(jīng)不是另一個節(jié)點的子節(jié)點）來減少掃描子樹輪廓所需要的時間，如上圖所示，虛線表示一個線程，而實線表示父子關(guān)系。
我們也可以利用這個事實，如果一棵樹比另一棵樹深，我們只需要往下走到較矮的那棵樹。任何更深的內(nèi)容都不需要這兩棵樹再進行分離，因為它們之間不可能會有沖突。
使用線程以及遍歷到較矮的樹，我們可以得到一個樹的輪廓，并使用下面的代碼在線性的時間復(fù)雜度內(nèi)設(shè)置線程。
// 代碼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
}
很明顯可以看到，這個過程只訪問被掃描的子樹中每一層的兩個節(jié)點。
把它們組合起來
代碼8計算輪廓的過程簡潔且快速，但它不能和我們更早的時候討論的mod方式一起工作，因為一個節(jié)點實際的x坐標是該節(jié)點的x值加上從它到根節(jié)點路徑上的所有mod值之和。為了解決這個問題，我們需要給輪廓算法增加一些復(fù)雜度。
我們要做的第一件事就是需要維護兩個額外的變量，左子樹上的mod值之和以及右子樹的mod值之和，這些對于計算輪廓上的每個節(jié)點實際的位置來說是必需的，這樣我們就可以檢查它是否與另一側(cè)的節(jié)點發(fā)生沖突：
// 代碼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]
}
我們要做的另外一件事是在退出的時候返回函數(shù)的當(dāng)前狀態(tài)，這樣我們就可以在線程節(jié)點上設(shè)置適當(dāng)?shù)钠屏?。有了這些信息，我們就可以看看這個函數(shù)，它使用代碼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，這樣他們就不會發(fā)生沖突，如果中間點是奇數(shù)，那么就再加1，這讓我們測試更方便 - 所有的節(jié)點都有整數(shù)x坐標，不會損失精度。
然后我們將右邊的樹向右移動相應(yīng)的距離，請記住，我們在x坐標上加上diff并且也把diff保存到mod屬性上的原因是mod值只用于當(dāng)前節(jié)點下面的節(jié)點。如果右子樹有超過一個子節(jié)點，我們將差異添加到roffset，因為右節(jié)點的所有子節(jié)點都要向右移動那么遠。
如果樹的左邊比右邊深，或反過來，我們需要設(shè)置一個線程。我們只是檢查一側(cè)的節(jié)點指針是否比另一側(cè)的節(jié)點指針前進得更遠，如果是的話，將線程從淺的樹的外側(cè)設(shè)置到深的樹的內(nèi)側(cè)。
為了正確處理我們之前提到的mod值，我們需要在線程節(jié)點上設(shè)置一個特殊的mod值，因為我們已經(jīng)更新了我們右側(cè)偏移值來反應(yīng)右側(cè)樹的移動量，我們需要做的就是將線程節(jié)點的mod值設(shè)置為更深層次樹的偏移量與它本身的差值。
現(xiàn)在我們就已經(jīng)有了合適的代碼來找到樹的輪廓，并將兩棵樹盡可能近的放在一起，我們可以很容易的實現(xiàn)上面描述的算法。我將不加注釋地呈現(xiàn)其余的代碼：
// 代碼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叉樹
現(xiàn)在我們終于得到一個畫二叉樹的算法，并且滿足我們所有的原則，在大部分情況下看起來都不錯，并且為線性時間復(fù)雜度，那么很自然的就會想到如何把它擴展為支持任意多個子節(jié)點的樹。如果你一直看到這里，你可能會想，我們是不是只需要把剛定義的美妙的算法應(yīng)用到節(jié)點的所有子節(jié)點上即可。
擴展前面的算法使之能在多叉樹上工作：
- 對樹進行后序遍歷
- 如果節(jié)點是葉子節(jié)點，那么給它一個值為
0的x坐標 - 否則，遍歷它的子節(jié)點，將其子節(jié)點放置在盡可能靠近其左邊兄弟節(jié)點的位置
- 將父節(jié)點放置在其最左邊和最右邊子節(jié)點的中間
這個算法可以工作，并且很快，但是會有一個問題，它把節(jié)點的所有子樹都盡可能填到左邊，如果最右邊的節(jié)點與最左邊的節(jié)點發(fā)生沖突，那么中間的樹都將被填充到右邊。讓我們采用繪制樹的最后一個原則來解決這個問題：
原則6：同一個父節(jié)點的子節(jié)點應(yīng)該間隔均勻
為了對稱且快速地畫出N叉樹，我們需要用到目前為止我們學(xué)到的所有技巧，并且還要再加上一些新技巧，這要感謝Christoph Buchheim等人最近發(fā)表的一篇論文，我們已經(jīng)有了所有的知識儲備來做這些并且仍然能夠在線性時間內(nèi)完成。
對上述算法進行修改，使其滿足原則6，我們需要一個方法來分隔兩棵沖突的大樹之間的樹，最簡單的方法是，每當(dāng)兩棵樹發(fā)生沖突時，將可用空間除以樹的數(shù)量，然后移動每棵樹，使它的和它相鄰的樹分隔那個距離。舉個例子，在上圖，右邊和左邊的大樹之間存在一個距離n，在它們之間存在3棵樹，如果我們把第一棵樹和最左邊的間隔n/3距離，下一個又和這個間隔n/3，以此類推，就會得到滿足原則6的樹。
到目前為止，我們在本文中看到的每一個簡單的算法，我們都會發(fā)現(xiàn)它的不足之處，這個也不例外，如果我們必須在每兩棵有沖突的樹之間移動所有的樹，我們又會在算法中引入一個O(n^2)復(fù)雜度的運算。
這個問題的解決方式和前面我們解決移位問題類似，我們引入mod，而不是每次有沖突時都在中間移動每個子樹，我們把我們在中間需要移動的樹的值保存起來，在放置完所有節(jié)點后再應(yīng)用。
為了正確的求出我們需要移動中間節(jié)點的距離，我們需要能夠找到兩個沖突節(jié)點之間的樹的數(shù)量，當(dāng)我們只有兩棵樹時，很明顯，所有的沖突都發(fā)生在左樹和右樹之間，當(dāng)有任意棵樹時，找出是哪棵樹引起了沖突就成為了一個挑戰(zhàn)。
為了應(yīng)對這個挑戰(zhàn)，我們將引入一個默認的祖先變量，并向樹的數(shù)據(jù)結(jié)構(gòu)中添加另一個成員，我們稱之為ancestor，ancestor要么指向自身，要么指向它所屬樹的根，當(dāng)我們需要找到一個節(jié)點屬于哪一棵樹的時候，如果這個屬性設(shè)置了就使用它，否則使用default_ancestor。
當(dāng)我們放置一個節(jié)點的第一個子樹，我們把default_ancestor指向這個子樹，假設(shè)如果下一棵樹發(fā)生了沖突，那么一定是與第一棵樹發(fā)生的，當(dāng)我們放置好了第二棵樹后，我們區(qū)分兩種情況，如果第二棵子樹沒有第一棵深，我們遍歷它的右輪廓，將ancestor屬性設(shè)置為第二棵樹的根，否則，第二棵樹就是比第一棵樹深，這意味著與下一棵樹沖突的任何內(nèi)容都將被放置在第二棵樹中，因此我們只需設(shè)置default_ancestor來指向它。
話不多說，我們來看看由Buchheim提出的一個時間復(fù)雜度為O(n)的樹繪制算法：
請看下下下節(jié): ）
總結(jié)
在本文中，我略去了一些東西，因為我覺得為了最終算法嘗試并呈現(xiàn)一個邏輯進展更重要，而不是用純代碼重載文章。如果你想要查看更多細節(jié)，或者想知道在各個代碼清單中使用的樹的數(shù)據(jù)結(jié)構(gòu)，你可以去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
譯者的個人發(fā)揮
算法詳細分解
雖然作者已經(jīng)花了這么大篇幅來引出最后的算法，但是直接放出來，大概率還是看不懂的，所以譯者嘗試分解一下，想直接看原版的可以點此listing12.py。
節(jié)點類如下，請務(wù)必仔細看一下right()和left()方法：
// 樹節(jié)點類
class DrawTree {
constructor(tree, parent = null, depth = 0, number = 1) {
// 節(jié)點名稱
this.name = tree.name;
// 坐標
this.x = -1;
this.y = depth;
// 子節(jié)點
this.children = tree.children.map((child, index) => {
return new DrawTree(child, this, depth + 1, index + 1);
});
// 父節(jié)點
this.parent = parent;
// 線程節(jié)點，也就是指向下一個輪廓節(jié)點
this.thread = null;
// 根據(jù)左兄弟定位的x與根據(jù)子節(jié)點中間定位的x之差
this.mod = 0;
// 要么指向自身，要么指向所屬樹的根
this.ancestor = this;
// 記錄分攤偏移量
this.change = this.shift = 0;
// 最左側(cè)的兄弟節(jié)點
this._lmost_sibling = null;
// 這是它在兄弟節(jié)點中的位置索引 1...n
this.number = number;
}
// 關(guān)聯(lián)了線程則返回線程節(jié)點，否則返回最右側(cè)的子節(jié)點，也就是樹的右輪廓的下一個節(jié)點
right() {
return (
this.thread ||
(this.children.length > 0
? this.children[this.children.length - 1]
: null)
);
}
// 關(guān)聯(lián)了線程則返回線程節(jié)點，否則返回最左側(cè)的子節(jié)點，也就是樹的左輪廓的下一個節(jié)點
left() {
return (
this.thread || (this.children.length > 0 ? this.children[0] : null)
);
}
// 獲取前一個兄弟節(jié)點
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;
}
// 獲取同一層級第一個兄弟節(jié)點，如果第一個是自身，那么返回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;
}
// 同一層級第一個兄弟節(jié)點
get leftmost_sibling() {
return this.get_lmost_sibling();
}
}
進入第一次遞歸，處理如下：
1.當(dāng)前節(jié)點是葉子節(jié)點且無左兄弟，x設(shè)為0
2.當(dāng)前節(jié)點是葉子節(jié)點且有左兄弟，x為左兄弟的x加上間距，即根據(jù)左兄弟定位
3.當(dāng)前節(jié)點非葉子節(jié)點且無左兄弟，x為第一個子節(jié)點的x加上最后一個子節(jié)點的x除以2，即根據(jù)子節(jié)點定位
4.當(dāng)前節(jié)點非葉子節(jié)點且有左兄弟，x為左兄弟的x加上間距，mod設(shè)為x相對子節(jié)點定位的差值
// 第一次遞歸
const firstwalk = (v, distance = 1) => {
if (v.children.length === 0) {
// 當(dāng)前節(jié)點是葉子節(jié)點且存在左兄弟節(jié)點，則其x坐標等于其左兄弟的x坐標加上間距distance
if (v.leftmost_sibling) {
v.x = v.left_brother().x + distance;
} else {
// 當(dāng)前節(jié)點是葉節(jié)點無左兄弟，那么x坐標為0
v.x = 0;
}
} else {
// 后序遍歷，先遞歸子節(jié)點
v.children.forEach((child) => {
firstwalk(child);
});
// 子節(jié)點的中點
let midpoint =
(v.children[0].x + v.children[v.children.length - 1].x) / 2;
// 左兄弟
let w = v.left_brother();
if (w) {
// 有左兄弟節(jié)點，x坐標設(shè)為其左兄弟的x坐標加上間距distance
v.x = w.x + distance;
// 同時記錄下偏移量（x坐標與子節(jié)點的中點之差）
v.mod = v.x - midpoint;
} else {
// 沒有左兄弟節(jié)點，x坐標直接是子節(jié)點的中點
v.x = midpoint;
}
}
return v;
};
第二次遞歸將mod值加到x上，使父節(jié)點仍舊居中于子節(jié)點：
// 第二次遍歷
const second_walk = (v, m = 0, depth = 0) => {
// 初始x值加上所有祖宗節(jié)點的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;
};
第一次遞歸后的節(jié)點位置：
第二次遞歸后的節(jié)點位置：
明顯存在沖突的子樹可以看到是G和P兩棵子樹，子樹P需要向右移動一定的距離才行，這個距離怎么算呢？
1.進入子樹
G和P的第二層，找到子樹G在這一層中的最右側(cè)子節(jié)點，為F，找到子樹P在這一層的最左側(cè)子節(jié)點，為I，比較它們的x坐標，原始x值加上它們祖先節(jié)點的mod值之和，比較后發(fā)現(xiàn)沒有交叉，于是進入下一層。2.進入第三層，同樣找到子樹
G在這一層中的最右側(cè)子節(jié)點，為E，子樹P在這一層的最左側(cè)子節(jié)點，為J，比較它們的x，發(fā)現(xiàn)存在交叉，這個差值再加上節(jié)點的間隔distance就是子樹P需要向右移動的距離3.重復(fù)以上，直到最底層。
那么怎么最快速的找到每一層的最左側(cè)或最右側(cè)節(jié)點呢，當(dāng)然可以直接遞歸，但是時間復(fù)雜度就非線性了，所以就引入了前面所說的線程的概念。
以上圖中的G節(jié)點為例介紹線程的連接過程，從它的子節(jié)點C回來后因為C沒有左兄弟，所以不處理，進入F節(jié)點遞歸，從F節(jié)點回來之后緊接著處理F節(jié)點，它存在左兄弟C，因為每棵樹都有內(nèi)側(cè)和外側(cè)，所以我們設(shè)置四個指針：
vInnerLeft為當(dāng)前節(jié)點的左兄弟節(jié)點，vOuterLeft為當(dāng)前節(jié)點的最左側(cè)的兄弟節(jié)點，當(dāng)然對于F節(jié)點來說，這兩個指針都指向C節(jié)點，vInnerRight和vOuterRight初始都指向當(dāng)前節(jié)點。
接下來我們就將線程從淺的樹的外側(cè)設(shè)置到深的樹的內(nèi)側(cè)：
1.因為C和F節(jié)點都存在子節(jié)點，所以這一層還無法判斷哪棵樹深哪棵樹淺，所以就下移一層，同時更新四個指針，這里就會用到節(jié)點的left()或right()方法：
這里存在四個指針，怎么判斷是否還有下一層呢，因為我們要檢查節(jié)點沖突是根據(jù)兩棵樹的內(nèi)側(cè)節(jié)點進行比較，所以這里也只需要檢查兩個內(nèi)側(cè)節(jié)點指針來判斷是否還有下一層，我們只需走到較淺的樹即可停止，另一棵樹更深的節(jié)點不會發(fā)生沖突，所以判斷vInnerLeft.right()和vInnerRight.left()是否都存在即可。
2.下移一層后發(fā)現(xiàn)已經(jīng)達到F的葉子節(jié)點了，那么接下來就進行判斷，重復(fù)一下我們的原則：
將線程從淺的樹的外側(cè)設(shè)置到深的樹的內(nèi)側(cè)
淺的樹為F子樹，深的樹為C子樹，那么從F的外側(cè)設(shè)置到C的內(nèi)側(cè)，也就是要將E節(jié)點和A節(jié)點通過線程連接起來。
具體的判斷規(guī)則為：
2.1.如果
vInnerLeft.right()節(jié)點（也就是B節(jié)點所在樹的右側(cè)輪廓的下一個節(jié)點，這里是存在的，為A節(jié)點）存在，且vOuterRight.right()節(jié)點（也就是E節(jié)點所在樹的右側(cè)輪廓的下一個節(jié)點，這里是不存在的）不存在，那么就在vOuterRight節(jié)點上設(shè)置線程thread屬性指向vInnerLeft.right()節(jié)點，這里剛好滿足這個條件，所以E.thread指向了A節(jié)點。2.2.否則如果
vOuterLeft.left()節(jié)點（也就是B節(jié)點所在樹的左輪廓的下一個節(jié)點，這里是存在的，為A節(jié)點）不存在，且vInnerRight.left()節(jié)點（也就是D節(jié)點所在樹的左輪廓的下一個節(jié)點，這里是不存在的）存在，那么就在vOuterLeft節(jié)點上設(shè)置線程thread屬性指向vInnerRight.left()節(jié)點，顯然這里不滿足條件。
對于其他所有節(jié)點，都用這種方法判斷，最終這棵樹上線程節(jié)點連接為：
因為我們是后序遍歷樹，所以越下層的節(jié)點線程連接的越早，比如處理O節(jié)點時候就會把I和J節(jié)點連接起來了，那么在后面處理P節(jié)點時，雖然也走到了I節(jié)點，但是I節(jié)點因為有了線程節(jié)點，所以一定程度上它就不是“葉子節(jié)點”了，所以I不會再被連接到其他節(jié)點上。
// 第一次遞歸
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) {
// 四個節(jié)點指針
let vInnerRight = v;// 右子樹左輪廓
let vOuterRight = v;// 右子樹右輪廓
let vInnerLeft = leftBrother;// 當(dāng)前節(jié)點的左兄弟節(jié)點，左子樹右輪廓
let vOuterLeft = v.leftmost_sibling;// 當(dāng)前節(jié)點的最左側(cè)的兄弟節(jié)點，左子樹左輪廓
// 一直遍歷到葉子節(jié)點
while(vInnerLeft.right() && vInnerRight.left()) {
// 更新指針
vInnerLeft = vInnerLeft.right()
vInnerRight = vInnerRight.left()
vOuterLeft = vOuterLeft.left()
vOuterRight = vOuterRight.right()
}
// 將線程從淺的樹的外側(cè)設(shè)置到深的樹的內(nèi)側(cè)
if (vInnerLeft.right() && !vOuterRight.right()) {
vOuterRight.thread = vInnerLeft.right();
} else {
if (vInnerRight.left() && !vOuterLeft.left()) {
vOuterLeft.thread = vInnerRight.left();
}
}
}
};
線程節(jié)點連接好了，接下來就可以根據(jù)輪廓判斷兩棵樹是否存在交叉，同樣因為我們是后序遍歷，所以判斷某個子樹是否存在沖突時它下面的節(jié)點線程肯定已經(jīng)連接完成了，可以直接使用。
根據(jù)輪廓判斷的邏輯同樣也放在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) {
// ...
// 從當(dāng)前節(jié)點依次往下走，判斷是否和左側(cè)的子樹發(fā)生沖突
while(vInnerLeft.right() && vInnerRight.left()) {
// ...
// 左側(cè)節(jié)點減右側(cè)節(jié)點
let shift = vInnerLeft.x + distance - vInnerRight.x
if (shift > 0) {
// 大于0說明存在交叉，那么右側(cè)的樹要向右移動
move_subtree(v, shift)
}
}
// ...
}
}
// 移動子樹
const move_subtree = (v, shift) => {
v.x += shift// 自身移動
v.mod += shift// 后代節(jié)點移動
}
以節(jié)點P為例，過程如下：
vInnerLeft.right()存在（H.right()=F），vInnerRight.left()存在（P.left()=I），所以下移一層：
比較F和I節(jié)點的x坐標之差可以發(fā)現(xiàn)它們不存在沖突，于是繼續(xù)下一層：
這一次比較會發(fā)現(xiàn)E和J節(jié)點發(fā)生沖突，那么子樹P需要整體向右移動一定距離。
當(dāng)然，上述代碼是有問題的，因為一個節(jié)點真正的最終x坐標是還要加上它所有祖宗節(jié)點的mod值，所以我們新增四個變量來累加mod值：
const apportion = (v, distance) => {
if (leftBrother) {
// 四個節(jié)點指針
// ...
// 累加mod值，它們的父節(jié)點是同一個，所以往上它們要加的mod值也是一樣的，那么在后面shift值計算時vInnerLeft.x + 父節(jié)點.mod - (vInnerRight.x + 父節(jié)點.mod)，父節(jié)點.mod可以直接消掉，所以不加上面的祖先節(jié)點的mod也沒關(guān)系
let sInnerRight = vInnerRight.mod;
let sOuterRight = vOuterRight.mod;
let sInnerLeft = vInnerLeft.mod;
let sOuterLeft = vOuterLeft.mod;
// 從當(dāng)前節(jié)點依次往下走，判斷是否和左側(cè)的子樹發(fā)生沖突
while (vInnerLeft.right() && vInnerRight.left()) {
// ...
// 左側(cè)節(jié)點減右側(cè)節(jié)點，需要累加上mod值
let shift = vInnerLeft.x + sInnerLeft + distance - (vInnerRight.x + sInnerRight);
if (shift > 0) {
// ...
// v.mod，也就是節(jié)點P.mod增加了shift，sInnerRight、sOuterRight當(dāng)然也要同步增加
sInnerRight += shift;
sOuterRight += shift;
}
// 累加當(dāng)前層節(jié)點mod
sInnerRight += vInnerRight.mod;
sOuterRight += vOuterRight.mod;
sInnerLeft += vInnerLeft.mod;
sOuterLeft += vOuterLeft.mod;
}
// ...
}
};
效果如下：
但是這樣依然是有問題的，為啥呢，比如對于節(jié)點E來說，它累加上了節(jié)點F、H的mod值，但問題是H節(jié)點并不是E節(jié)點的祖先，它們只是通過一根線程虛線產(chǎn)生了連接而已，實際要加上的應(yīng)該是節(jié)點F、G的mod值才對，這咋辦呢，還是以例子來看，我們假設(shè)部分節(jié)點的mod值如下：
那么對于節(jié)點A真正要累加的mod值應(yīng)該為：
B.mod + C.mod + G.mod = 1 + 2 + 3 = 6
但是因為線程連接，實際累加的mod值變成了：
E.mod + F.mod + H.mod = 0 + 4 + 0 = 4
少了2，如果能在線程節(jié)點E和H上設(shè)置一個特殊的mod值上，來彌補上這相差的值豈不美哉，反正因為它們兩個下面也沒有子節(jié)點了，所以無論給它們設(shè)置什么mod值都不會有影響。那么這個特殊的mod值又怎么計算呢？很簡單，比如在第一次處理F節(jié)點時，它存在左節(jié)點C，所以進行它們下面的節(jié)點的線程連接判斷，因為它們都存在子級，所以下移一層，此時F子樹到頭了，C子樹沒有，此時滿足vInnerLeft.right() && !vOuterRight.right()的條件，會把E連接到A，對于C和F來說，它們的祖先節(jié)點都是一樣的，所以祖先節(jié)點的mod值不用管，那么對于A節(jié)點來說，它真正要累加的mod值為B.mod + C.mod，而根據(jù)線程連接它會加上的mod值為E.mod + F.mod，兩個式子的運算結(jié)果要相同，那么求E.mod顯然等于B.mod + C.mod - F.mod，也就是sInnerLeft - sOuterRight，修改代碼如下：
// 將線程從淺的樹的外側(cè)設(shè)置到深的樹的內(nèi)側(cè)
if (vInnerLeft.right() && !vOuterRight.right()) {
vOuterRight.thread = vInnerLeft.right();
// 修正因為線程影響導(dǎo)致mod累加出錯的問題，深的樹減淺的樹
vOuterRight.mod += sInnerLeft - sOuterRight// ++
} else {
if (vInnerRight.left() && !vOuterLeft.left()) {
vOuterLeft.thread = vInnerRight.left();
vOuterLeft.mod += sInnerRight - sOuterLeft// ++
}
}
此時效果如下：
到這里沖突是沒有了，但是H的位置應(yīng)該居中才對，顯然是要向右移動，移動多少呢，子樹P向右移動了shift距離，那么這個距離需要平分到G、H、P三個節(jié)點之間的間距上，假設(shè)兩個沖突子樹之間的子樹數(shù)量為n，那么就是shift / (n + 1)，子樹H向右移動這個距離即可。
換言之，我們先要找到是哪兩棵子樹發(fā)生了沖突，才能修正它們之間的樹，上圖可以看到發(fā)生沖突的是E和J節(jié)點，對于J節(jié)點，我們肯定知道它屬于當(dāng)前的頂層子樹P，那么只要能找出E節(jié)點所屬的樹即可，我們可以一眼就看出來是G節(jié)點，但是代碼沒有眼，可以直接通過向上遞歸來找，但是為了線性時間復(fù)雜度我們也不能這么做。
我們給每個節(jié)點都設(shè)置一個ancestor屬性，初始都指向自身，對于E節(jié)點，雖然在沖突判斷時它屬于vInnerLeft節(jié)點，但是在它所屬的樹上，它屬于vOuterRight節(jié)點，所以在線程連接階段，我們可以順便設(shè)置一下每層的vOuterRight節(jié)點的ancestor，讓它指向當(dāng)前的頂層節(jié)點v，但是這個指向有時不一定滿足我們的要求，比如上圖的N節(jié)點，它的ancestor成功的指向了P節(jié)點，但是對于E節(jié)點來說，它的ancestor指向的是它的父節(jié)點F，而我們需要的是G，所以我們再設(shè)置一個變量default_ancestor，當(dāng)一個節(jié)點的ancestor指向不滿足我們的要求時就使用default_ancestor指向的節(jié)點，default_ancestor初始指向一個節(jié)點的第一個子節(jié)點，然后從每個子節(jié)點回來時都更新該指針，如果前一個子節(jié)點沒有后一個子節(jié)點深，那么default_ancestor就更新為指向后一個子節(jié)點，因為如果右側(cè)有子樹和左側(cè)發(fā)生沖突，那么一定是和較深的那一棵。
const firstwalk = (v, distance = 1) => {
if (v.children.length === 0) {
// ...
} else {
let default_ancestor = v.children[0]// ++初始指向第一個子節(jié)點
v.children.forEach((child) => {
firstwalk(child);
default_ancestor = apportion(child, distance, default_ancestor);// 遞歸完每一個子節(jié)點都更新default_ancestor
});
}
}
const apportion = (v, distance, default_ancestor) => {
let leftBrother = v.left_brother();
if (leftBrother) {
// ...
while (vInnerLeft.right() && vInnerRight.left()) {
// ...
// 節(jié)點v下面的每一層右輪廓節(jié)點都關(guān)聯(lián)v
vOuterRight.ancestor = v;// ++
// ...
}
// ...
if (vInnerLeft.right() && !vOuterRight.right()) {
// ...
} else {
// ...
default_ancestor = v// ++，前面的節(jié)點沒有當(dāng)前節(jié)點深，那么default_ancestor指向當(dāng)前節(jié)點
}
}
return default_ancestor;// ++
}
然后我們就可以找出左側(cè)樹發(fā)生沖突的節(jié)點所屬的根節(jié)點：
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節(jié)點所屬的根節(jié)點
let _ancestor = ancestor(vInnerLeft, v, default_ancestor)// ++
move_subtree(v, shift);
// ...
}
// ...
}
// ...
}
return default_ancestor;// ++
}
// 找出節(jié)點所屬的根節(jié)點
const ancestor = (vInnerLeft, v, default_ancestor) => {
// 如果vInnerLeft節(jié)點的ancestor指向的節(jié)點是v節(jié)點的兄弟，那么符合要求
if (v.parent.children.includes(vInnerLeft.ancestor)) {
return vInnerLeft.ancestor;
} else {
// 否則使用default_ancestor指向的節(jié)點
return default_ancestor
}
}
找出了是哪兩棵樹發(fā)生沖突后我們就能找到這兩棵樹之間的子樹，然后把shift分攤給它們即可，不過我們還是不能直接遍歷它們進行修正，沒錯，還是為了保持線性時間復(fù)雜度，所以只能先把分攤數(shù)據(jù)保存到這兩棵沖突的樹根節(jié)點上，然后等它們的所有兄弟節(jié)點都遞歸完成了再一次性設(shè)置。
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分攤添加到中間節(jié)點的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
// 從后往前遍歷子節(jié)點
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// 越往左，節(jié)點添加的shift值越小
}
}
const move_subtree = (leftV, v, shift) => {
let subTrees = v.number - leftV.number// 索引相減，得到節(jié)點之間被分隔的數(shù)量
let average = shift / subTrees// 平分偏移量
v.shift += shift// 完整的shift值添加到v節(jié)點的shift屬性上
v.change -= average// v左邊的節(jié)點從右往左要添加的偏移量是遞減的，所以是加上負的average
leftV.change += average// v.change減了average，為了不影響leftV左側(cè)的節(jié)點，這里需要恢復(fù)
// ...
};
接下來以下圖為例來看一下這個過程，假設(shè)P節(jié)點最終計算出來的shift = 3，那么P.number - G.number = 4 - 1 = 3，中間節(jié)點分攤的值3 / 3 = 1，節(jié)點G到P之間的節(jié)點要距離相等的話，H需要向右移動1，H2要移動1 + 1，這樣它們的坐標為1,3,5,7，等差數(shù)列，間距相等，如果還有更多節(jié)點，以此類推，因為越右邊的節(jié)點移動了本身的1后，還被前面的n個節(jié)點向右推了n * 1，我們把這兩個值保存到節(jié)點G和P上：
然后執(zhí)行execute_shifts方法從后往前遍歷Q的子節(jié)點：
1.
change=0，shift=0，首先更新最后一個節(jié)點P2：P2.x和P2.mod加上shift，即加0，更新change：change + P2.change = 0 + 0 = 0，更新shift：shift + P2.shift + change = 0 + 0 + 0 = 02.更新
P節(jié)點：P.x和P.mod加上shift，即加0，更新change：change + P.change = 0 + (-1) = -1，更新shift：shift + P.shift + change = 0 + 3 + (-1) = 23.更新
H2節(jié)點：H2.x和H2.mod加上shift，即加2，更新change：change + H2.change = -1 + 0 = -1，更新shift：shift + H2.shift + change = 2 + 0 + (-1) = 14.更新
H節(jié)點：H.x和H.mod加上shift，即加1，更新change：change + H.change = -1 + 0 = -1，更新shift：shift + H.shift + change = 1 + 0 + (-1) = 05.更新
G節(jié)點：G.x和G.mod加上shift，即加0，更新change：change + G.change = -1 + 1 = 0，更新shift：shift + G.shift + change = 0 + 0 + 0 = 06.更新
G0節(jié)點：G0.x和G0.mod加上shift，即加0，更新change：change + G0.change = 0 + 0 = 0，更新shift：shift + G0.shift + change = 0 + 0 + 0 = 0
以上就是譯者馬后炮式的理解，最終效果：
x和y交換一下：
實現(xiàn)思維導(dǎo)圖
上述算法還是不能直接應(yīng)用于思維導(dǎo)圖的，因為前面考慮的樹每個節(jié)點的大小都是一樣的，而思維導(dǎo)圖每個節(jié)點的寬高都是有可能不同的，需要在上述算法的基礎(chǔ)上進行一定修改，因為本文已經(jīng)很長了，所以就不細說了，在線示例https://wanglin2.github.io/tree_layout_demo/，完整代碼在https://github.com/wanglin2/tree_layout.
