← 目录 / 算法文档 · 模块十一 树与二叉树 / 11.3 二叉树的遍历

11.3　二叉树的遍历

同一棵树，访问顺序可以完全不同——前序、中序、后序三种递归遍历，加上借助队列的层序遍历。

本页目录
① 为什么遍历顺序有讲究

数组和链表是"一条线"，从头走到尾顺序是唯一的。但树是"一对多"的结构——站在某个节点上，下一步是先往左子节点走，还是先往右子节点走，还是先处理完自己再说？不同的选择顺序，会得到完全不同的访问序列。二叉树的遍历，说的就是按什么顺序访问树上的每一个节点，能且仅能访问一次。

本节还是用 11.1 节那棵熟悉的示例树：

1 2 3 4 5 6
下面所有遍历方式，访问的都是这同一棵树，只是访问顺序不同。
② 前序、中序、后序：三选一，选哪一步先访问根节点

前序、中序、后序这三种遍历，都是先处理左子树，再处理右子树（这一点是共同的），唯一的区别是"访问根节点"这个动作插在哪一步：

前序（根 → 左 → 右）
1 1 2 2 3 5 4 3 5 4 6 6
橙色小圆圈里的数字是访问顺序。走法：① 访问 1 → ② 往左走到 2 → ③ 2 还有左子节点 4，先访问 4 → ④ 4 没有子节点了，回头访问 2 的右子节点 5 → ⑤ 2 这边处理完，回到 1，访问右子节点 3 → ⑥ 访问 3 的左子节点 6。得到序列 1 2 4 5 3 6——规律就是"先访问自己，再左子树，再右子树"。
中序（左 → 根 → 右）
1 4 2 2 3 6 4 1 5 3 6 5
走法：① 从 1 出发先往左，一路走到 4（4 没有左子节点了，第一个访问它）→ ② 回到 2，这时候左边处理完了，访问 2 → ③ 访问 2 的右子节点 5 → ④ 2 这一整块都处理完，回到 1，访问 1 → ⑤ 进入右边，一路走到 6，访问它 → ⑥ 回到 3，访问 3。得到序列 4 2 5 1 6 3——规律就是"先左子树，再自己，再右子树"。
后序（左 → 右 → 根）
1 6 2 3 3 5 4 1 5 2 6 4
走法：① 一路往左走到 4，先访问它（还没轮到它的父节点）→ ② 4 没有兄弟节点可看了，回到 2，但 2 还不能访问，先看它的右子节点 5，访问 5 → ③ 2 的左右子节点都访问完了，这才轮到访问 2 → ④ 进入右边，走到 6，访问它 → ⑤ 6 访问完，轮到 3 → ⑥ 左右两边全部处理完，最后才访问根节点 1。得到序列 4 5 2 6 3 1——规律就是"先左子树，再右子树，最后才轮到自己"。
💡
名字里的"前中后"，指的就是"根节点"出现的位置：前序 = 根节点在前面（根左右）；中序 = 根节点在中间（左根右）；后序 = 根节点在后面（左右根）。三种遍历里，左子树永远在右子树之前处理，唯一变化的只是根节点插入的时机。
③ 递归代码：三种遍历只差一行的顺序

这三种遍历的代码结构完全一样，都是"处理左子树、处理右子树、访问根节点"这三个动作的排列组合——写成递归函数后，唯一的区别就是"访问根节点"这一行放在哪个位置：

C++ · 前序 / 中序 / 后序遍历（递归）
1void PreOrder(TreeNode* root) // 前序：根→左→右
2{
3 if (root == nullptr) return; // 递归终止：空节点直接返回
4 cout << root->val << " "; // ① 先访问根
5 PreOrder(root->left); // ② 再递归左子树
6 PreOrder(root->right); // ③ 再递归右子树
7}
8
9void InOrder(TreeNode* root) // 中序：左→根→右
10{
11 if (root == nullptr) return;
12 InOrder(root->left); // ① 先递归左子树
13 cout << root->val << " "; // ② 再访问根
14 InOrder(root->right); // ③ 再递归右子树
15}
16
17void PostOrder(TreeNode* root) // 后序：左→右→根
18{
19 if (root == nullptr) return;
20 PostOrder(root->left); // ① 先递归左子树
21 PostOrder(root->right); // ② 再递归右子树
22 cout << root->val << " "; // ③ 最后访问根
23}
📖
递归终止条件永远是同一句：if (root == nullptr) return;——遇到空节点（比如访问某个只有左子节点的节点的右子节点）就直接返回，不做任何事。这一句保证了递归不会无限往下走，是三种遍历共同的"地基"。
④ 层序遍历：借助队列，按层扩展

前中后序都是"一条路走到底"的思路——一头扎进左子树的最深处，处理完了才往回走。但有时候我们想要的是"一层一层"地访问：先访问根节点，再访问第二层的所有节点，再访问第三层……这种"一条路走到底"和"一层一层扩展"的区别，后面的章节会给它们专门起名字，分别叫 DFS（深度优先）和 BFS（广度优先）——这里不用急着记名字，只要先体会到这是两种完全不同的访问方式就够了。

层序遍历的队列变化过程
初始化
1
根节点先入队
取出 1
1
2
3
访问 1，把它的左子节点 2、右子节点 3 依次入队
取出 2
2
4
5
访问 2，把它的左子节点 4、右子节点 5 入队（3 还在队列里等着）
取出 3
3
6
访问 3，只有左子节点 6，入队（右子节点不存在，跳过）
依次取出
4、5、6
4
5
6
三个都是叶子节点，没有子节点可入队，队列清空，遍历结束
C++ · 层序遍历（借助队列）
1void LevelOrder(TreeNode* root)
2{
3 if (root == nullptr) return; // 空树直接返回
4
5 queue<TreeNode*> q;
6 q.push(root); // 根节点先入队
7
8 while (!q.empty())
9 {
10 TreeNode* cur = q.front(); // 取出队头
11 q.pop();
12 cout << cur->val << " "; // 访问当前节点
13
14 if (cur->left) q.push(cur->left); // 左子节点存在才入队
15 if (cur->right) q.push(cur->right); // 右子节点存在才入队
16 }
17}
💡
提前预告一下：这种"用队列、一层一层扩展"的访问方式，在图和网格上还有更广泛的应用，后面的章节会正式学到，那时候它有一个专门的名字叫 BFS（广度优先搜索）。到时候回头再看这里的层序遍历，会发现思路完全是一回事——只是"扩展的对象"从"左右两个子节点"变成了"上下左右的邻居格子"。
🎓
拓展：前序 + 中序能唯一还原一棵二叉树。如果同时知道一棵树的前序序列和中序序列，可以唯一确定这棵树长什么样（中序序列里根节点左边的部分就是左子树、右边就是右子树，再结合前序序列里"第一个就是根节点"，可以递归地切分下去）。这是一个很经典的小结论，感兴趣可以自己动手试着用示例树的两个序列反推验证一下。
⑤ 常见陷阱

把本节内容汇总成几条最容易踩坑的规则：

⚠
递归函数忘记写终止条件：如果漏掉 if (root == nullptr) return;，递归会在访问到空节点时继续往下访问 root->left，而空指针没有 left 成员可言，程序会直接崩溃（典型的"空指针解引用"）。
⚠
前中后序记混："访问根节点"插入的位置":建议牢记口诀——前序根节点在前、中序根节点在中、后序根节点在后，而不是死记"先左后右"这种共性（三种遍历这一点都一样，不能用来区分）。
⚠
层序遍历里判断子节点是否存在不能漏：if (cur->left) q.push(cur->left) 这一步的判断不能省略——如果不判断直接 push(cur->left)，遇到不存在的子节点（nullptr）也会入队，后面取出来访问 nullptr->val 同样会崩溃。
🏆
接下来：下一节（11.4）是二叉树最重要的应用之一——二叉搜索树（BST）：给二叉树的每个节点值加上"左小右大"的规则，就能把查找的效率提升到接近二分查找的水平。