计算机 · 数据结构
树的遍历（前/中/后/层序）
Tree Traversal (pre/in/post/level order)
约 16 分钟 · v19
树的遍历
cs-ds/tree-traversal · COMP2521
0 / 5
1 一句话定义
树的遍历（tree traversal）就是按某种固定顺序，不重不漏地访问树里的每一个节点。
像逛一栋楼，规定一条固定走法：比如"先记下自己这间、再下左楼梯、最后下右楼梯"。同一棵树，走法不同，记录下来的房间清单（访问顺序）就不同。深度优先的三种走法（前/中/后序）只差"记录"动作放在什么时候；层序则是"一层一层横着走"，要排队（队列）。
· 前序（根左右）：50 30 20 40 70 80
· 中序（左根右）：20 30 40 50 70 80 ← 正好升序（这棵恰好是 BST！）
· 后序（左右根）：20 40 30 80 70 50
· 层序（一层层）：50 30 70 20 40 80
2 模型 · 一行代码定遍历顺序
先看下面的代码：前/中/后序三种写法唯一的差别，就是 visit(t) 放在哪一行。点上面切换遍历方式、点 ▶ 单步演示——左边树上节点会按访问顺序标号，右上代码当前行高亮，右下显示调用栈（递归）或队列（层序）。
遍历在代码里怎么写？——只差 visit(t) 的位置
节点定义和二叉树一样；"访问"就是对节点做点事（这里以打印为例）。三种深度优先遍历共用一个递归骨架，把 visit(t) 挪到不同位置，就得到前/中/后序。层序完全不同——不用递归，用一个队列。
// 节点定义同二叉树 struct node { int value; struct node *left, *right; }; // "访问" = 对节点做点事，这里就打印它的值 void visit(struct node *t) { printf("%d ", t->value); } // 三种深度优先遍历：骨架完全一样，只有 visit(t) 的位置不同 ↓ void preorder (node *t){ if(!t) return; visit(t); preorder(t->left); preorder(t->right); } // 根左右 void inorder (node *t){ if(!t) return; inorder(t->left); visit(t); inorder(t->right); } // 左根右 void postorder(node *t){ if(!t) return; postorder(t->left); postorder(t->right); visit(t);} // 左右根
记忆口诀："前/中/后"说的就是"根"被访问的时机——前序＝先访问根，中序＝中间访问根，后序＝最后访问根。"左在右前"对三者都成立。层序请在下面切到「层序」看它怎么用队列横着走。
遍历演示器
当前遍历的代码（当前行高亮）
递归调用栈
提示
选一种遍历方式，点 ▶ 播放或"单步"，看节点按访问顺序被标号。
3 核心要点 · 4 句人话记住四种遍历
三种深度优先（前/中/后）只差一句话；层序是另一套（队列）。
① 前序 Preorder · 根左右
一句话：先盖章再下楼——每到一个节点，先访问它自己，再去左、再去右。
访问顺序：根 → 左子树 → 右子树。常用于复制/序列化一棵树（先建根再建孩子）。示例树：50 30 20 40 70 80。
visit(t); ← 先访问根
preorder(t->left);
preorder(t->right);
② 中序 Inorder · 左根右
一句话：左边走完才盖章。对 BST 来说，中序遍历的结果正好是从小到大排好序的！
访问顺序：左子树 → 根 → 右子树。BST 的中序 = 升序序列，这是考试爱考的性质。示例树：20 30 40 50 70 80（升序）。
inorder(t->left);
visit(t); ← 中间访问根
inorder(t->right);
③ 后序 Postorder · 左右根
一句话：孩子都处理完，最后才轮到自己。要"先算/先释放孩子"的事都用它。
访问顺序：左子树 → 右子树 → 根。求树高、释放整棵树（free）、算子树聚合值都靠后序——必须先有孩子的结果。示例树：20 40 30 80 70 50。
postorder(t->left);
postorder(t->right);
visit(t); ← 最后访问根
④ 层序 Level-order · 用队列
一句话：一层一层横着走，不是递归——靠一个队列：出队就访问、再把孩子排到队尾。
从上到下、每层从左到右。实现是 BFS：根入队 → 反复"出队访问 + 孩子入队"。用栈会变成深度优先，不是层序！示例树：50 30 70 20 40 80。
enqueue(根);
while (队列非空) {
n = dequeue(); visit(n);
入队 n 的左、右孩子;
}
4 错误实验室 · 点一下亲眼看 bug
遍历最常踩这几个坑。点击卡片，下面控制台模拟程序输出 / 段错误。
① visit 放错位置
想要前序，却把 visit(t) 写在两次递归之间 → 实际是中序
② 层序用了栈
层序应该用队列；用栈会变成深度优先，顺序全错
③ 漏写空子树基准
没有 if(t==NULL) return → 递归到叶子的孩子时解引用空指针
// 点击上方任一卡片，查看错误代码与运行效果
$ ./a.out
（等待运行...）
5 即时小测 · 5 题 + 动手例题
都用上面那棵示例树。先在脑子里走一遍，再点选项对答案。最后到练习系统亲手写遍历。
去做例题：树的遍历 · 前/中/后序
去做例题
读完这节，你应该明白：
遍历就是给"访问每个节点"定一个固定顺序。深度优先的前/中/后序共用同一套递归，唯一差别是 visit(t) 写在哪一步——先访问根=前序、中间=中序、最后=后序；层序则换一套思路、用队列一层层横着走。为什么要分这么多种？因为用途不同：复制树用前序、要有序输出（BST）用中序、求树高 / 释放整棵树用后序、按层处理用层序。下一站就是把这套遍历用到具体结构上 ↓