(Day 13) 選擇排序 (Selection Sort)
選擇排序 (Selection Sort) 是一種簡單直觀的排序演算法。核心概念: 每一輪從尚未排序的元素中挑出最小（或最大）者，放到目前應在的位置，一直重複直到完成。可以把它想成「選拔賽」: 第一輪選出最優放第一名，第二輪從剩下的人選次優放第二名，依此類推。
(Day 7) 二元樹 (Binary Tree)
目錄
前面幾天所介紹的資料結構就是線性的資料結構，今天開始所介紹的樹資料節構是屬於非線性資料結構，也非常的重要。
基本定義
在進入 Binary Tree 之前，先來介紹一下基本的組成部分，可以搭配著下圖看:
- Root: 樹的起始點 (e.g. 2)
- Internal: 有子節點的節點 (e.g. 7, 5, 6, 9)
- Leaf: 沒有子節點的節點 (e.g. 2, 5, 11, 4)
Binary Tree 就是一個由有限節點所組成的集合，或由一個 Root 及左右兩個子樹所組成。簡單來說，Binary Tree 最多只能有兩個子節點 (也可以是一個)，Binary Tree 還可以再細分:
- Fully Binary Tree
- Complete Binary Tree
- Skewed Binary Tree
- Strictly Binary Tree
這邊就先點到為止，不一一的詳細介紹。
資料儲存方式
Binary Tree 有很多種的儲存方式，比較常見的會是 Array 與 Linked List 的儲存方式，本篇就會分別介紹這兩種儲存方式。
Array 表示法
就直接用上一張圖的部分來說明，先對照一下，由上至下、由左至右的放入 Array。
- A[1] = 2
- A[2] = 7, A[3] = 5
- A[4] = 2, A[5] = 6, A[6] = null, A[7] = 9
- A[8] = null, A[9] = null, A[10] = 5, A[11] = 11, A[12] = 4, A[13] = null
我們可以發現，index 有以下關係:
- 左子樹 index 是父節點 index*2。
- 右子樹 index 是父節點 index*2+1。
接下來，就用程式碼實作:
tree = [
None, # index 0 不用
2, # A[1]
7, 5, # A[2], A[3]
2, 6, None, 9, # A[4]...A[7]
None, None, 5, 11, 4, None # A[8]...A[13]
]
def left(i):
return 2 * i if 2 * i < len(tree) else None
def right(i):
return 2 * i + 1 if 2 * i + 1 < len(tree) else None
def preorder(i):
if i is None or i >= len(tree) or tree[i] is None:
return
print(tree[i], end=" ")
preorder(left(i))
preorder(right(i))
# 測試
preorder(1) # 從根節點 A[1] 開始
Linked List 表示法
也是用程式碼實作:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# 手動建樹
root = Node(2)
root.left = Node(7)
root.right = Node(5)
root.left.left = Node(2)
root.left.right = Node(6)
root.right.right = Node(9)
root.left.right.left = Node(5)
root.left.right.right = Node(11)
root.right.right.left = Node(4)
# 遞迴遍歷 (前序)
def preorder(node):
if not node: return # 終止條件: 當傳進來的 node 為 None (樹的葉子沒有子節點時)，就直接返回，不做任何事。
print(node.value, end=" ")
preorder(node.left) # 遞迴遍歷左子樹。
preorder(node.right) # 遞迴遍歷右子樹。
preorder(root) # 輸出: 2 7 2 6 5 11 5 9 4
結語
今天我們初步介紹了 Binary Tree，這是一種非線性資料結構，相較於前面提到的線性結構 (Array、Stack、Queue)，樹結構更能有效表達層次與關聯性。Binary Tree 的特性在於每個節點最多有兩個子節點，並且能用 Array 表示法 或 Linked List 表示法 來儲存，這兩種方式在不同應用場景中各有優缺點。
理解 Binary Tree 的概念非常重要，因為後續許多資料結構 (Binary Search Tree、AVL Tree、Heap、Segment Tree) 都是基於二元樹演變而來。透過二元樹，我們可以更深入掌握如何在 搜尋、排序、圖形處理、編譯器語法樹 等問題中找到高效的解法。