0. 學習目標

樹 (Tree) 是程序設(shè)計和算法中最重要的非線性數(shù)據(jù)結(jié)構(gòu)之一，它以層次化的方式組織數(shù)據(jù)，廣泛應用于文件系統(tǒng)、數(shù)據(jù)庫索引、表達式解析、網(wǎng)絡路由等場景。本節(jié)將首先介紹樹的基本概念及其抽象數(shù)據(jù)類型 (ADT)，然后講解常見的兩種存儲實現(xiàn)方式，并通過示例驗證其操作；最后結(jié)合實際問題，演示如何利用樹實現(xiàn)復雜算法。
通過本節(jié)學習，應掌握以下內(nèi)容：

• 樹的基本概念、術(shù)語及常見類型
• 樹的抽象數(shù)據(jù)類型定義及核心操作
• 鏈式存儲與順序存儲（數(shù)組表示）的實現(xiàn)方法及時間空間復雜度分析
• 常用遍歷算法(前序、中序、后序、層次)及其實現(xiàn)
• 利用樹解決實際問題(表達式求值等)

1. 樹的基本概念

在計算機科學中，樹 (Tree) 是一種表示層次關(guān)系的非線性抽象數(shù)據(jù)結(jié)構(gòu)，由節(jié)點 (Node) 和連接節(jié)點的邊 (Edge) 組成。每個節(jié)點最多只有一個父節(jié)點，但可以連接任意數(shù)量的子節(jié)點，這意味著樹中不存在環(huán)路或循環(huán)結(jié)構(gòu)。根節(jié)點 (Root) 是沒有父節(jié)點的節(jié)點，作為樹的起始點；而沒有子節(jié)點的節(jié)點稱為葉節(jié)點 (Leaf)。樹中每個節(jié)點可以擁有零個或多個子節(jié)點，適用于文件系統(tǒng)、組織結(jié)構(gòu)等場景。

1.1 常用術(shù)語

樹 (Tree)：由節(jié)點 (Node) 和連接節(jié)點的邊 (Edge) 組成的層次結(jié)構(gòu)。
根節(jié)點 (Root)：沒有父節(jié)點的唯一節(jié)點。
子節(jié)點 (Child) 與父節(jié)點 (Parent)：父節(jié)點是直接與子節(jié)點相連且位于上層的節(jié)點，子節(jié)點是其下層節(jié)點。
葉子節(jié)點 (Leaf)：沒有子節(jié)點的節(jié)點。
內(nèi)部節(jié)點（Internal Node）：至少有一個子節(jié)點的非根節(jié)點。
深度 (Depth)：從根節(jié)點到某節(jié)點的邊數(shù)；根的深度為 0。
高度 (Height)：從某節(jié)點到最深葉子的最長邊數(shù)；整棵樹的高度是根的高度。
度 (Degree)：節(jié)點擁有的子節(jié)點個數(shù)；樹的度是所有節(jié)點度的最大值。
二叉樹 (Binary Tree)：度不超過 2 的有序樹，子節(jié)點分別稱為左子樹和右子樹。

1.2 樹的抽象數(shù)據(jù)類型

ADT Tree
?數(shù)據(jù)對象：$D=n_i\mid n_i\in \text{Node},i=1,2,\dots$
?數(shù)據(jù)關(guān)系：$R=?n_i,n_j?|a_i,a_{i+1}\in D,i=1,2,...,n?1$
?基本操作：
??1. __init__()：初始化空樹
??2. is_empty()：判斷樹是否為空
??3. add_root(data)：創(chuàng)建根節(jié)點
??4. add_child(parent, data)：在指定父節(jié)點下添加子節(jié)點
??5. remove(node)：刪除指定節(jié)點及其子樹
??6. traverse_preorder(mode)：按指定模式遍歷樹
??7. find(data)：查找值為 data 的節(jié)點

1.3 樹的應用場景

樹具有廣泛的應用場景，例如：

• 文件系統(tǒng)：目錄與文件的層次管理
• XML/JSON 解析：數(shù)據(jù)以樹狀結(jié)構(gòu)存儲
• 編譯原理：抽象語法樹用于表達式和程序結(jié)構(gòu)
• 數(shù)據(jù)庫索引：如 B 樹、B+ 樹、紅黑樹等
• 路由表和決策樹：網(wǎng)絡分組轉(zhuǎn)發(fā)與機器學習

2. 樹的實現(xiàn)

樹的存儲方式主要有兩種：鏈式存儲(每個節(jié)點保存對其子節(jié)點的引用)和順序存儲(使用列表保存所有節(jié)點及其父節(jié)點索引)。

2.1 鏈式存儲實現(xiàn)

樹的鏈式存儲中，每個節(jié)點包含數(shù)據(jù)和指向其子節(jié)點的指針。使用一個列表 (children) 來存儲子節(jié)點。每個節(jié)點可能有多個子節(jié)點，因此我們使用一個列表來保存這些子節(jié)點的引用：

class ChainNode:def __init__(self, data):self.data = dataself.children = []  # 存放子節(jié)點引用def __str__(self):return str(self.data)

2.1.1 樹的初始化

初始化空樹，即將根節(jié)點設(shè)置為 None：

class Tree:def __init__(self):self.root = None

2.1.2 樹判空

判斷樹是否為空，當根節(jié)點為 None 時，樹為空：

    def is_empty(self):return self.root is None

2.1.3 創(chuàng)建根節(jié)點

創(chuàng)建根節(jié)點，若已有根則拋出異常；返回新建的根節(jié)點引用：

    def add_root(self, data):if self.root is not None:raise Exception("根節(jié)點已存在")self.root = ChainNode(data)return self.root

2.1.4 創(chuàng)建子節(jié)點

在指定父節(jié)點下添加子節(jié)點，父節(jié)點不存在時拋出異常；返回新建的子節(jié)點引用：

    def add_child(self, parent, data):if parent is None:raise Exception("父節(jié)點不存在")node = ChainNode(data)parent.children.append(node)return node

2.1.5 刪除指定節(jié)點

刪除指定節(jié)點及其整個子樹，若刪除根則將樹置為空：

    def remove(self, node):if self.root is None or node is None:returnif node is self.root:self.root = Nonereturndef _remove_from_parent(cur, target):for child in cur.children:if child is target:cur.children.remove(child)return Trueif _remove_from_parent(child, target):return Truereturn False_remove_from_parent(self.root, node)

2.1.6 遍歷樹

按指定模式遍歷樹，支持前序 (preorder)、后序 (postorder) 和層序 (levelorder)：
前序遍歷：也稱深度優(yōu)先遍歷，首先訪問根節(jié)點，然后遞歸依次遍歷各子樹
后序遍歷：首先對節(jié)點的各子樹依次遞歸遍歷，然后訪問根節(jié)點
層序遍歷：也成廣度優(yōu)先遍歷，按層次從上至下、從左至右依次訪問節(jié)點

    def traverse(self, mode='preorder'):if self.root is None:return []result = []if mode == 'preorder':def dfs_pre(node):result.append(node.data)for ch in node.children:dfs_pre(ch)dfs_pre(self.root)elif mode == 'postorder':def dfs_post(node):for ch in node.children:dfs_post(ch)result.append(node.data)dfs_post(self.root)elif mode == 'levelorder':from collections import dequeq = deque([self.root])while q:cur = q.popleft()result.append(cur.data)for ch in cur.children:q.append(ch)else:raise ValueError("不支持的遍歷模式：" + mode)return result

2.1.7 查找

查找值為 data 的節(jié)點，返回第一個匹配的節(jié)點引用，否則返回 None：

    def find(self, data):def dfs(node):if node.data == data:return nodefor ch in node.children:found = dfs(ch)if found:return foundreturn Noneif self.root is None:return Nonereturn dfs(self.root)

2.2 順序存儲實現(xiàn)

在樹的順序存儲中，我們通常使用數(shù)組(或列表)來存儲樹的節(jié)點信息，并通過節(jié)點的父子關(guān)系來定位每個節(jié)點的位置，每個節(jié)點的子節(jié)點在數(shù)組中的位置是連續(xù)的。

2.2.1 樹的初始化

初始化空樹，數(shù)據(jù)和值列表均為空：

class SeqTree:def __init__(self):self.data_list = []self.parent_list = []

2.2.2 判樹空

判斷樹是否為空，當 data_list 為空時返回 True：

    def is_empty(self):return len(self.data_list) == 0

2.2.3 創(chuàng)建根節(jié)點

創(chuàng)建根節(jié)點，將 data_list 添加根值，parent_list 添加 -1；返回根節(jié)點索引：

    def add_root(self, data):if not self.is_empty():raise Exception("根已存在")self.data_list.append(data)self.parent_list.append(-1)return 0

2.2.4 創(chuàng)建子節(jié)點

在指定父節(jié)點索引下添加子節(jié)點，索引無效時拋出異常；返回新節(jié)點索引：

    def add_child(self, parent_idx, data):if parent_idx < 0 or parent_idx >= len(self.data_list):raise IndexError("父節(jié)點索引無效")idx = len(self.data_list)self.data_list.append(data)self.parent_list.append(parent_idx)return idx

2.2.5 刪除指定節(jié)點

刪除指定節(jié)點及其子樹，先收集所有待刪除節(jié)點索引，再降序刪除并修正父索引：

    def remove(self, idx):if idx < 0 or idx >= len(self.data_list):returnto_del = set()def dfs_del(i):to_del.add(i)for j, p in enumerate(self.parent_list):if p == i:dfs_del(j)dfs_del(idx)for i in sorted(to_del, reverse=True):self.data_list.pop(i)self.parent_list.pop(i)self.parent_list = [p-1 if p > i else p for p in self.parent_list]

2.6 遍歷樹

按指定模式遍歷樹，支持 preorder、postorder 和 levelorder：

    def traverse(self, mode='preorder'):if self.is_empty():return []result = []if mode == 'preorder':def dfs(i):result.append(self.data_list[i])for j, p in enumerate(self.parent_list):if p == i:dfs(j)dfs(0)elif mode == 'postorder':def dfs(i):for j, p in enumerate(self.parent_list):if p == i:dfs(j)result.append(self.data_list[i])dfs(0)elif mode == 'levelorder':from collections import dequeq = deque([0])while q:i = q.popleft()result.append(self.data_list[i])for j, p in enumerate(self.parent_list):if p == i:q.append(j)else:raise ValueError("不支持的遍歷模式：" + mode)return result

2.7 查找

查找值為 data 的節(jié)點，返回第一個匹配的索引，否則返回 None：

   def find(self, data):for i, d in enumerate(self.data_list):if d == data:return ireturn None

2.3 實現(xiàn)對比

特性	鏈式存儲	順序存儲
存儲結(jié)構(gòu)	節(jié)點對象 + 動態(tài)列表	Python 列表
插入	$O(1)$	$O(1)$，但可能觸發(fā)擴容復制
刪除	$O(n)$	$O(n)$
遍歷	遞歸/迭代	索引計算
空間利用率	與節(jié)點個數(shù)成正比	需預留/擴容，存在浪費

3. 樹的應用

3.1 鏈樹

首先初始化一個鏈樹，然后測試相關(guān)操作：

tree = ChainTree()
r = tree.add_root('A')
b = tree.add_child(r, 'B')
c = tree.add_child(r, 'C')
tree.add_child(b, 'D')
tree.add_child(b, 'E')
print(tree.traverse('preorder'))
print(tree.find('E').data)
tree.remove(b)
print(tree.traverse('levelorder'))

輸出結(jié)果如下所示：

['A', 'B', 'D', 'E', 'C']
E
['A', 'C']

3.2 順序樹

初始化一個順序樹，然后測試相關(guān)操作：

st = SeqTree()
r_idx = st.add_root('A')
b_idx = st.add_child(r_idx, 'B')
c_idx = st.add_child(r_idx, 'C')
st.add_child(b_idx, 'D')
st.add_child(b_idx, 'E')
print(st.traverse('postorder'))
print(st.find('C'))
st.remove(b_idx)
print(st.traverse('levelorder'))

輸出結(jié)果如下所示：

['D', 'E', 'B', 'C', 'A']
2
['A', 'C']

小結(jié)

本節(jié)系統(tǒng)地介紹了樹的基本術(shù)語和結(jié)構(gòu)，包括節(jié)點、邊、根節(jié)點、父子關(guān)系、度、深度和高度等概念，建立對樹結(jié)構(gòu)的清晰認知。隨后，通過詳細的代碼，展示了樹的構(gòu)建及其常用的遍歷方法，包括前序、后序和層次遍歷。