本文同步更新於個人網站中，有更好的排版和程式碼區塊 highlighting 支援。
Tree 是電腦程式設計中最重要、最核心的一種資料結構。樹狀結構是日常生活中廣泛存在的一種結構，例如族譜、公司組織架構等等。在程式設計中，Tree 更是無處不在，例如瀏覽器的 DOM、文件系統、編譯器中的語法樹也是一種樹。
而 Tree 這種資料結構，最經典、最基礎的例子就是二元樹（Binary Tree）。掌握好二元樹是學習其他樹狀結構的基石。
鏈結串列的每個節點都是物件，它由一個 next 屬性指向下一個節點，而樹是由多個屬性指向多個節點，然後每個節點都是同一種結構。整體結構可以參考附圖。
以前端人最熟悉的 HTML DOM Tree 為例：html 就是樹，然後它有兩個孩子 head 和 body，我們可以透過 html.firstChild、html.lastChild 存取它們。然後他們也可以透過 parentNode 存取到 html。head 裡也有許多元素節點。為了方便管理元素，瀏覽器提供了一個 children 屬性，裝載了某個元素的所有子元素節點。
接著來學習一下樹的基本術語：
樹的分類有很多種，但基本上都是二元樹的衍生。二元樹顧名思義，就是每個節點最多只能有兩個子節點的樹，這兩個子樹被稱為左子樹和右子樹。而左右子樹也必須是二元樹，並且次序不能任意顛倒。
二元樹是遞迴定義的，所以一般二元樹的相關題目也都可以使用遞迴的思想來解決。當然也有一些可以使用非遞迴的方法解決。
二元樹有 3 種型態：歪斜樹、完滿二元樹、完整二元樹。
n 個節點的二元樹按層序編號，如果編號為 i 的節點與同樣深度的完滿二元樹中編號為 i 的節點在二元樹中的位置完全相同，那麼它就是完整二元樹。完滿二元樹一定是完整二元樹，但完整二元樹不一定是完滿二元樹。兩者結構示意圖如下：
二元樹的主要方法如下：
二元樹的許多方法是遞迴實現的，實作程式碼如下：
class TreeNode {
constructor(data) {
this.parent = null;
this.data = data;
this.left = null;
this.right = null;
}
}
class Tree {
constructor() {
this.root = null;
this._size = 0;
}
insert(data) {}
remove(data) {}
size() {}
minNode() {}
maxNode() {}
min() {}
max() {}
getNodeSize() {}
height() {}
getNodeHeight() {}
}
我們新增一個私有屬性 _insertLeft，用來決定資料插入的位置。首先，我們需要判斷它有沒有左子樹節點：沒有則插入左邊，如果有則插入右邊。如果這個節點滿了，那就要選擇是從左子樹還是右子樹繼續往下找。我們通過 _insertLeft 來決定是往左邊還是右邊，可以這次是左邊，下次是右邊，每次執行前修改 _insertLeft 的值。
constructor() {
this.root = null;
this._size = 0;
this._insertLeft = false;
}
insert(data) {
const dir = (this._insertLeft = !this._insertLeft); // 插入方向
function insertIt(node, data) {
if (node.data === data) {
return false;
} else if (!node.left) {
node.left = new TreeNode(data);
node.left.parent = node;
return true;
} else if (!node.right) {
node.right = new TreeNode(data);
node.right.parent = node;
return true;
} else {
if (dir === true) {
return insertIt(node.left, data); // 遞迴
}
return insertIt(node.right, data); // 遞迴
}
}
let ret = false;
if (!this.root) {
this.root = new TreeNode(data);
ret = true;
} else {
ret = insertIt(this.root, data);
}
if (ret) {
this._size++;
}
return ret;
}
const tree = new Tree();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
tree.insert(6);
tree.insert(7);
tree.insert(8);
console.log(tree);
執行一下上面的程式碼，在控制台確認一下結果：
在開始刪除操作之前，我們需要先實作一個搜尋方法，傳入 data，有與之對應的資料就回傳該節點，沒有就回傳 null。 由於我們的樹的資料是沒有放置規則的，所以只能全部遞迴搜尋一遍。
find(data) {
let ret = null;
function findIt(node, data) {
if (node) {
if (node.data === data) {
ret = node;
} else {
findIt(node.left, data);
findIt(node.right, data);
}
}
}
findIt(this.root, data);
return ret;
}
刪除可以算是二元樹最為複雜的操作，因為刪除節點後，樹的結構會發生變化，所以刪除操作需要考慮很多情況。
在刪除時上面四種情況都必須考慮進去，並且這四種情況還有更細的劃分。實作程式碼如下：
remove(data) {
const node = this.find(data);
if (node) {
this._size--;
if (node === this.root) {
this.root = null;
return true;
}
let left = node.left;
let right = node.right;
let parent = node.parent;
let isLeft = parent && parent.left === node;
if (!left && !right) { // 沒有子節點
// todo 1
} else if (left && !right) { // 只有左子節點
// todo 2
} else if (!left && right) { // 只有右子節點
// todo 3
} else if (left && right) { // 有左右子節點
// todo 4
}
}
}
(1) 如果被刪除的節點是葉節點，直接刪掉就好了，具體操作是判斷它是父節點哪一邊的子節點，然後將父節點的對應屬性設為 null。
if (isLeft) {
parent.left = null;
} else {
parent.right = null;
}
(2) 被刪除的節點只有左子節點。
if (isLeft) {
parent.left = left;
} else {
parent.right = left;
}
left.parent = parent;
當被刪除的節點只有一個子節點時，我們只需要將子節點提升到被刪除的節點的位置即可。只是在最後一步，我們需要將子節點的 parent 屬性指向被刪除節點的 parent 屬性。
(3) 被刪除的節點只有右子節點，這種情況跟第二種情況類似：
if (isLeft) {
parent.left = right;
} else {
parent.right = right;
}
right.parent = parent;
(4) 被刪除的節點有兩個子節點，這種情況最為麻煩，如果我們隨便選擇一個子節點來替代被刪除的節點，那麼這個分支上就只有一個子節點了。一個完整的二元樹不能在中間出現只有一個子節點的情況。因此，我們可以在被刪除節點的“孩子”裡找到一個葉節點，先讓它替代被刪除的節點，然後再刪除這個葉節點。
let child = right;
while (child.left) {
child = child.left;
}
this.remove(child.data);
node.data = child.data;
這樣一來 remove 方法就成功了，但有許多可以改進的地方，我們可以將一些重複的程式碼獨立出來，例如連接被刪節點的“子節點”和“父節點”這一步，可以寫成一個 transplant 方法：
transplant(node, child) {
if (node.parent == null) {
this.root = child;
} else if (node === node.parent.left) {
node.parent.left = child;
} else {
node.parent.right = child;
}
if (child) {
child.parent = node.parent;
}
}
移除的方法可以弄成幾個分支：有兩個子節點，只有一個子節點，沒有子節點。程式碼如下：
remove(data) {
const node = this.find(data);
if (node) {
this.removeNode(node);
this._size--;
}
}
removeNode(node) {
// 如果有兩個子節點
if (node.left !== null && node.right !== null) {
let succ = null;
for (succ = node.right; succ.left !== null; succ = succ.left); // 找到後繼
node.data = succ.data; // 用後繼的值替換當前節點的值
this.removeNode(succ); // 遞迴刪除，只可能遞迴一次
} else {
// 葉節點或只有一個子節點
let child = node.left || node.right || null;
this.transplant(node, child);
}
}
如果這個二元樹是一個二元搜尋樹（後面會提到），那麼最大值和最小值就是最右邊的葉節點和最左邊的葉節點：
minNode(node) {
let current = node || this.root;
while (current.left) {
current = current.left;
}
return current;
}
maxNode(node) {
let current = node || this.root;
while (current.right) {
current = current.right;
}
return current;
}
min() {
const node = this.minNode();
return node ? node.data : null;
}
max() {
const node = this.maxNode();
return node ? node.data : null;
}
如果不是二元搜尋樹，那麼就需要遍歷整棵樹，找到最大值和最小值。
要取得二元樹的節點數，需要遍歷所有子樹，然後相加求出總和。
size() {
return this._size; // this.getNodeSize(this.root);
}
getNodeSize(node) {
if (node === null) {
return 0;
}
const leftChildSize = this.getNodeSize(node.left);
const rightChildSize = this.getNodeSize(node.right);
return leftChildSize + rightChildSize + 1;
}
要取得樹的高度，需要遍歷所有子樹的高度，然後取最大值。
height() {
return this.getNodeHeight(this.root);
}
getNodeHeight(node) {
if (node === null) {
return 0;
}
const leftChildHeight = this.getNodeHeight(node.left);
const rightChildHeight = this.getNodeHeight(node.right);
const max = Math.max(leftChildHeight, rightChildHeight);
return max + 1; // 加上自己本身
}
我們今天已經對 Tree 有了一個初步的認識，並且實作了二元樹的建立、新增、刪除、搜尋、取得樹高、取得樹的節點數等方法，明天我們還要來看如何去走訪一棵樹，這也是一個非常基礎且重要的操作。
iThome鐵人賽
看影片追技術