《Hello 算法》二叉树遍历全解：层序（BFS）与前序/中序/后序（DFS）的队列与递归实现

二叉树遍历（二分木走査）是理解树形结构搜索的第一步，也是后续学习二叉搜索树、堆、回溯等章节的基础。本文以 ja/docs/chapter_tree/binary_tree_traversal.md（及与之同源的 docs/chapter_tree/binary_tree_traversal.md）为核心，结合仓库中的 Python、C++、C 与 Go 等真实代码，讲解广度优先遍历（层序遍历）与深度优先遍历（前序、中序、后序遍历）的概念、实现、复杂度与应用。读完本文，你将能独立写出一棵二叉树四种基本遍历算法，并能说清每种遍历背后的队列或递归原理。

遍历的本质：从线性链表到非线性树

从物理结构看，树是基于链表（指针/引用）组织的数据结构，遍历需要沿指针逐个访问节点；但树又是非线性结构，一个节点同时连接多个子节点，因此无法像单链表那样“一路走到头”，必须借助搜索算法在“分叉”处做出选择。由此，树的遍历被划分为两个大类：

• 层序遍历：属于广度优先遍历（BFS），自上而下、逐层自左向右推进；
• 前序 / 中序 / 后序遍历：属于深度优先遍历（DFS），先沿一条分支走到尽头再回溯。

遍历方式	所属类别	核心思想	典型实现手段
层序遍历（level-order）	广度优先遍历 / BFS	一圈一圈向外、逐层扩展	队列（先进先出）
前序遍历（pre-order）	深度优先遍历 / DFS	先走到尽头再回溯	递归（函数调用栈）
中序遍历（in-order）	深度优先遍历 / DFS	先走到尽头再回溯	递归
后序遍历（post-order）	深度优先遍历 / DFS	先走到尽头再回溯	递归

层序遍历（Level-Order / BFS）：用“队列”逐层推进

层序遍历从树的顶部到底部逐层进行，在同一层内按照从左到右的顺序访问节点。它体现的是一种“同心圆向外扩散”的逐层推进方式，因此本质上就是广度优先遍历，常与图论中的广度优先搜索（BFS）对应。

为什么选择队列？

队列遵循“先进先出”（FIFO），而层序遍历遵循“逐层推进”。用队列保存“下一层待访问的节点”，就能保证：同一层先入队的节点先被取出访问，其子节点（位于下一层）会追加到队尾，从而天然形成自上而下、自左而右的访问次序。

以下为仓库 codes/python/chapter_tree/binary_tree_bfs.py 中 level_order 的实现：

from collections import deque

def level_order(root: TreeNode | None) -> list[int]:
    """层序遍历"""
    # 初始化队列，加入根节点
    queue: deque[TreeNode] = deque()
    queue.append(root)
    # 初始化一个列表，用于保存遍历序列
    res = []
    while queue:
        node: TreeNode = queue.popleft()  # 队列出队
        res.append(node.val)              # 保存节点值
        if node.left is not None:
            queue.append(node.left)       # 左子节点入队
        if node.right is not None:
            queue.append(node.right)      # 右子节点入队
    return res

主流程可拆解为四步：

1. 将根节点入队；
2. 队头节点出队并记录其值；
3. 若出队节点存在左子节点，则左子节点入队；
4. 若存在右子节点，则右子节点入队；重复 2–4 直到队列为空。

从仓库源码可以看出，不同语言对该算法只差“队列”这一基础设施的选择：C++ 用标准库 std::queue<TreeNode*>，Go 用 container/list 的双向链表 list.New()，C 版则在 binary_tree_bfs.c 中手工维护 front/rear 下标模拟环形队列并用 malloc 分配辅助数组，逻辑骨架完全一致。这说明层序遍历的本质是“队列”，与具体语言无关。

复杂度分析

• 时间复杂度为 $O(n)$：每个节点恰好被访问一次，$n$ 为节点总数；
• 空间复杂度为 $O(n)$：最差情况下（满二叉树），在遍历到最底层之前，队列中最多同时存在 $(n+1)/2$ 个节点。

运行与验证

仓库驱动代码使用 [1, 2, 3, 4, 5, 6, 7] 通过 list_to_tree（Python）或 vectorToTree（C++）构造一棵完全二叉树，然后打印层序遍历序列：

# 在仓库 codes/python 目录下运行
python3 chapter_tree/binary_tree_bfs.py

可观察到输出序列为：

初始化二叉树
层序遍历的节点打印序列 =  [1, 2, 3, 4, 5, 6, 7]

前序、中序、后序遍历（DFS）：递归与三个“访问时机”

前序、中序、后序遍历都属于深度优先遍历（DFS），体现的是“先走到尽头，再回溯继续”的策略。一个直观比喻是：DFS 像沿着整棵二叉树的外围走一圈。由于二叉树每个节点都有两条分支，行走路线会在每个节点处“路过”三次，分别对应三种遍历的访问时机：

• 前序遍历：根 → 左子树 → 右子树（首次到达节点时访问）；
• 中序遍历：左子树 → 根 → 右子树（从左子树返回时访问）；
• 后序遍历：左子树 → 右子树 → 根（访问完右子树、即将返回时访问）。

代码实现：三行递归，三种次序

仓库 codes/python/chapter_tree/binary_tree_dfs.py 中，三个函数代码结构完全相同，差别仅在“访问（append）”这行语句的位置：

res = []

def pre_order(root: TreeNode | None):
    """前序遍历：根 -> 左 -> 右"""
    if root is None:
        return
    res.append(root.val)          # 访问根节点
    pre_order(root=root.left)     # 递归左子树
    pre_order(root=root.right)    # 递归右子树

def in_order(root: TreeNode | None):
    """中序遍历：左 -> 根 -> 右"""
    if root is None:
        return
    in_order(root=root.left)      # 递归左子树
    res.append(root.val)          # 访问根节点
    in_order(root=root.right)     # 递归右子树

def post_order(root: TreeNode | None):
    """后序遍历：左 -> 右 -> 根"""
    if root is None:
        return
    post_order(root=root.left)    # 递归左子树
    post_order(root=root.right)   # 递归右子树
    res.append(root.val)          # 访问根节点

三种遍历的“访问代码”只移动了一行，却产生了完全不同的输出次序——这正是“访问时机”决定遍历类型这一事实的最佳证明。仓库中 C 版、Java 版 等 13 种语言实现均遵循同样的递归骨架（C 版以输出数组下标自增代替 append）。

运行与验证

同样用 [1, 2, 3, 4, 5, 6, 7] 构造树并运行：

python3 chapter_tree/binary_tree_dfs.py

三种遍历的打印结果分别为：

前序遍历的节点打印序列 =  [1, 2, 4, 5, 3, 6, 7]
中序遍历的节点打印序列 =  [4, 2, 5, 1, 6, 3, 7]
后序遍历的节点打印序列 =  [4, 5, 2, 6, 7, 3, 1]

递归过程：拆解“递”与“归”

原文档还以前序遍历为例，用 preorder_step1.png 至 preorder_step11.png 共 11 张过程图（见 ja/docs/chapter_tree/binary_tree_traversal.assets/）展示了递归在二叉树上的逐步执行。整个过程可划分为两个方向相反的部分：

1. “递”：开启新的方法调用，程序沿指针进入下一个节点（对应函数入栈）；
2. “归”：函数返回，代表以该节点为根的子树处理完毕（对应函数出栈）。

正是每一次“递”和“归”在栈上交替发生，才让递归可以在无显式指针回溯的情况下回到父节点继续处理另一条分支。

!!! tip 提示 深度优先遍历同样可以不借助递归、用显式栈迭代实现。文档将其留作读者自行研究的题目；从本章代码看，层序用队列、DFS 用递归（隐式栈），两者在结构上互为镜像，理解这一点有助于自行推导迭代版 DFS。

复杂度分析

• 时间复杂度为 $O(n)$：每个节点恰好被访问一次；
• 空间复杂度为 $O(n)$：最差情况下，树退化为链表，递归深度达到 $n$，系统需要占用 $O(n)$ 的栈帧空间。

四种遍历的对照总览

以完全二叉树 [1, 2, 3, 4, 5, 6, 7] 为例，四种遍历结果对比如下：

遍历方式	访问规则	结果序列	依赖结构
层序遍历	逐层，自左向右	1, 2, 3, 4, 5, 6, 7	队列
前序遍历	根→左→右	1, 2, 4, 5, 3, 6, 7	递归栈
中序遍历	左→根→右	4, 2, 5, 1, 6, 3, 7	递归栈
后序遍历	左→右→根	4, 5, 2, 6, 7, 3, 1	递归栈

为什么这些遍历值得掌握：与仓库后续章节的联系

四种遍历并非孤立的代码练习，而是理解仓库后续内容的地基，从源码结构可以清晰看到它们的复用价值：

• 中序遍历与二叉搜索树：对二叉搜索树做中序遍历得到的结果是升序序列，这正是 binary_search_tree.py 以及 二叉树（二叉搜索树）章节 反复强调的性质；
• 前序遍历与回溯搜索：仓库 chapter_backtracking 下的 preorder_traversal_i_compact.py、preorder_traversal_ii_compact.py 等文件，正是用“前序遍历整棵树并在途中按条件筛选路径”的方式来求解搜索问题，可见 DFS 思想从本章延伸到了回溯章节；
• 二叉树的数组表示与层序：在 array_binary_tree.py 中，二叉树被存入数组并按“层序索引”定位父节点与子节点，理解层序遍历有助于建立树的逻辑结构与数组存储之间的对应关系。

若需进一步了解树节点定义与建树工具，可查看 codes/python/modules/tree_node.py；仓库以简体中文为主文档，同时维护日文（ja）、英文（en）、繁体中文（zh-hant）、俄文（ru）等多语言同步版本，本文主题对应源文档见 ja/docs/chapter_tree/binary_tree_traversal.md。