前面幾天所介紹的資料結構就是線性的資料結構，今天開始所介紹的樹資料節構是屬於非線性資料結構，也非常的重要。

基本定義

在進入 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) 都是基於二元樹演變而來。透過二元樹，我們可以更深入掌握如何在 搜尋、排序、圖形處理、編譯器語法樹 等問題中找到高效的解法。