【算法】《算法图解》第七章学习笔记：树

发表于2025-07-15|更新于2025-07-15|算法

|总字数:6.2k|阅读时长:23分钟|浏览量:

前言

在前面的章节中，我们学习了数组、链表、散列表等基本数据结构，以及一些基础算法。本章将介绍一种非常重要的数据结构——树(Tree)，特别是二叉搜索树(Binary Search Tree)。树结构在计算机科学中应用广泛，从文件系统到数据库再到人工智能，都能看到树的身影。《算法图解》第七章深入浅出地介绍了树的基本概念、实现和应用，帮助读者理解这一关键数据结构。

一、树的基本概念

（一）什么是树

树是一种分层数据的抽象模型，它由一系列节点组成，这些节点通过边相连。树具有以下特性：

树有一个根节点(Root)，它是树的起始点
除根节点外，每个节点都有且仅有一个父节点
每个节点可以有零个或多个子节点
节点之间没有循环连接（这意味着树是无环的）
没有子节点的节点称为叶节点(Leaf)

树的常见术语：

节点(Node): 树中的基本单位，包含数据和指向其他节点的链接
边(Edge): 连接两个节点的线
根(Root): 树顶部的节点，是树中唯一没有父节点的节点
叶节点(Leaf): 没有子节点的节点
父节点(Parent): 有子节点的节点
子节点(Child): 有父节点的节点
兄弟节点(Sibling): 共享同一父节点的节点
高度(Height): 从节点到其最远叶节点的最长路径上的边数
深度(Depth): 从根节点到该节点的边数

（二）树与其他数据结构的比较

树结构综合了数组和链表的一些优点，同时克服了它们的某些缺点：

数据结构	随机访问	插入/删除	有序遍历	查找效率
数组	O(1)	O(n)	O(n)	O(n) (无序)，O(log n) (有序，二分查找)
链表	O(n)	O(1)*	O(n)	O(n)
二叉搜索树	O(log n)**	O(log n)**	O(n)	O(log n)**

*: 假设已知插入/删除位置
**: 对于平衡树，最坏情况下可能退化为O(n)

二、图的搜索算法

在《算法图解》第七章，作者首先介绍了两种重要的图搜索算法：广度优先搜索(BFS)和深度优先搜索(DFS)。这两种算法都可以用于在树或更一般的图结构中搜索节点。

（一）广度优先搜索(BFS)

广度优先搜索是一种逐层遍历的搜索算法，它首先访问起始节点的所有邻居，然后再访问这些邻居的邻居，以此类推。BFS使用队列来跟踪待访问的节点。

BFS的主要特点：

它能找到两点之间的最短路径（段数最少的路径）
对于相同权重的边，BFS总是先找到距离起点”步数”最少的节点

下面是一个简单的BFS实现示例：

from collections import deque

def bfs(graph, start, target):
    """
    使用广度优先搜索在图中查找从start到target的路径
    graph: 邻接表表示的图
    start: 起始节点
    target: 目标节点
    """
    # 创建一个队列用于BFS
    queue = deque([start])
    # 记录已经访问过的节点
    visited = {start}
    # 记录每个节点的前驱节点，用于重建路径
    parent = {start: None}
    
    while queue:
        # 从队列中取出一个节点
        current = queue.popleft()
        
        # 如果找到目标节点，则返回路径
        if current == target:
            path = []
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1]  # 反转路径，从起点到终点
        
        # 对当前节点的所有邻居进行探索
        for neighbor in graph[current]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
                parent[neighbor] = current
    
    # 如果无法到达目标节点
    return None

# 示例使用
if __name__ == "__main__":
    # 定义一个简单的图（使用邻接表表示）
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    
    path = bfs(graph, 'A', 'F')
    if path:
        print(f"从A到F的最短路径是: {' -> '.join(path)}")
    else:
        print("无法从A到达F")

（二）深度优先搜索(DFS)

深度优先搜索与BFS不同，它会尽可能深地探索一条路径，直到走到尽头，然后回溯并探索其他路径。DFS通常使用递归或栈来实现。

DFS的主要特点：

它会沿着一条路径一直走到底，然后回溯
相比BFS，DFS更适合解决像”迷宫”这样的问题，寻找是否存在一条路径
DFS可能不会找到最短路径

以下是DFS的两种常见实现方式：

1. 递归实现

def dfs_recursive(graph, current, target, visited=None):
    """
    递归实现的深度优先搜索
    """
    if visited is None:
        visited = set()
    
    # 标记当前节点为已访问
    visited.add(current)
    
    # 如果找到目标，返回True
    if current == target:
        return True
    
    # 探索所有未访问的邻居
    for neighbor in graph[current]:
        if neighbor not in visited:
            if dfs_recursive(graph, neighbor, target, visited):
                return True
    
    # 如果所有路径都无法找到目标
    return False

2. 使用栈的非递归实现

def dfs_iterative(graph, start, target):
    """
    使用栈的非递归深度优先搜索
    """
    # 用列表模拟栈
    stack = [start]
    # 记录已访问的节点
    visited = set()
    # 记录路径
    parent = {start: None}
    
    while stack:
        # 弹出栈顶元素
        current = stack.pop()
        
        # 如果当前节点已访问，则跳过
        if current in visited:
            continue
        
        # 标记为已访问
        visited.add(current)
        
        # 如果找到目标
        if current == target:
            path = []
            while current is not None:
                path.append(current)
                current = parent.get(current)
            return path[::-1]  # 反转路径
        
        # 将所有未访问的邻居压入栈中
        for neighbor in graph[current]:
            if neighbor not in visited:
                stack.append(neighbor)
                # 只有当邻居没有父节点时才设置父节点
                if neighbor not in parent:
                    parent[neighbor] = current
    
    # 如果无法找到目标
    return None

# 示例使用
if __name__ == "__main__":
    # 与BFS示例相同的图
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    
    # 递归DFS
    if dfs_recursive(graph, 'A', 'F', set()):
        print("递归DFS: 存在从A到F的路径")
    
    # 迭代DFS
    path = dfs_iterative(graph, 'A', 'F')
    if path:
        print(f"迭代DFS: 从A到F的路径是: {' -> '.join(path)}")
        # 注意：这可能不是最短路径

（三）BFS与DFS的比较

特性	广度优先搜索(BFS)	深度优先搜索(DFS)
数据结构	队列(Queue)	栈(Stack)或递归
搜索方式	逐层扩展	一条路径到底
找最短路径	适合（对于边权重相同的图）	不适合
内存使用	可能较高（需要存储每一层的所有节点）	通常较低（只需存储当前路径上的节点）
适用场景	寻找最短路径、社交网络中的人际关系	迷宫问题、拓扑排序、检测环
完整性	总是找到答案（如果存在）	可能陷入无限深的路径

在《算法图解》中，作者提到：

如果你需要找到最短路径，应该使用BFS
如果你只需要知道是否存在路径，或者在解决迷宫类问题时，DFS可能是更好的选择
在处理树结构时，前序、中序和后序遍历实际上都是DFS的不同变种

（四）实际应用示例：文件搜索

以下是一个使用队列实现广度优先搜索(BFS)遍历文件夹的代码示例，与《算法图解》中的方法一致：

from collections import deque
import os

def search_file(root_dir, target_file):
    """
    使用广度优先搜索查找文件
    root_dir: 起始目录
    target_file: 要查找的文件名
    """
    # 创建一个队列并将起始目录加入队列
    search_queue = deque()
    search_queue.append(root_dir)
    
    # 记录已经检查过的目录，避免循环
    searched = set()
    
    while search_queue:  # 只要队列不为空
        # 取出队列中的第一个目录
        current_dir = search_queue.popleft()
        
        # 如果这个目录已经检查过了，就跳过
        if current_dir in searched:
            continue
        
        print(f"正在搜索目录: {current_dir}")
        
        try:
            # 列出当前目录中的所有内容
            items = os.listdir(current_dir)
            
            # 检查每一项
            for item in items:
                full_path = os.path.join(current_dir, item)
                
                # 如果找到了目标文件
                if item == target_file:
                    print(f"找到文件 {target_file} 在路径: {full_path}")
                    return full_path
                
                # 如果是目录，则加入队列以便后续搜索
                if os.path.isdir(full_path):
                    search_queue.append(full_path)
            
            # 将当前目录标记为已搜索
            searched.add(current_dir)
            
        except PermissionError:
            print(f"权限不足，无法访问: {current_dir}")
            searched.add(current_dir)  # 标记为已搜索，避免再次尝试
        except Exception as e:
            print(f"搜索 {current_dir} 时出错: {str(e)}")
            searched.add(current_dir)
    
    # 如果队列为空仍未找到，则返回None
    print(f"未找到文件 {target_file}")
    return None

# 使用示例
if __name__ == "__main__":
    start_directory = "C:/Users/Username/Documents"
    file_to_find = "example.txt"
    print(f"从 {start_directory} 开始搜索 {file_to_find}")
    result = search_file(start_directory, file_to_find)
    
    if result:
        print(f"搜索成功！文件位置: {result}")
    else:
        print("文件未找到。")

下面是使用DFS递归方式搜索文件的示例：

import os

def search_file_dfs(directory, target_file):
    """
    使用DFS递归搜索文件
    """
    print(f"搜索目录: {directory}")
    
    try:
        # 列出目录中的所有内容
        items = os.listdir(directory)
        
        # 先检查当前目录中的文件
        for item in items:
            full_path = os.path.join(directory, item)
            
            # 如果是文件且匹配目标
            if os.path.isfile(full_path) and item == target_file:
                print(f"找到文件 {target_file} 在路径: {full_path}")
                return full_path
        
        # 然后递归搜索子目录
        for item in items:
            full_path = os.path.join(directory, item)
            
            # 如果是目录，递归搜索
            if os.path.isdir(full_path):
                result = search_file_dfs(full_path, target_file)
                if result:
                    return result
        
    except PermissionError:
        print(f"权限不足，无法访问: {directory}")
    except Exception as e:
        print(f"搜索 {directory} 时出错: {str(e)}")
    
    # 在当前目录及其子目录中未找到
    return None

# 使用示例
if __name__ == "__main__":
    start_directory = "C:/Users/Username/Documents"
    file_to_find = "example.txt"
    print(f"使用DFS从 {start_directory} 开始搜索 {file_to_find}")
    result = search_file_dfs(start_directory, file_to_find)
    
    if result:
        print(f"搜索成功！文件位置: {result}")
    else:
        print("文件未找到。")

DFS文件搜索的特点是它会先深入探索一个目录树的分支，直到无法继续为止，然后回溯到上一级目录并尝试另一个分支。这与BFS方式不同，BFS会先搜索当前目录中的所有文件和子目录，然后再搜索这些子目录。

三、二叉树与二叉搜索树

（一）二叉树

二叉树(Binary Tree)是一种特殊的树，其中每个节点最多有两个子节点，通常称为”左子节点”和”右子节点”。

（二）二叉搜索树(BST)

二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树，它具有以下性质：

对于树中的每个节点，其左子树中所有节点的值都小于该节点的值
对于树中的每个节点，其右子树中所有节点的值都大于该节点的值
左右子树也分别是二叉搜索树

这种结构使得BST非常适合进行快速查找、插入和删除操作，平均情况下这些操作的时间复杂度为O(log n)。

（三）BST的基本操作

1. 查找

在BST中查找一个值的过程如下：

从根节点开始
如果当前节点的值等于目标值，则找到了目标
如果目标值小于当前节点的值，则在左子树中继续查找
如果目标值大于当前节点的值，则在右子树中继续查找
如果到达叶节点仍未找到，则目标值不在树中

def search(node, key):
    # 基本情况：节点为空或节点值等于目标值
    if node is None or node.value == key:
        return node
    
    # 如果目标值小于当前节点值，往左子树找
    if key < node.value:
        return search(node.left, key)
    
    # 如果目标值大于当前节点值，往右子树找
    return search(node.right, key)

2. 插入

插入操作遵循类似的逻辑：

从根节点开始
如果树是空的，新节点成为根节点
如果新值小于当前节点的值，则在左子树中寻找插入位置
如果新值大于当前节点的值，则在右子树中寻找插入位置
找到合适的空位置后插入新节点

def insert(node, value):
    # 如果树是空的，创建一个新节点
    if node is None:
        return Node(value)
    
    # 否则，递归向下遍历
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    
    # 如果值已存在，BST通常不允许重复，所以不做任何事
    # 或者可以增加计数器表示重复次数
    
    return node

3. 删除

删除操作比较复杂，因为需要保持BST的性质：

如果目标节点是叶节点，直接删除
如果目标节点只有一个子节点，用子节点替换目标节点
如果目标节点有两个子节点，找到目标节点的中序后继（右子树中的最小值）来替换目标节点，然后删除后继节点

def delete(node, key):
    # 基本情况
    if node is None:
        return node
    
    # 寻找要删除的节点
    if key < node.value:
        node.left = delete(node.left, key)
    elif key > node.value:
        node.right = delete(node.right, key)
    else:
        # 找到了要删除的节点
        
        # 情况1：没有子节点或只有一个子节点
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        
        # 情况2：有两个子节点
        # 找到右子树中的最小值（中序后继）
        node.value = min_value(node.right)
        
        # 删除中序后继
        node.right = delete(node.right, node.value)
    
    return node

def min_value(node):
    current = node
    while current.left is not None:
        current = current.left
    return current.value

4. 遍历

BST的遍历有三种主要方式：

前序遍历(Pre-order): 访问顺序是节点->左子树->右子树
中序遍历(In-order): 访问顺序是左子树->节点->右子树（产生排序的结果）
后序遍历(Post-order): 访问顺序是左子树->右子树->节点

# 中序遍历示例
def in_order_traversal(node):
    if node is not None:
        in_order_traversal(node.left)
        print(node.value)
        in_order_traversal(node.right)

四、BST的性能分析

（一）时间复杂度

对于平衡的BST，主要操作的时间复杂度如下：

查找：O(log n)
插入：O(log n)
删除：O(log n)
遍历：O(n)

然而，在最坏情况下（当树完全不平衡时，例如每个节点只有右子节点，形成链表），这些操作的时间复杂度可能退化为O(n)。

（二）BST的问题：不平衡

BST的主要问题是可能变得不平衡。当数据以特定顺序插入时（例如，按升序或降序），树可能会退化成一个链表，这将导致操作效率从O(log n)降低到O(n)。

例如，如果我们按顺序插入数字1、2、3、4、5，得到的BST会是这样的：

这种情况下，BST失去了其在时间复杂度上的优势。为了解决这个问题，我们需要使用平衡树，这将在下一章中详细讨论。

五、霍夫曼编码

《算法图解》第七章的7.4部分介绍了霍夫曼编码(Huffman Coding)，这是一种重要的无损数据压缩算法，广泛应用于文件压缩、图像压缩(JPEG)和音频压缩(MP3)等领域。霍夫曼编码也是树结构的一个重要应用。

（一）霍夫曼编码的基本原理

霍夫曼编码的核心思想是对出现频率不同的字符使用不同长度的编码，出现频率高的字符使用较短的编码，出现频率低的字符使用较长的编码，从而减少数据的整体存储空间。

与固定长度编码（如ASCII）相比，霍夫曼编码是一种变长编码。例如，在英文文本中，字母’e’出现的频率远高于字母’z’，因此可以给’e’分配一个较短的编码，给’z’分配一个较长的编码。

（二）霍夫曼树的构建过程

霍夫曼编码使用二叉树（称为霍夫曼树）来表示编码方案。构建霍夫曼树的步骤如下：

统计每个字符的出现频率
创建一个叶节点，表示每个字符及其频率
使用优先队列（最小堆）将这些节点按频率排序
循环执行以下操作，直到只剩一个节点：
- 取出频率最低的两个节点
- 创建一个新的内部节点，其左右子节点为这两个节点
- 新节点的频率为其子节点频率之和
- 将新节点插入优先队列
最后剩下的节点就是霍夫曼树的根节点

通过这个过程，出现频率高的字符会更靠近树的根部，因此编码更短。

（三）编码和解码

一旦构建了霍夫曼树，就可以确定每个字符的编码：

从根节点到叶节点的路径决定了字符的编码
通常，向左走记为”0”，向右走记为”1”
每个叶节点代表一个字符，其编码是从根到该叶节点的路径

霍夫曼编码的一个重要特性是前缀性质：任何字符的编码都不是另一个字符编码的前缀。这保证了解码过程的唯一性。

解码过程是编码的逆过程：

从根节点开始
读取编码位，如果是”0”则向左走，如果是”1”则向右走
当到达叶节点时，输出该节点对应的字符，然后重新从根节点开始

（四）Python实现霍夫曼编码

以下是一个简单的霍夫曼编码实现：

import heapq
from collections import defaultdict, Counter

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char  # 字符
        self.freq = freq  # 频率
        self.left = None  # 左子节点
        self.right = None # 右子节点
    
    # 为了在优先队列中比较节点
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text):
    """构建霍夫曼树"""
    # 统计字符频率
    freq = Counter(text)
    
    # 创建叶节点并加入优先队列
    priority_queue = [HuffmanNode(char, frequency) for char, frequency in freq.items()]
    heapq.heapify(priority_queue)
    
    # 构建霍夫曼树
    while len(priority_queue) > 1:
        # 取出两个频率最低的节点
        left = heapq.heappop(priority_queue)
        right = heapq.heappop(priority_queue)
        
        # 创建新的内部节点
        internal_node = HuffmanNode(None, left.freq + right.freq)
        internal_node.left = left
        internal_node.right = right
        
        # 将新节点加入优先队列
        heapq.heappush(priority_queue, internal_node)
    
    # 返回根节点
    return priority_queue[0] if priority_queue else None

def generate_huffman_codes(node, code="", mapping=None):
    """生成霍夫曼编码映射"""
    if mapping is None:
        mapping = {}
    
    # 叶节点，记录字符对应的编码
    if node.char is not None:
        mapping[node.char] = code
        return mapping
    
    # 递归处理左右子树
    if node.left:
        generate_huffman_codes(node.left, code + "0", mapping)
    if node.right:
        generate_huffman_codes(node.right, code + "1", mapping)
    
    return mapping

def huffman_encode(text):
    """使用霍夫曼编码压缩文本"""
    # 处理边界情况
    if not text:
        return "", {}, None
    if len(set(text)) == 1:
        # 只有一种字符的特殊情况
        return "0" * len(text), {text[0]: "0"}, HuffmanNode(text[0], len(text))
    
    # 构建霍夫曼树
    root = build_huffman_tree(text)
    
    # 生成编码映射
    codes = generate_huffman_codes(root)
    
    # 编码文本
    encoded_text = "".join(codes[char] for char in text)
    
    return encoded_text, codes, root

def huffman_decode(encoded_text, root):
    """使用霍夫曼树解码编码文本"""
    if not encoded_text or not root:
        return ""
    
    decoded_text = []
    current_node = root
    
    for bit in encoded_text:
        # 向左走（0）或向右走（1）
        current_node = current_node.left if bit == "0" else current_node.right
        
        # 如果到达叶节点
        if current_node.char is not None:
            decoded_text.append(current_node.char)
            current_node = root  # 重新从根节点开始
    
    return "".join(decoded_text)

# 使用示例
if __name__ == "__main__":
    text = "this is an example for huffman encoding"
    
    # 编码
    encoded_text, codes, tree = huffman_encode(text)
    
    # 计算压缩率
    original_size = len(text) * 8  # 假设每个字符8位
    compressed_size = len(encoded_text)
    compression_ratio = compressed_size / original_size
    
    print(f"原文本: {text}")
    print(f"编码映射: {codes}")
    print(f"编码后: {encoded_text}")
    print(f"原始大小: {original_size} bits")
    print(f"压缩后大小: {compressed_size} bits")
    print(f"压缩率: {compression_ratio:.2%}")
    
    # 解码
    decoded_text = huffman_decode(encoded_text, tree)
    print(f"解码后: {decoded_text}")
    print(f"解码正确: {text == decoded_text}")

（五）霍夫曼编码的应用

霍夫曼编码在现实中有广泛的应用：

文件压缩：霍夫曼编码是许多压缩算法的核心组件，如DEFLATE（被ZIP和PNG使用）
多媒体压缩：JPEG图像格式和MP3音频格式都使用了基于霍夫曼编码的技术
数据传输：减少数据传输量，提高网络通信效率
信息论：霍夫曼编码是熵编码的一个典型例子，接近香农极限

（六）霍夫曼编码的优缺点

优点：

无损压缩，保证数据的完整性
为不同出现频率的符号提供最优的前缀编码
压缩效率高，特别是对于出现频率差异大的符号集

缺点：

需要存储或传输编码表（或霍夫曼树）
编码和解码过程相对复杂
对于动态变化的数据，可能需要不断更新编码表

霍夫曼编码是树结构应用于实际问题的绝佳例子，展示了如何利用树的层次结构和路径特性来解决数据压缩问题。

六、树的实际应用

（一）文件系统

计算机的文件系统通常使用树形结构来组织文件和目录。例如，UNIX/Linux文件系统是一个层次结构，以根目录(/)开始，然后分支到各种目录和子目录。

（二）数据库索引

B树和B+树广泛用于数据库系统的索引结构，以提供高效的数据检索。

（三）编译器

抽象语法树(AST)在编译过程中用于表示程序的语法结构。

（四）网络路由

在网络路由中，前缀树(Trie)被用来存储和搜索IP地址。

（五）机器学习

决策树是一种重要的机器学习算法，用于分类和回归任务。

七、Python实现二叉搜索树

以下是一个简单的BST的Python实现示例：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_recursive(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_recursive(node.right, value)
        # 如果值相等，BST通常不插入重复值
    
    def search(self, value):
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node, value):
        if node is None or node.value == value:
            return node
        
        if value < node.value:
            return self._search_recursive(node.left, value)
        return self._search_recursive(node.right, value)
    
    def in_order_traversal(self):
        result = []
        self._in_order_recursive(self.root, result)
        return result
    
    def _in_order_recursive(self, node, result):
        if node:
            self._in_order_recursive(node.left, result)
            result.append(node.value)
            self._in_order_recursive(node.right, result)

# 使用示例
bst = BinarySearchTree()
values = [5, 3, 7, 2, 4, 6, 8]
for value in values:
    bst.insert(value)

print("中序遍历结果（应该是排序的）:", bst.in_order_traversal())
print("查找值4:", "存在" if bst.search(4) else "不存在")
print("查找值9:", "存在" if bst.search(9) else "不存在")