二叉树的遍历

二叉树的遍历是指按照某种顺序访问树中的所有节点，且每个节点仅访问一次的过程。遍历是二叉树的基础操作之一，广泛应用于数据检索、表达式求值、文件系统管理等场景。根据访问节点的顺序不同，主要分为深度优先遍历（DFS）和广度优先遍历（BFS）两大类。

深度优先遍历（DFS）

深度优先遍历沿着树的深度遍历节点，尽可能深地搜索树的分支，直到无法继续为止，再回溯到上一层节点。根据访问根节点的时机，分为以下三种方式：

前序遍历（Preorder Traversal）

访问顺序：根节点 → 左子树 → 右子树 常用于复制树结构或生成前缀表达式（如波兰表达式）。

# Python 前序遍历递归实现
def preorder(root):
    if root:
        print(root.val, end=" ")  # 访问根节点
        preorder(root.left)       # 遍历左子树
        preorder(root.right)      # 遍历右子树

# 示例输入与输出
# 二叉树结构：
#      1
#     / \
#    2   3
#   / \
#  4   5
# 输出：1 2 4 5 3

中序遍历（Inorder Traversal）

访问顺序：左子树 → 根节点 → 右子树 对二叉搜索树（BST）使用时，会按升序输出节点值。

// Java 中序遍历递归实现
void inorder(TreeNode root) {
    if (root != null) {
        inorder(root.left);       // 遍历左子树
        System.out.print(root.val + " ");  // 访问根节点
        inorder(root.right);      // 遍历右子树
    }
}

// 示例输入与输出（同上二叉树）
// 输出：4 2 5 1 3

后序遍历（Postorder Traversal）

访问顺序：左子树 → 右子树 → 根节点 常用于删除树或生成后缀表达式（如逆波兰表达式）。

// C++ 后序遍历递归实现
void postorder(Node* root) {
    if (root) {
        postorder(root->left);    // 遍历左子树
        postorder(root->right);   // 遍历右子树
        cout << root->data << " "; // 访问根节点
    }
}

// 示例输入与输出（同上二叉树）
// 输出：4 5 2 3 1

可视化示例

graph TD A((1)) --> B((2)) A --> C((3)) B --> D((4)) B --> E((5))

广度优先遍历（BFS）

广度优先遍历按层次从上到下、从左到右访问节点，通常借助队列实现。

层序遍历（Level Order Traversal）

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# 示例输入与输出（同上二叉树）
# 输出：1 2 3 4 5

非递归实现

递归方法可能引发栈溢出，以下是使用栈的迭代实现：

# Python 前序遍历迭代实现
def preorder_iterative(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            print(node.val, end=" ")
            stack.append(node.right)  # 右子节点先入栈
            stack.append(node.left)   # 左子节点后入栈

实际应用案例

1. 文件系统遍历：目录树本质是N叉树，前序遍历可用于统计文件数量。 2. 表达式求值：中序遍历生成中缀表达式，后序遍历适合计算器实现。 3. DOM树渲染：浏览器使用深度优先遍历渲染HTML节点。

时间复杂度分析

设树有$n$个节点：

• 所有遍历方式的时间复杂度均为$O(n)$
• 空间复杂度：

 * 递归：$O(h)$（$h$为树高，最坏情况$O(n)$）
 * 迭代：$O(n)$

扩展：Morris遍历

一种空间复杂度为$O(1)$的遍历算法，通过临时修改树结构实现（适合内存受限场景）。