2025-10-01 約 2300 字預計閱讀 11 分鐘

Tree（樹）資料結構完整教學

什麼是樹？

樹（Tree）是一種非線性的階層式資料結構，由節點（nodes）和邊（edges）組成。樹模擬了現實世界中的階層關係，如組織架構、檔案系統、決策過程等。

樹的基本概念

         A          <- 根節點 (Root)
       / | \
      B  C  D       <- 內部節點 (Internal Nodes)
     /|   \
    E F    G        <- 葉節點 (Leaf Nodes)

重要術語

節點（Node）：樹的基本單位，包含資料和指向其他節點的連結
根（Root）：樹的最頂層節點，沒有父節點
父節點（Parent）：有子節點的節點
子節點（Child）：從屬於另一個節點的節點
葉節點（Leaf）：沒有子節點的節點
兄弟節點（Siblings）：有相同父節點的節點
深度（Depth）：從根到該節點的邊數
高度（Height）：從該節點到最深葉節點的邊數
子樹（Subtree）：節點及其所有後代組成的樹

二元樹（Binary Tree）

二元樹是每個節點最多有兩個子節點的樹結構。

基本實作

class TreeNode:
    """二元樹節點"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    
    def __repr__(self):
        return f"TreeNode({self.val})"

class BinaryTree:
    """二元樹基本實作"""
    def __init__(self):
        self.root = None
    
    def __repr__(self):
        if not self.root:
            return "Empty Tree"
        return self._visualize(self.root)
    
    def _visualize(self, node, level=0, prefix="Root: "):
        """視覺化顯示樹結構"""
        if not node:
            return ""
        
        result = " " * (level * 4) + prefix + str(node.val) + "\n"
        if node.left or node.right:
            if node.left:
                result += self._visualize(node.left, level + 1, "L--- ")
            else:
                result += " " * ((level + 1) * 4) + "L--- None\n"
            
            if node.right:
                result += self._visualize(node.right, level + 1, "R--- ")
            else:
                result += " " * ((level + 1) * 4) + "R--- None\n"
        
        return result

樹的遍歷

1. 深度優先遍歷（DFS）

def preorder_traversal(self, node):
    """前序遍歷：根 -> 左 -> 右"""
    if not node:
        return []
    
    return [node.val] + \
           self.preorder_traversal(node.left) + \
           self.preorder_traversal(node.right)

def inorder_traversal(self, node):
    """中序遍歷：左 -> 根 -> 右"""
    if not node:
        return []
    
    return self.inorder_traversal(node.left) + \
           [node.val] + \
           self.inorder_traversal(node.right)

def postorder_traversal(self, node):
    """後序遍歷：左 -> 右 -> 根"""
    if not node:
        return []
    
    return self.postorder_traversal(node.left) + \
           self.postorder_traversal(node.right) + \
           [node.val]

# 迭代版本的中序遍歷
def inorder_iterative(self, root):
    """迭代版本的中序遍歷"""
    result = []
    stack = []
    current = root
    
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        result.append(current.val)
        current = current.right
    
    return result

2. 廣度優先遍歷（BFS）

from collections import deque

def level_order_traversal(self, root):
    """層序遍歷"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

二元樹的基本操作

def height(self, node):
    """計算樹的高度 - O(n)"""
    if not node:
        return -1
    
    left_height = self.height(node.left)
    right_height = self.height(node.right)
    
    return max(left_height, right_height) + 1

def size(self, node):
    """計算節點數 - O(n)"""
    if not node:
        return 0
    
    return 1 + self.size(node.left) + self.size(node.right)

def is_balanced(self, node):
    """檢查是否平衡 - O(n)"""
    def check(node):
        if not node:
            return True, 0
        
        left_balanced, left_height = check(node.left)
        if not left_balanced:
            return False, 0
        
        right_balanced, right_height = check(node.right)
        if not right_balanced:
            return False, 0
        
        # 檢查高度差
        is_balanced = abs(left_height - right_height) <= 1
        height = max(left_height, right_height) + 1
        
        return is_balanced, height
    
    return check(node)[0]

def find_path(self, root, target):
    """找到從根到目標值的路徑"""
    def dfs(node, path):
        if not node:
            return False
        
        path.append(node.val)
        
        if node.val == target:
            return True
        
        if dfs(node.left, path) or dfs(node.right, path):
            return True
        
        path.pop()
        return False
    
    path = []
    dfs(root, path)
    return path

二元搜尋樹（Binary Search Tree, BST）

BST 是一種特殊的二元樹，滿足以下性質：

左子樹的所有節點值都小於根節點
右子樹的所有節點值都大於根節點
左右子樹也是BST

BST 實作

class BSTNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinarySearchTree:
    """二元搜尋樹實作"""
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        """插入節點 - 平均 O(log n)，最差 O(n)"""
        self.root = self._insert_helper(self.root, val)
    
    def _insert_helper(self, node, val):
        if not node:
            return BSTNode(val)
        
        if val < node.val:
            node.left = self._insert_helper(node.left, val)
        elif val > node.val:
            node.right = self._insert_helper(node.right, val)
        
        return node
    
    def search(self, val):
        """搜尋節點 - 平均 O(log n)，最差 O(n)"""
        return self._search_helper(self.root, val)
    
    def _search_helper(self, node, val):
        if not node:
            return False
        
        if val == node.val:
            return True
        elif val < node.val:
            return self._search_helper(node.left, val)
        else:
            return self._search_helper(node.right, val)
    
    def delete(self, val):
        """刪除節點 - 平均 O(log n)，最差 O(n)"""
        self.root = self._delete_helper(self.root, val)
    
    def _delete_helper(self, node, val):
        if not node:
            return node
        
        if val < node.val:
            node.left = self._delete_helper(node.left, val)
        elif val > node.val:
            node.right = self._delete_helper(node.right, val)
        else:
            # 找到要刪除的節點
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            
            # 有兩個子節點：找右子樹的最小值
            min_node = self._find_min(node.right)
            node.val = min_node.val
            node.right = self._delete_helper(node.right, min_node.val)
        
        return node
    
    def _find_min(self, node):
        """找最小值節點"""
        while node.left:
            node = node.left
        return node
    
    def find_min(self):
        """找整棵樹的最小值 - O(h)"""
        if not self.root:
            return None
        return self._find_min(self.root).val
    
    def find_max(self):
        """找整棵樹的最大值 - O(h)"""
        if not self.root:
            return None
        
        node = self.root
        while node.right:
            node = node.right
        return node.val
    
    def is_valid_bst(self, node=None, min_val=float('-inf'), max_val=float('inf')):
        """驗證是否為有效的BST"""
        if node is None:
            node = self.root
        
        if not node:
            return True
        
        if node.val <= min_val or node.val >= max_val:
            return False
        
        return (self.is_valid_bst(node.left, min_val, node.val) and
                self.is_valid_bst(node.right, node.val, max_val))

BST 的進階操作

def find_kth_smallest(self, k):
    """找第 k 小的元素 - O(n)"""
    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    
    sorted_values = inorder(self.root)
    return sorted_values[k-1] if k <= len(sorted_values) else None

def find_lca(self, p, q):
    """找最近共同祖先 - O(h)"""
    node = self.root
    
    while node:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node.val
    
    return None

def range_sum(self, low, high):
    """計算範圍內的總和 - O(n)"""
    def dfs(node):
        if not node:
            return 0
        
        if node.val < low:
            return dfs(node.right)
        elif node.val > high:
            return dfs(node.left)
        else:
            return node.val + dfs(node.left) + dfs(node.right)
    
    return dfs(self.root)

AVL樹（自平衡二元搜尋樹）

AVL樹是自動保持平衡的BST，任何節點的左右子樹高度差不超過1。

AVL樹實作

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 0

class AVLTree:
    """AVL樹實作"""
    def __init__(self):
        self.root = None
    
    def get_height(self, node):
        """獲取節點高度"""
        if not node:
            return -1
        return node.height
    
    def update_height(self, node):
        """更新節點高度"""
        if node:
            node.height = 1 + max(self.get_height(node.left),
                                  self.get_height(node.right))
    
    def get_balance_factor(self, node):
        """獲取平衡因子"""
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)
    
    def rotate_right(self, y):
        """右旋轉"""
        x = y.left
        T2 = x.right
        
        x.right = y
        y.left = T2
        
        self.update_height(y)
        self.update_height(x)
        
        return x
    
    def rotate_left(self, x):
        """左旋轉"""
        y = x.right
        T2 = y.left
        
        y.left = x
        x.right = T2
        
        self.update_height(x)
        self.update_height(y)
        
        return y
    
    def insert(self, val):
        """插入節點並保持平衡 - O(log n)"""
        self.root = self._insert_helper(self.root, val)
    
    def _insert_helper(self, node, val):
        # 標準BST插入
        if not node:
            return AVLNode(val)
        
        if val < node.val:
            node.left = self._insert_helper(node.left, val)
        elif val > node.val:
            node.right = self._insert_helper(node.right, val)
        else:
            return node  # 不允許重複值
        
        # 更新高度
        self.update_height(node)
        
        # 獲取平衡因子
        balance = self.get_balance_factor(node)
        
        # 左左情況
        if balance > 1 and val < node.left.val:
            return self.rotate_right(node)
        
        # 右右情況
        if balance < -1 and val > node.right.val:
            return self.rotate_left(node)
        
        # 左右情況
        if balance > 1 and val > node.left.val:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        
        # 右左情況
        if balance < -1 and val < node.right.val:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        
        return node
    
    def delete(self, val):
        """刪除節點並保持平衡 - O(log n)"""
        self.root = self._delete_helper(self.root, val)
    
    def _delete_helper(self, node, val):
        # 標準BST刪除
        if not node:
            return node
        
        if val < node.val:
            node.left = self._delete_helper(node.left, val)
        elif val > node.val:
            node.right = self._delete_helper(node.right, val)
        else:
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            
            # 找後繼節點
            temp = self._find_min(node.right)
            node.val = temp.val
            node.right = self._delete_helper(node.right, temp.val)
        
        # 更新高度
        self.update_height(node)
        
        # 重新平衡
        balance = self.get_balance_factor(node)
        
        # 左左情況
        if balance > 1 and self.get_balance_factor(node.left) >= 0:
            return self.rotate_right(node)
        
        # 左右情況
        if balance > 1 and self.get_balance_factor(node.left) < 0:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        
        # 右右情況
        if balance < -1 and self.get_balance_factor(node.right) <= 0:
            return self.rotate_left(node)
        
        # 右左情況
        if balance < -1 and self.get_balance_factor(node.right) > 0:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        
        return node
    
    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

特殊樹結構

1. 完全二元樹（Complete Binary Tree）

class CompleteBinaryTree:
    """使用陣列實作的完全二元樹"""
    def __init__(self):
        self.data = [None]  # 索引從1開始，方便計算
    
    def parent(self, i):
        """父節點索引"""
        return i // 2
    
    def left_child(self, i):
        """左子節點索引"""
        return 2 * i
    
    def right_child(self, i):
        """右子節點索引"""
        return 2 * i + 1
    
    def insert(self, val):
        """插入節點 - O(1)"""
        self.data.append(val)
    
    def get_height(self):
        """獲取高度 - O(1)"""
        import math
        n = len(self.data) - 1
        return int(math.log2(n)) if n > 0 else -1

2. 二元堆（Binary Heap）

class MinHeap:
    """最小堆實作"""
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def push(self, val):
        """插入元素 - O(log n)"""
        self.heap.append(val)
        self._bubble_up(len(self.heap) - 1)
    
    def _bubble_up(self, i):
        """向上調整"""
        parent = self.parent(i)
        if i > 0 and self.heap[i] < self.heap[parent]:
            self.swap(i, parent)
            self._bubble_up(parent)
    
    def pop(self):
        """移除最小元素 - O(log n)"""
        if not self.heap:
            return None
        
        if len(self.heap) == 1:
            return self.heap.pop()
        
        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._bubble_down(0)
        
        return min_val
    
    def _bubble_down(self, i):
        """向下調整"""
        min_index = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] < self.heap[min_index]:
            min_index = left
        
        if right < len(self.heap) and self.heap[right] < self.heap[min_index]:
            min_index = right
        
        if min_index != i:
            self.swap(i, min_index)
            self._bubble_down(min_index)
    
    def peek(self):
        """查看最小元素 - O(1)"""
        return self.heap[0] if self.heap else None

3. 字典樹（Trie）

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    """字典樹實作"""
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """插入單詞 - O(m)，m為單詞長度"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        """搜尋單詞 - O(m)"""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def starts_with(self, prefix):
        """搜尋前綴 - O(m)"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
    
    def delete(self, word):
        """刪除單詞 - O(m)"""
        def _delete_helper(node, word, index):
            if index == len(word):
                if not node.is_end:
                    return False
                node.is_end = False
                return len(node.children) == 0
            
            char = word[index]
            if char not in node.children:
                return False
            
            should_delete = _delete_helper(node.children[char], word, index + 1)
            
            if should_delete:
                del node.children[char]
                return not node.is_end and len(node.children) == 0
            
            return False
        
        _delete_helper(self.root, word, 0)

4. 線段樹（Segment Tree）

class SegmentTree:
    """線段樹實作（區間和查詢）"""
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        
        # 建樹
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    
    def update(self, pos, val):
        """更新值 - O(log n)"""
        pos += self.n
        self.tree[pos] = val
        
        while pos > 1:
            self.tree[pos // 2] = self.tree[pos] + self.tree[pos ^ 1]
            pos //= 2
    
    def query(self, left, right):
        """區間查詢 - O(log n)"""
        res = 0
        left += self.n
        right += self.n
        
        while left < right:
            if left % 2 == 1:
                res += self.tree[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                res += self.tree[right]
            left //= 2
            right //= 2
        
        return res

樹的應用場景

1. 檔案系統

class FileSystem:
    """簡單檔案系統實作"""
    def __init__(self):
        self.root = {'type': 'dir', 'name': '/', 'children': {}}
    
    def mkdir(self, path):
        """建立目錄"""
        dirs = path.split('/')[1:]
        current = self.root
        
        for dir_name in dirs:
            if dir_name not in current['children']:
                current['children'][dir_name] = {
                    'type': 'dir',
                    'name': dir_name,
                    'children': {}
                }
            current = current['children'][dir_name]
    
    def create_file(self, path, content=""):
        """建立檔案"""
        parts = path.split('/')[1:]
        file_name = parts[-1]
        dirs = parts[:-1]
        
        current = self.root
        for dir_name in dirs:
            if dir_name not in current['children']:
                return False
            current = current['children'][dir_name]
        
        current['children'][file_name] = {
            'type': 'file',
            'name': file_name,
            'content': content
        }
        return True

2. 表達式樹

class ExprNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class ExpressionTree:
    """表達式樹求值"""
    def __init__(self, postfix):
        self.root = self.build_tree(postfix)
    
    def build_tree(self, postfix):
        """從後序表達式建樹"""
        stack = []
        operators = {'+', '-', '*', '/'}
        
        for token in postfix:
            if token not in operators:
                stack.append(ExprNode(int(token)))
            else:
                right = stack.pop()
                left = stack.pop()
                stack.append(ExprNode(token, left, right))
        
        return stack[0] if stack else None
    
    def evaluate(self):
        """計算表達式的值"""
        return self._eval_helper(self.root)
    
    def _eval_helper(self, node):
        if not node:
            return 0
        
        # 葉節點（數字）
        if not node.left and not node.right:
            return node.val
        
        # 遞迴計算左右子樹
        left_val = self._eval_helper(node.left)
        right_val = self._eval_helper(node.right)
        
        # 根據運算符計算
        if node.val == '+':
            return left_val + right_val
        elif node.val == '-':
            return left_val - right_val
        elif node.val == '*':
            return left_val * right_val
        elif node.val == '/':
            return left_val / right_val if right_val != 0 else 0

樹的常見問題與解法

1. 最近公共祖先（LCA）

def find_lca(self, root, p, q):
    """找兩個節點的最近公共祖先"""
    if not root or root == p or root == q:
        return root
    
    left = self.find_lca(root.left, p, q)
    right = self.find_lca(root.right, p, q)
    
    if left and right:
        return root
    
    return left if left else right

2. 序列化與反序列化

class Codec:
    """二元樹的序列化與反序列化"""
    def serialize(self, root):
        """前序遍歷序列化"""
        def preorder(node):
            if not node:
                vals.append("#")
            else:
                vals.append(str(node.val))
                preorder(node.left)
                preorder(node.right)
        
        vals = []
        preorder(root)
        return ",".join(vals)
    
    def deserialize(self, data):
        """反序列化"""
        def build():
            val = next(vals)
            if val == "#":
                return None
            
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        
        vals = iter(data.split(","))
        return build()

3. 樹的直徑

def diameter_of_tree(self, root):
    """計算樹的直徑（最長路徑）"""
    self.diameter = 0
    
    def height(node):
        if not node:
            return 0
        
        left_height = height(node.left)
        right_height = height(node.right)
        
        # 更新直徑
        self.diameter = max(self.diameter, left_height + right_height)
        
        return max(left_height, right_height) + 1
    
    height(root)
    return self.diameter

效能比較

資料結構	插入	刪除	搜尋	特點
二元樹	O(n)	O(n)	O(n)	無特殊限制
BST	O(h)	O(h)	O(h)	有序性
AVL樹	O(log n)	O(log n)	O(log n)	嚴格平衡
紅黑樹	O(log n)	O(log n)	O(log n)	近似平衡
B樹	O(log n)	O(log n)	O(log n)	多路平衡
Heap	O(log n)	O(log n)	O(n)	優先級
Trie	O(m)	O(m)	O(m)	字串處理

實際應用範例

1. 決策樹

class DecisionNode:
    def __init__(self, question=None, true_branch=None, false_branch=None, prediction=None):
        self.question = question
        self.true_branch = true_branch
        self.false_branch = false_branch
        self.prediction = prediction

class DecisionTree:
    """簡單決策樹"""
    def __init__(self):
        self.root = None
    
    def predict(self, sample):
        """預測樣本"""
        return self._predict_helper(self.root, sample)
    
    def _predict_helper(self, node, sample):
        if node.prediction is not None:
            return node.prediction
        
        if self.answer_question(sample, node.question):
            return self._predict_helper(node.true_branch, sample)
        else:
            return self._predict_helper(node.false_branch, sample)
    
    def answer_question(self, sample, question):
        """回答問題（簡化版）"""
        feature, operator, value = question
        if operator == ">=":
            return sample[feature] >= value
        elif operator == "==":
            return sample[feature] == value
        return False

2. 遊戲樹（Minimax）

class GameTree:
    """遊戲樹與Minimax算法"""
    def __init__(self, state, is_maximizing=True):
        self.state = state
        self.is_maximizing = is_maximizing
        self.children = []
    
    def minimax(self, depth, alpha=float('-inf'), beta=float('inf')):
        """Minimax with Alpha-Beta剪枝"""
        if depth == 0 or self.is_terminal():
            return self.evaluate()
        
        if self.is_maximizing:
            max_eval = float('-inf')
            for child in self.children:
                eval = child.minimax(depth - 1, alpha, beta)
                max_eval = max(max_eval, eval)
                alpha = max(alpha, eval)
                if beta <= alpha:
                    break  # Beta剪枝
            return max_eval
        else:
            min_eval = float('inf')
            for child in self.children:
                eval = child.minimax(depth - 1, alpha, beta)
                min_eval = min(min_eval, eval)
                beta = min(beta, eval)
                if beta <= alpha:
                    break  # Alpha剪枝
            return min_eval
    
    def is_terminal(self):
        """檢查是否為終端節點"""
        return len(self.children) == 0
    
    def evaluate(self):
        """評估函數（需要根據具體遊戲實作）"""
        return 0

總結

樹是計算機科學中最重要的資料結構之一：

核心概念

基本結構：節點和邊的階層關係
遍歷方法：DFS（前中後序）和BFS
平衡性：影響操作效率的關鍵

常見樹類型

二元樹：最基礎的樹結構
BST：提供有序性
平衡樹：AVL、紅黑樹等
特殊用途：Heap、Trie、B樹等

應用場景

資料庫索引：B樹、B+樹
檔案系統：目錄結構
決策支援：決策樹
遊戲AI：遊戲樹
編譯器：語法樹
網路路由：最短路徑樹

選擇指南

需要快速插入刪除 → Heap
需要有序性 → BST/AVL/紅黑樹
處理字串 → Trie
區間查詢 → 線段樹
持久化存儲 → B樹

理解樹的原理和應用，是成為優秀程式設計師的必經之路！

Tree（樹）資料結構完整指南