企业官网建设流程全解析

hello-algo：二叉树遍历详解——BFS 层序遍历与 DFS 前中后序遍历的两种体系

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

树是一种基于链表的物理结构，却是一种非线性的逻辑结构，因此无法像链表那样从头节点一路指针走到底，而必须借助搜索算法来系统性地访问每个节点。本文基于 hello-algo 仓库中 二叉树遍历文档 展开，完整讲解二叉树两大遍历体系——广度优先的层序遍历（BFS）与深度优先的前序/中序/后序遍历（DFS），并对照仓库中 Python、C++、Go 等多语言源码，给出可复制实现的代码、输出序列与复杂度结论，帮助读者真正掌握二叉树遍历的原理与工程实现。

一、遍历为什么比链表更难

从物理结构的角度看，树是一种基于链表的数据结构，遍历方式是顺着指针逐个访问节点。但树是非线性结构，一个节点可能分叉出左右两个子树，若只是“走到下一个指针”就会遗漏分支，因此遍历必须借助搜索算法来实现：

• 广度优先搜索（breadth-first search, BFS）：体现“一圈一圈向外扩展”的逐层推进思路，对应层序遍历；
• 深度优先搜索（depth-first search, DFS）：体现“先走到尽头，再回溯继续”的深入思路，对应前序、中序、后序遍历。

下面分别结合 hello-algo 仓库源码讲解这两套遍历的算法与实现。

二、层序遍历（BFS）

层序遍历（level-order traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。如上图中那棵 7 节点树，层序访问顺序为1, 2, 3, 4, 5, 6, 7：先第 1 层的 1，再第 2 层的 2、3，最后第 3 层的 4、5、6、7。

2.1 算法思路

广度优先遍历通常借助队列实现：队列遵循“先进先出”的规则，而广度优先遍历遵循“逐层推进”的规则，两者背后的思想一致——当前层的节点先出队处理，其子节点入队等待下一轮，天然保证了“逐层、从左到右”的访问次序。

2.2 代码实现（Python）

仓库中 binary_tree_bfs.py 的level_order函数是标准实现：

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. 出队即“访问”：把node.val追加进结果列表；
3. 左、右子节点按左前右后的顺序入队，保证同一层从左到右的次序。

驱动代码中使用了list_to_tree(arr=[1, 2, 3, 4, 5, 6, 7])从数组直接构造一棵满二叉树，该工具函数定义在 tree_node.py，其内部通过递归按“下标i的左子节点在2*i+1、右子节点在2*i+2”的数组表示规则反序列化建树。

2.3 多语言实现对照

仓库提供了与 Python 版逻辑完全一致的多语言实现，可以互相印证：

• C++：binary_tree_bfs.cpp 的levelOrder使用std::queue<TreeNode*>与std::vector<int>，通过queue.front()/queue.pop()出队访问；
• Go：binary_tree_bfs.go 的levelOrder使用标准库container/list的双向链表作队列，queue.Remove(queue.Front())出队；
• 此外，Java、C#、JavaScript、TypeScript、Kotlin、Swift、Rust、Ruby 等版本也分别在 codes/java/chapter_tree/、codes/csharp/、codes/rust/ 等目录下提供了对应的levelOrder实现，核心步骤（入队根节点 → 出队访问 → 左右子节点入队）完全一致。

2.4 复杂度分析

• 时间复杂度为 O(n)：所有节点被访问一次，使用 O(n) 时间，其中 n 为节点数量。
• 空间复杂度为 O(n)：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 (n+1)/2 个节点（即倒数一层的全部节点加上最后一层的一半），占用 O(n) 空间。

三、前序、中序、后序遍历（DFS）

对应层序遍历，前序、中序和后序遍历都属于深度优先遍历，体现“先走到尽头，再回溯继续”的遍历方式。

3.1 核心原理：绕树一圈，三个访问位置

深度优先遍历就像是绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历：

• 前序：进入节点时（访问左子树之前）记录；
• 中序：左子树访问完、即将访问右子树时记录；
• 后序：左右子树都访问完、函数返回前记录。

以下图（第 4 步）为例，虚线表示“已走过的路径”，实线箭头表示“即将深入的方向”。图中节点 1、2、4 已经被访问（前序序列为1, 2, 4），搜索路径正沿虚线向上回溯，准备进入节点 4 的右兄弟节点 5。

以这棵 7 节点满二叉树为例，三种深度优先遍历的输出序列分别为（与上图标注一致）：

一个值得注意的细节：前序序列恰好与层序序列不同但都以 1 开头，而中序、后序序列首元素都是最左边的节点 4——这与“沿左子树一路深入”的搜索方向完全吻合。

3.2 代码实现（Python）

深度优先搜索通常基于递归实现。仓库 binary_tree_dfs.py 给出了三个函数，它们结构几乎完全相同，唯一的区别就是res.append(root.val)这一“访问”语句的位置：

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)

实现要点：

1. 递归终止条件：root is None时直接返回，保证空子树不会触发越界访问；
2. 三种遍历的差异仅在访问语句的位置：放在两个递归调用之前即前序、夹在中间即中序、放在之后即后序；
3. 从源码结构看，res是一个模块级共享列表，驱动代码中通过res.clear()在三种遍历之间复用（见 binary_tree_dfs.py 的 main 部分），避免每次遍历都新建列表。

3.3 递归的“递”与“归”

前序遍历的递归过程可分为两个逆向的部分：

1. “递”：开启新方法，程序沿指针向下推进，访问下一个节点；
2. “归”：函数返回，代表当前节点已经访问完毕，回溯到父节点继续处理右子树。

文档原文档配有 11 步动画序列（preorder_step1.png~preorder_step11.png，位于 binary_tree_traversal.assets），完整演示了从根节点出发、一路“递”到节点 4，再“归”回并逐个处理 5、3、6、7 的全过程。读者可以对照动画理解递归栈帧的压入与弹出。

3.4 多语言实现对照

• C++：binary_tree_dfs.cpp 中同样提供preOrder、inOrder、postOrder三个函数，使用文件作用域的全局vector<int> vec保存序列，main 中每次调用前执行vec.clear()；
• 其余语言（Java、C#、Go、JavaScript、TypeScript、Kotlin、Swift、Rust 等）在各自chapter_tree目录下均有等价实现，如 codes/java/chapter_tree/binary_tree_dfs.java、codes/go/chapter_tree/。

值得指出的是，原文档提示深度优先搜索也可以基于迭代实现（用显式栈模拟递归），有兴趣的读者可以在仓库的其他章节代码中继续研究。

3.5 复杂度分析

• 时间复杂度为 O(n)：所有节点被访问一次，使用 O(n) 时间；
• 空间复杂度为 O(n)：在最差情况下，即树退化为链表（每个节点只有一个子节点）时，递归深度达到 n，系统占用 O(n) 栈帧空间。

与层序遍历的空间开销来源不同：BFS 的 O(n) 来自队列，DFS 的 O(n) 来自递归调用栈。

四、两种遍历体系对比总结

五、小结

hello-algo 的 二叉树遍历文档 通过“外围绕一圈”的视角把四种遍历统一为两个体系：层序遍历用队列逐层扩展，前中后序遍历用递归深入并回溯，三者差别只是“访问节点”这一动作在递归中的位置。仓库中各语言的实现代码（level_order/levelOrder与pre_order/in_order/post_order）与文档描述一一对应，且驱动代码统一使用list_to_tree([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四组输出序列，是理解二叉树遍历原理与工程落地的完整材料。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo