5.3 樹的應用與表示法#

概念說明#

樹在真實系統中無所不在，而「如何在記憶體中表示一棵樹」會直接影響程式效率。常見表示法有三：

引用（節點物件）表示法：每個節點持有子節點參考，如前兩節的 TreeNode。最直觀，適合二元樹。
子女串列表示法：每個節點的子女存成一個串列，適合「分支數不定的多叉樹」，如檔案系統、組織圖。
陣列表示法：把節點按層序放進陣列，索引 i 的左右小孩分別在 2i+1、2i+2，父節點在 (i-1)//2。零指標、快取友善，正是第7章堆積的基礎，也用於以 1 為起點的「左子女右兄弟」編碼。

另有幾個重要家族：運算式樹（編譯器解析 a+b*c 後的抽象語法樹，後序走訪即求值）、堆積（優先權佇列，第7章）、字典樹 Trie（字串前綴，第8章）。

Python 實作#

多叉樹：迷你檔案系統

class FileNode:
    def __init__(self, name, is_dir=False, size=0):
        self.name = name
        self.is_dir = is_dir
        self.size = size
        self.children = []            # 子女串列表示法

    def add(self, node):
        self.children.append(node)

    def total_size(self):             # 後序走訪：先算子樹再合併
        s = self.size
        for c in self.children:
            s += c.total_size()
        return s

    def find(self, name):             # DFS 搜尋
        if self.name == name:
            return self
        for c in self.children:
            r = c.find(name)
            if r:
                return r
        return None

    def show(self, depth=0):
        kind = "📁" if self.is_dir else "📄"
        print("  " * depth + f"{kind} {self.name}")
        for c in self.children:
            c.show(depth + 1)

root = FileNode("根目錄", is_dir=True)
docs = FileNode("文件", is_dir=True)
docs.add(FileNode("報告.pdf", size=2000))
docs.add(FileNode("筆記.md", size=15))
img = FileNode("圖片", is_dir=True)
img.add(FileNode("旅行.jpg", size=5000))
root.add(docs); root.add(img)
root.show()
print("總大小：", root.total_size())       # 7015

陣列表示法

#        1
#      /   \
#     2     3        層序放進陣列 [1, 2, 3, 4, 5]
#    / \
#   4   5
tree = [1, 2, 3, 4, 5]
for i in range(len(tree)):
    l, r = 2*i + 1, 2*i + 2
    kids = []
    if l < len(tree): kids.append(tree[l])
    if r < len(tree): kids.append(tree[r])
    print(f"節點 {tree[i]} 的小孩: {kids}")
# 完全二元樹用陣列表示，指標完全省略

應用對照表#

應用	樹的型態	用到的技術
檔案系統、XML/HTML 解析	多叉樹	子女串列、DFS
編譯器運算式求值	二元運算式樹	後序走訪
資料庫索引、有序集合	平衡搜尋樹（B樹、紅黑樹）	第6章
堆積 / 優先權佇列	完全二元樹	陣列表示、第7章
前綴搜尋、自動補全	Trie	第8章
併查集	森林	第7章 7.3

複雜度分析#

子女串列表示法中，add 是 O(1)；find/total_size 需走整棵樹，O(n)。陣列表示法中，「已知索引找父子」皆 O(1)，但若樹不是完全的，空間會浪費（如只剩右鏈，需 2ⁿ 格）。

練習#

在 FileNode 加上 find_dirs_larger_than(size)：回傳所有總大小超過指定值的目錄（提示：後序走訪）。
寫一個函式把「節點物件表示的二元樹」轉成陣列表示（不足的位置補 None），並反過來寫還原函式。
給定運算式樹節點（value 為數字或 + - * /），實作後序求值函式，並手工畫出 2 * (3 + 4) 對應的樹。