Jimmy 的架站筆記

嗨~我是 Jimmy!我可能不是你認識的第 1 個 Jimmy,但一定是最帥的那個。


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

By Jimmy 2022-04-11
發表於 資工 資料結構-資工
資料結構筆記 4 - Binary Tree (二元樹)

1. Binary Tree 定義

Binary tree 是定義更狹窄的 tree,一棵 binary tree 的定義如下:

2. Binary Tree 種類

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

2.1 Skewed Tree (歪斜樹)

Left skewed tree

Right skewed tree

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

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

Full / Perfect Binary Tree

2.3 Complete Binary Tree (完全二元樹)

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

Complete Binary Tree

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

Not Complete Binary Tree

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

3. Binary Tree 表示方法

3.1 使用 Array 表示

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

Array Binary Tree

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

Array Binary Tree

[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;
  }
}

linked-list binary tree

4. 參考資料

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


你可能也會喜歡

演算法筆記 0 – 演算法定義與 Big O Notation

演算法筆記 0 – 演算法定義與 Big O Notation

1. 演算法定義 一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法: 1.1 輸入(Input) An algorithm may have many inputs or no inputs at all. 演算法應該具有 0 個或多個輸入。 1.2 輸出(Output) An algorithm should result at least one outpu

Read More