第11章树 (Trees)

一、导读

1.1 本章学习目标

完成本章学习后，你将能够：

理解树的定义和基本性质：根、父节点、子节点、叶节点、深度、高度

掌握二叉树的特性和遍历方法：前序、中序、后序、层序

理解二叉搜索树的插入、删除和查找操作

掌握平衡二叉树的概念：AVL树和红黑树的基本原理

理解堆和优先队列的实现

掌握哈夫曼编码的原理和应用

理解决策树在分类和游戏中的应用

能够将层次化数据结构建模为树并设计相应算法

理解B树和B+树在数据库索引中的应用

掌握Trie（前缀树）的结构和字符串匹配应用

1.2 为什么本章如此重要

树是最常用的非线性数据结构，广泛应用于计算机科学的各个领域。

在文件系统中：目录结构是树形组织，文件路径对应从根到节点的路径。权限继承也基于树结构。

在数据库中：B树和B+树是索引的核心结构，支持高效的范围查询和顺序访问。大多数关系数据库默认使用B+树索引。

在编译器中：语法树表示程序结构；符号表组织为树。AST（抽象语法树）是编译器的中间表示。

在人工智能中：决策树用于分类和回归；游戏树用于博弈搜索（如国际象棋、围棋）。随机森林是多个决策树的集成。

在网络中：路由表可以用前缀树（Trie）组织；DNS系统是分层树结构。生成树协议（STP）防止网络环路。

在压缩中：哈夫曼树用于无损数据压缩。LZW等字典压缩也涉及树结构。

在图形学中：场景图是树结构；四叉树/八叉树用于空间划分和碰撞检测。

在版本控制中：Git的提交历史是有向无环图（DAG），但分支模型可以视为树。

1.3 核心问题引导

在学习本章之前，请思考以下问题：

树和图有什么区别？树是特殊的图吗？

为什么二叉搜索树的查找效率可能是O(n)而不是O(log n)？

平衡树如何保证操作效率？

前序、中序、后序遍历各适用于什么场景？

哈夫曼编码为什么能保证无歧义解码？

堆和二叉搜索树有什么区别？

什么是B树？为什么数据库使用它？

决策树如何用于分类？

为什么红黑树比AVL树更常用在某些场景中？

Trie相比哈希表有什么优势？

二、核心概念详解

11.1 树的基本概念

定义

树是一个连通的无环无向图。等价地，树是满足以下任一条件的图：

连通且有 V-1 条边
无环且有 V-1 条边
任意两点之间有且仅有一条路径

有根树：指定一个顶点为根的树。这引入了层次结构。

森林：不相交的树的集合。移除树的根后得到森林。

术语

根（Root）：树的顶层节点
父节点（Parent）：直接上级节点
子节点（Child）：直接下级节点
兄弟节点（Sibling）：同一父节点的子节点
叶节点（Leaf）：没有子节点的节点
内部节点（Internal）：至少有一个子节点的节点
祖先（Ancestor）：从根到该节点路径上的所有节点
后代（Descendant）：该节点的子树中的所有节点
深度（Depth）：从根到该节点的路径长度（根的深度为0）
高度（Height）：从该节点到最远叶节点的路径长度（叶节点的高度为0）
树的高度：根节点的高度 = 最大深度

注意：深度的定义可能因教材而异（有些从1开始）。关键是保持一致。

性质

n个节点的树有 n-1 条边
从根到任意节点有唯一路径
移除任意边会将树分为两棵子树
在任意两个节点之间添加一条边会形成唯一的环

证明n个节点的树有n-1条边（归纳法）：

基础：n=1时，0条边。✓
归纳：假设对n-1成立。n个节点的树至少有一个叶节点。移除叶节点及其关联的边，得到n-1个节点的树，有n-2条边。加上刚才移除的边，共n-1条边。∎

11.2 二叉树

定义

二叉树是每个节点最多有两个子节点的树，分别称为左子节点和右子节点。

满二叉树（Full Binary Tree）：每个节点要么是叶节点，要么有两个子节点。

完全二叉树（Complete Binary Tree）：除了最后一层外，所有层都填满，最后一层的节点尽可能靠左。

完美二叉树（Perfect Binary Tree）：所有内部节点都有两个子节点，所有叶节点在同一层。完美二叉树一定是满二叉树和完全二叉树。

退化二叉树（Degenerate Binary Tree）：每个节点只有一个子节点，退化为链表。

性质

高度为h的二叉树最多有 2^(h+1) - 1 个节点
有n个节点的完全二叉树的高度为 ⌊log₂n⌋
第i层最多有 2^i 个节点（根为第0层）
对于满二叉树，叶节点数 = 内部节点数 + 1

证明叶节点数 = 内部节点数 + 1（满二叉树）：

设L为叶节点数，I为内部节点数，N = L + I为总节点数。

边数 = N - 1 = L + I - 1

另一方面，每个内部节点贡献2条边（因为它有两个子节点），但根节点没有父节点，所以边数 = 2I。

因此 2I = L + I - 1，即 I = L - 1，L = I + 1。∎

遍历

前序遍历（Preorder）：根 → 左 → 右

中序遍历（Inorder）：左 → 根 → 右

后序遍历（Postorder）：左 → 右 → 根

层序遍历（Level-order）：按层从上到下，从左到右（使用BFS）

python

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


def preorder(root):
    """前序遍历"""
    if root is None:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)


def inorder(root):
    """中序遍历"""
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)


def postorder(root):
    """后序遍历"""
    if root is None:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]


def level_order(root):
    """层序遍历"""
    from collections import deque
    if root is None:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

遍历的应用：

前序：复制树、序列化
中序：BST的排序输出
后序：删除树、计算表达式树
层序：BFS相关操作

迭代遍历：可以使用栈模拟递归，避免栈溢出。

11.3 二叉搜索树

定义

二叉搜索树（BST）是满足以下性质的二叉树：

左子树的所有节点值小于根节点
右子树的所有节点值大于根节点
左右子树也是二叉搜索树

注意：严格来说，左子树的所有节点值 ≤ 根节点 < 右子树的所有节点值（允许重复时需要明确规则）。

操作

查找：

python

def search_bst(root, target):
    if root is None or root.val == target:
        return root
    if target < root.val:
        return search_bst(root.left, target)
    return search_bst(root.right, target)

插入：

python

def insert_bst(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

删除：三种情况

叶节点：直接删除

只有一个子节点：用子节点替代

有两个子节点：用后继（右子树最小值）或前驱（左子树最大值）替代，然后删除后继/前驱

python

def delete_bst(root, val):
    if root is None:
        return None
    
    if val < root.val:
        root.left = delete_bst(root.left, val)
    elif val > root.val:
        root.right = delete_bst(root.right, val)
    else:
        # 找到要删除的节点
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        else:
            # 有两个子节点，找后继（右子树最小值）
            successor = find_min(root.right)
            root.val = successor.val
            root.right = delete_bst(root.right, successor.val)
    
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node

复杂度

平均情况（随机插入）：O(log n)
最坏情况（有序插入，退化为链表）：O(n)

改进：使用自平衡BST（AVL树、红黑树）。

11.4 平衡二叉树

AVL树

定义：每个节点的左右子树高度差不超过1（平衡因子 ∈ {-1, 0, 1}）。

旋转：插入或删除后可能破坏平衡，需要通过旋转恢复。

四种不平衡情况：

LL（左左）：右旋

RR（右右）：左旋

LR（左右）：先左旋左子节点，再右旋

RL（右左）：先右旋右子节点，再左旋

性质：高度始终为 O(log n)，所有操作 O(log n)。

旋转示例（LL情况，右旋）：

y              x
    / \            / \
   x   T4   =>   T1   y
  / \                / \
T1   T2            T2   T3

红黑树

定义：每个节点有颜色（红或黑），满足以下性质：

根节点是黑色

叶节点（NIL）是黑色

红色节点的子节点必须是黑色（不能有连续的红色节点）

从任意节点到其叶节点的所有路径包含相同数量的黑色节点

性质：高度为 O(log n)，所有操作 O(log n)。

与AVL树的比较：

AVL树更严格平衡，查找更快
红黑树插入/删除时的旋转更少，修改操作更快
Java TreeMap、C++ std::map、Linux内核使用红黑树

11.5 堆

定义

堆是完全二叉树，满足堆序性质：

最大堆：父节点值 ≥ 子节点值
最小堆：父节点值 ≤ 子节点值

注意：堆不是BST。堆只保证父子关系，不保证左右子树的大小关系。

数组表示

完全二叉树可以用数组高效表示：

根在索引0
节点i的左子节点在 2i+1，右子节点在 2i+2
节点i的父节点在 (i-1)//2

操作

插入（上浮/sift up）：

添加到末尾

与父节点比较，如果违反堆序则交换

重复直到堆序恢复

删除最大/最小（下沉/sift down）：

用最后一个元素替换根

与子节点比较，如果违反堆序则与较小的子节点交换（最小堆）

重复直到堆序恢复

建堆：从最后一个内部节点开始，依次下沉。时间复杂度 O(n)。

python

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)
    
    def pop(self):
        if not self.heap:
            return None
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        min_val = self.heap.pop()
        if self.heap:
            self._sift_down(0)
        return min_val
    
    def _sift_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] < self.heap[parent]:
                self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
                i = parent
            else:
                break
    
    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
            
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
            
            if smallest != i:
                self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
                i = smallest
            else:
                break

应用

优先队列
堆排序：O(n log n) 原地排序
Top-K问题：维护大小为K的堆
合并K个有序列表

11.6 哈夫曼编码

原理

哈夫曼编码是一种最优前缀码，用于无损数据压缩。

步骤：

统计每个字符的频率

将字符放入最小堆

重复：取出两个最小频率的节点，合并为新节点，放回堆中

直到只剩一个节点（根）

从根到叶的路径即为编码（左0右1或反之）

性质：

前缀码：没有任何编码是另一个编码的前缀，保证无歧义解码
最优：平均编码长度最短

python

import heapq

class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right
    
    def __lt__(self, other):
        return self.freq < other.freq


def build_huffman_tree(freq_dict):
    heap = [HuffmanNode(char, freq) for char, freq in freq_dict.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, merged)
    
    return heap[0]


def generate_codes(root, prefix="", codes=None):
    if codes is None:
        codes = {}
    
    if root is None:
        return codes
    
    if root.char is not None:
        codes[root.char] = prefix
    else:
        generate_codes(root.left, prefix + "0", codes)
        generate_codes(root.right, prefix + "1", codes)
    
    return codes

示例：字符频率 {a:5, b:9, c:12, d:13, e:16, f:45}

哈夫曼编码：

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

平均长度 = (45×1 + 12×3 + 13×3 + 5×4 + 9×4 + 16×3) / 100 = 2.24 位/字符

固定长度编码需要 3 位/字符（6个字符）。压缩率 = 2.24/3 ≈ 75%。

11.7 B树和B+树

B树

定义：m阶B树满足：

每个节点最多有m个子节点

除根节点外，每个节点至少有⌈m/2⌉个子节点

根节点至少有2个子节点（如果不是叶节点）

所有叶节点在同一层

非叶节点有k个子节点和k-1个键

特点：

多路搜索树，降低树高
适合磁盘存储（一次I/O读取整个节点）
所有操作 O(log_m n)

应用：文件系统、数据库索引。

B+树

B+树是B树的变体：

所有数据存储在叶节点
内部节点只存储键（作为索引）
叶节点通过链表连接，支持范围查询

优势：

范围查询更高效（只需遍历叶节点链表）
内部节点可以容纳更多键（因为不存数据），降低树高
顺序访问更快

应用：大多数关系数据库（MySQL InnoDB、PostgreSQL）使用B+树索引。

11.8 Trie（前缀树）

定义：Trie是用于存储字符串的树结构，每个节点代表一个字符，从根到节点的路径形成一个前缀。

特点：

共享公共前缀，节省空间
查找时间复杂度 O(L)，L是字符串长度
支持前缀查询（如自动补全）

应用：

自动补全
拼写检查
IP路由表（最长前缀匹配）
词典实现

11.9 决策树

定义：决策树是用于分类和决策的树结构。

内部节点：测试条件
边：测试结果
叶节点：类别或决策

构建算法：ID3、C4.5、CART。

分裂标准：

信息增益（ID3）
信息增益比（C4.5）
基尼指数（CART）

过拟合：决策树容易过拟合，需要剪枝。

集成方法：随机森林、梯度提升树。

三、程序员的视角

3.1 在计算机科学中的应用

文件系统

目录树结构，路径解析使用树遍历。权限继承基于树结构。

数据库索引

B+树支持范围查询和顺序访问。哈希索引不支持范围查询。

XML/JSON解析

文档对象模型（DOM）是树结构。XPath查询是树遍历。

网络路由

IP路由使用前缀树（Trie）。最长前缀匹配决定下一跳。

编译器

语法树表示程序结构。符号表组织为树。

3.2 常见陷阱与误区

BST退化

不平衡的BST可能退化为链表，操作变为O(n)。使用自平衡BST避免。

空指针异常

树操作中需要正确处理空节点。递归基条件是 node is None。

递归深度

深树可能导致栈溢出，考虑迭代实现或增加递归限制。

堆 vs BST

堆只保证堆序，不支持高效的查找和范围查询。BST支持但需要平衡。

3.3 与其他层级的联系

硬件层：堆用于中断优先级管理
操作系统层：进程树；CFS调度器使用红黑树
网络层：路由表的前缀树
应用层：UI组件树；DOM树

四、代码实战

11.1 二叉搜索树完整实现

python

"""
二叉搜索树完整实现
"""


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):
        self.root = self._insert(self.root, val)
    
    def _insert(self, node, val):
        if node is None:
            return BSTNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node
    
    def search(self, val):
        return self._search(self.root, val)
    
    def _search(self, node, val):
        if node is None or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)
    
    def delete(self, val):
        self.root = self._delete(self.root, val)
    
    def _delete(self, node, val):
        if node is None:
            return None
        
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # 找到要删除的节点
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                # 有两个子节点，找后继
                successor = self._find_min(node.right)
                node.val = successor.val
                node.right = self._delete(node.right, successor.val)
        
        return node
    
    def _find_min(self, node):
        while node.left:
            node = node.left
        return node
    
    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result
    
    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)


def demonstrate_bst():
    """演示BST操作"""
    
    bst = BinarySearchTree()
    values = [5, 3, 7, 1, 4, 6, 8]
    
    for v in values:
        bst.insert(v)
    
    print("=== 二叉搜索树 ===")
    print(f"中序遍历: {bst.inorder()}")
    print(f"搜索4: {bst.search(4) is not None}")
    print(f"搜索9: {bst.search(9) is not None}")
    
    bst.delete(3)
    print(f"删除3后中序遍历: {bst.inorder()}")


if __name__ == "__main__":
    demonstrate_bst()

11.2 哈夫曼编码

python

"""
哈夫曼编码实现
"""

import heapq


class HuffmanCoder:
    def __init__(self, text):
        self.text = text
        self.freq = {}
        self.codes = {}
        self.tree = None
        
        self._build_frequency()
        self._build_tree()
        self._generate_codes()
    
    def _build_frequency(self):
        for char in self.text:
            self.freq[char] = self.freq.get(char, 0) + 1
    
    def _build_tree(self):
        heap = [[freq, [char, ""]] for char, freq in self.freq.items()]
        heapq.heapify(heap)
        
        while len(heap) > 1:
            lo = heapq.heappop(heap)
            hi = heapq.heappop(heap)
            
            for pair in lo[1:]:
                pair[1] = '0' + pair[1]
            for pair in hi[1:]:
                pair[1] = '1' + pair[1]
            
            heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
        
        self.tree = heap[0]
        self.codes = dict(heap[0][1:])
    
    def _generate_codes(self):
        pass  # 已在_build_tree中生成
    
    def encode(self):
        return ''.join(self.codes[char] for char in self.text)
    
    def decode(self, encoded):
        # 反向查找
        reverse_codes = {v: k for k, v in self.codes.items()}
        decoded = []
        current = ""
        
        for bit in encoded:
            current += bit
            if current in reverse_codes:
                decoded.append(reverse_codes[current])
                current = ""
        
        return ''.join(decoded)
    
    def compression_ratio(self):
        original_bits = len(self.text) * 8
        encoded_bits = len(self.encode())
        return encoded_bits / original_bits


def demonstrate_huffman():
    """演示哈夫曼编码"""
    
    text = "this is an example of huffman encoding"
    coder = HuffmanCoder(text)
    
    print("=== 哈夫曼编码 ===")
    print(f"原始文本: {text}")
    print(f"字符频率: {coder.freq}")
    print(f"编码表: {coder.codes}")
    
    encoded = coder.encode()
    print(f"编码后: {encoded[:50]}...")
    
    decoded = coder.decode(encoded)
    print(f"解码后: {decoded}")
    print(f"压缩率: {coder.compression_ratio():.2%}")


if __name__ == "__main__":
    demonstrate_huffman()

五、深入思考

5.1 历史背景

树结构的研究始于19世纪。阿瑟·凯莱研究了化学分子结构的计数。迈克尔·阿德尔森-维尔斯基和叶夫根尼·兰迪斯发明了AVL树（1962）。鲁道夫·拜尔发明了B树（1972）。大卫·哈夫曼发明了哈夫曼编码（1952）。

Leo J. Guibas和Edward M. Reingold发展了红黑树的理论。Jon Bentley推广了B树在数据库中的应用。

5.2 前沿方向

持久化树结构：支持历史版本查询（如Git的对象存储）
并发树：多线程环境下的安全操作
外部存储器树：优化磁盘I/O（SSD-aware B树）
机器学习中的树：梯度提升树、XGBoost、LightGBM
量子树算法：量子加速的树遍历

5.3 延伸阅读

《Introduction to Algorithms》by CLRS, Chapters 12-14
《The Art of Computer Programming, Vol. 3》by Donald E. Knuth
《Data Structures and Algorithm Analysis in C++》by Mark Allen Weiss
《Algorithms》by Sedgewick and Wayne

六、实验笔记

实验1：平衡树实现

目标：实现AVL树或红黑树。

任务：

实现插入和删除操作

实现旋转操作

验证平衡性质

比较与BST的性能差异

可视化树结构

提交物：源代码、测试用例、性能对比报告。

实验2：表达式树

目标：使用树结构表示和计算算术表达式。

任务：

解析表达式构建语法树

实现树遍历计算结果

支持括号和运算符优先级

（进阶）生成逆波兰表示

支持变量代入

提交物：源代码、测试表达式、可视化输出。

七、本章小结

本章介绍了树这一重要的数据结构。树是连通的无环图，二叉树是每个节点最多有两个子节点的特殊树。

二叉搜索树支持高效的查找、插入和删除，但可能退化为链表。平衡树（如AVL树、红黑树）通过旋转保持平衡，保证O(log n)的操作复杂度。

堆是完全二叉树实现的优先队列，支持O(log n)的插入和删除。哈夫曼编码利用树结构实现最优前缀码，用于数据压缩。

B树和B+树是数据库索引的核心结构，适合磁盘存储。Trie用于字符串匹配和前缀查询。决策树是机器学习中常用的分类模型。

树结构在文件系統、编译器、网络路由等领域有广泛应用。理解树的性质和算法是设计和分析复杂系统的基础。

八、习题

习题1（基础）：画出包含元素{1,2,3,4,5,6,7}的完美二叉树。

习题2（基础）：对给定二叉树进行前序、中序、后序和层序遍历。

习题3（中等）：证明n个节点的二叉树有n+1个空指针。

习题4（中等）：实现AVL树的插入操作。

习题5（中等）：使用堆实现优先队列，并用它解决Top-K问题。

习题6（较难）：证明哈夫曼编码是最优前缀码。

习题7（较难）：实现B树的插入操作。

习题8（挑战）：研究并实现红黑树。

习题9（挑战）：设计算法判断一棵树是否是另一棵树的子树。

习题10（开放）：选择一个实际应用（如文件系统、数据库索引、编译器），分析其中使用的树结构并撰写报告。包括：

树的结构和特点
操作的复杂度分析
与其他数据结构的比较
实际应用场景和效果

第11章 树 (Trees)

一、导读

1.1 本章学习目标

1.2 为什么本章如此重要

1.3 核心问题引导

二、核心概念详解

11.1 树的基本概念

定义

术语

性质

11.2 二叉树

定义

性质

遍历

11.3 二叉搜索树

定义

操作

复杂度

11.4 平衡二叉树

AVL树

红黑树

11.5 堆

定义

数组表示

操作

应用

11.6 哈夫曼编码

原理

11.7 B树和B+树

B树

B+树

11.8 Trie（前缀树）

11.9 决策树

三、程序员的视角

3.1 在计算机科学中的应用

文件系统

数据库索引

XML/JSON解析

网络路由

编译器

3.2 常见陷阱与误区

BST退化

空指针异常

递归深度

堆 vs BST

3.3 与其他层级的联系

四、代码实战

11.1 二叉搜索树完整实现

11.2 哈夫曼编码

五、深入思考

5.1 历史背景

5.2 前沿方向

5.3 延伸阅读

六、实验笔记

实验1：平衡树实现

实验2：表达式树

七、本章小结

八、习题

第11章树 (Trees)