第 29 课 - 树的遍历

学习目标

理解并区分三种深度优先遍历（DFS）策略：前序、中序、后序遍历。
掌握使用递归和迭代（栈）方法实现二叉树的深度优先遍历。
理解并实现广度优先遍历（BFS，即层序遍历）策略。
能够根据实际需求（如打印结构、序列化）选择合适的遍历算法。

核心概念

树的遍历是指按照某种顺序，系统地访问树中的每一个节点恰好一次。这就像探索一座建筑（树），你需要决定是一路走到最深处再回头（深度优先），还是逐层检查每个房间（广度优先）。对于二叉树，主要有两种遍历框架：

深度优先遍历：优先向树的深处探索。主要有三种变体，区别在于访问“根”节点的时机：
- 前序遍历：根 → 左 → 右。常用于复制或序列化树结构。
- 中序遍历：左 → 根 → 右。对于二叉搜索树，会得到一个有序序列。
- 后序遍历：左 → 右 → 根。常用于计算目录大小、表达式求值等。
广度优先遍历：逐层从上到下、从左到右访问。也叫层序遍历，常用于查找最短路径或按层处理数据。

代码示例

以下示例使用 Python 实现。首先定义一个简单的二叉树节点。

# 定义二叉树节点
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 创建一个示例二叉树
#        1
#       / \
#      2   3
#     / \   \
#    4   5   6
def build_sample_tree():
    node4 = TreeNode(4)
    node5 = TreeNode(5)
    node2 = TreeNode(2, node4, node5)
    node6 = TreeNode(6)
    node3 = TreeNode(3, None, node6)
    root = TreeNode(1, node2, node3)
    return root

深度优先遍历 - 递归实现（直观）

递归实现非常简洁，遵循“根”的访问顺序即可。

def preorder_recursive(root):
    """前序遍历（递归）"""
    if root is None:
        return []
    # 根 -> 左 -> 右
    return [root.val] + preorder_recursive(root.left) + preorder_recursive(root.left)

def inorder_recursive(root):
    """中序遍历（递归）"""
    if root is None:
        return []
    # 左 -> 根 -> 右
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)

def postorder_recursive(root):
    """后序遍历（递归）"""
    if root is None:
        return []
    # 左 -> 右 -> 根
    return postorder_recursive(root.left) + postorder_recursive(root.right) + [root.val]

# 测试递归遍历
root = build_sample_tree()
print("前序遍历 (递归):", preorder_recursive(root))   # 输出: [1, 2, 4, 5, 3, 6]
print("中序遍历 (递归):", inorder_recursive(root))    # 输出: [4, 2, 5, 1, 3, 6]
print("后序遍历 (递归):", postorder_recursive(root))  # 输出: [4, 5, 2, 6, 3, 1]

深度优先遍历 - 迭代实现（使用栈）

递归本质上使用了系统栈，我们也可以用显式的栈来模拟，这在某些场景（如控制栈大小）更高效。

def preorder_iterative(root):
    """前序遍历（迭代）"""
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 先压入右子节点，再压入左子节点（栈是后进先出）
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

def inorder_iterative(root):
    """中序遍历（迭代）"""
    stack, result, curr = [], [], root
    while stack or curr:
        # 不断向左走，将沿途节点压栈
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val) # 访问节点
        curr = curr.right       # 转向右子树
    return result

def postorder_iterative(root):
    """后序遍历（迭代，较复杂）"""
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 先压入左子节点，再压入右子节点
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    # 最后将结果反转，得到“左右根”的逆序，即“左右根”
    return result[::-1]

# 测试迭代遍历
print("前序遍历 (迭代):", preorder_iterative(root))   # 输出: [1, 2, 4, 5, 3, 6]
print("中序遍历 (迭代):", inorder_iterative(root))    # 输出: [4, 2, 5, 1, 3, 6]
print("后序遍历 (迭代):", postorder_iterative(root))  # 输出: [4, 5, 2, 6, 3, 1]

广度优先遍历（层序遍历 - 使用队列）

层序遍历需要借助队列来存储下一层待访问的节点。

from collections import deque

def level_order_traversal(root):
    """广度/层序遍历"""
    if not root:
        return []
    queue = deque([root])
    result = []
    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

# 测试层序遍历
print("层序遍历:", level_order_traversal(root)) # 输出: [[1], [2, 3], [4, 5, 6]]

实践练习

基础题：给定以下二叉树，请写出它的前序、中序、后序和层序遍历结果。
```
    A
   / \
  B   C
   \   \
    D   E
```
进阶题：使用迭代（栈） 方法，实现二叉树的后序遍历。尝试理解并写出代码，参考上文中序遍历的迭代逻辑。
应用思考：在二叉搜索树（BST）中，哪种遍历方法可以得到一个有序的序列？为什么？

常见错误

递归终止条件遗漏：递归函数忘记处理 root is None 的情况，会导致无限递归或空指针错误。
迭代中栈/队列顺序错误：
- 前序迭代时，错误地先压左子节点后压右子节点，导致访问顺序错误。
- 后序迭代的反转法容易忘记最后一步 .reverse() 或 [::-1]。
混淆遍历顺序：例如，在前序递归中错误地写成 [root.val] + inorder_recursive(root.left) + ...。牢记口诀：“前根后”、“左根右”、“左右根”。
层序遍历结果格式错误：常见的错误是直接输出一维列表 [1, 2, 3, 4, 5, 6]，而题目或需求通常要求按层输出，即 [[1], [2,3], [4,5,6]]。

小结

在本课中，我们系统学习了二叉树的两大类、四种遍历方法：

深度优先遍历（DFS）：利用递归或栈实现。
- 前序（根左右）：结构优先，用于序列化。
- 中序（左根右）：顺序优先，BST中可得到有序序列。
- 后序（左右根）：依赖子节点信息优先，用于计算。
广度优先遍历（BFS）：利用队列实现，称为层序遍历，按层级处理数据。

理解这些遍历模式是操作和分析树结构的基础，它们在后续学习更高级的树（如二叉搜索树、AVL树）和图算法中至关重要。掌握递归和迭代两种实现方式，能加深你对树结构和算法思想的理解。

练习编辑器

rust