資料結構筆記 4 – Binary Tree (二元樹)

1. Binary Tree 定義

Binary tree 是定義更狹窄的 tree，一棵 binary tree 的定義如下：

• 每個 node 最多有兩個 subTree (也就是最多有兩個 child node)
• Left subTree (左子樹) 和 right subTree (右子樹) 是有順序的，順序不能任意顛倒
• 即使某個 node 只有一個 subTree，也必須區分它是 left subTree 還是 right subTree

2. Binary Tree 種類

Binary tree 根據不同定義，又細分為以下種類

2.1 Skewed Tree (歪斜樹)

2.2 Full / Perfect Binary Tree (滿二元樹 / 完美二元樹)

Full binary tree (滿二元樹) 又稱為 perfect binary tree (完美二元樹)，此種樹的特點為：

• 所有的 node 都存在兩個 subTree (也就是都有 left subTree 和 right subTree)
• 所有的 leaf node 都在同一個 level
• 在同樣 depth 的 binary tree 中，full / perfect binary tree 為 node 數最多的 binary tree

2.3 Complete Binary Tree (完全二元樹)

對一棵 binary tree 的 node 由上至下，由左至右編號，若其編號的 node 和 full binary tree 的 node 一模一樣，則可稱為 complete binary tree。

• Full / perfect binary tree 為 complete binary tree，但 complete binary tree 不一定是 full / perfect binary tree

▲ 所有 node 的編號都有對應到 full binary tree，為 complete binary tree

▲ 並非所有 node 的編號都和 full binary tree 一致，不為 complete binary tree

3. Binary Tree 表示方法

3.1 使用 Array 表示

將 binary tree 用 complete binary tree 的順序取 index：

• 當 binary tree 為 complete binary tree 時，可以不浪費 array 的空間完全用來表示所有 node

[A, B, C, D, E, F, G, H, I, J]

• 當 binary tree 不為 complete binary tree 時，需要用 null 取代本來應該存在 complete binary tree 的 node，如此一來會浪費許多 array 的空間

[A, B, C, D, null, null, null, H, I, null]

因此 array 表示法通常用來表示 complete binary tree。

3.2 使用 Linked-list 表示

可以設計一個 linked-list 的資料結構，該資料結構有 3 個 property：data, left, right，data 用來儲存該 node 的資料， left 和 right 則分別指向 left child node 的 data 和 right child node 的 data。

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

4. 參考資料

大話資料結構(全新彩色版)
Binary Tree: Intro(簡介)
JavaScript 學演算法（十二）- 樹 & 二元樹