二叉树与递归遍历
复习
- 树：用父子关系表示层次结构
- 递归：函数调用自身
- 栈：函数调用靠它保存信息
TL;DR
- 二叉树每个节点最多有两个子节点
- 遍历有前序、中序、后序三种
- 它们的区别在于“访问根”的时机
- 三种遍历都能用递归自然表达
正文
树里最常用的一种，是二叉树（binary tree）：每个节点最多有两个子节点，习惯上叫左孩子和右孩子。
为什么偏偏是“两”？因为它结构规整、操作简单，又足以表达丰富的信息，是后面搜索树、堆等结构的基础。
怎么把树走一遍
要处理一棵树，首先得能系统地访问每个节点，这叫遍历（traversal）。二叉树有三种常见顺序，区别只在于“什么时候访问根节点”：
- 前序遍历：根 → 左 → 右（先访问根）
- 中序遍历：左 → 根 → 右（中间访问根）
- 后序遍历：左 → 右 → 根（最后访问根）
名字里的“前、中、后”，说的正是根的位置。
递归写法有多自然
回想上一章：树是递归结构。遍历的递归写法也就水到渠成。以中序为例：
中序遍历(node)：
如果 node 为空，返回
中序遍历(node 的左孩子)
访问 node
中序遍历(node 的右孩子)
短短几行，含义却清清楚楚：处理左子树、处理自己、处理右子树。 换成前序或后序，只是把“访问 node”那句话挪个位置。如果不用递归，就得自己维护一个栈，代码立刻复杂起来。
它们分别有什么用
三种顺序并非随便定的，各有用途：
- 前序：适合“先处理根”的任务，比如复制整棵树
- 中序：对二叉搜索树来说，能得到有序的序列
- 后序：适合“先处理子节点”的任务，比如释放整棵树
这里先记住中序的那条性质，下一章讲二叉搜索树时它有大用。
此外还有一种“一层一层访问”的顺序，叫层序遍历，它需要用队列来实现——正好用上我们前面学过的队列。
思考题 1
前序、中序、后序遍历的区别是什么？
思考题 2
为什么遍历二叉树时，递归写法特别自然？
小结
知识点
- 二叉树每个节点最多两个子节点
- 前序、中序、后序遍历的区别在于访问根的时机
- 递归遍历与树的递归结构天然契合
- 三种顺序各有适用场景，层序遍历需要队列
参考资料
- Wikipedia(zh)：二叉树：每个节点最多两个子节点的树
- Wikipedia(zh)：树的遍历：前序、中序、后序等访问顺序
思考题答案（仅供参考）
思考题 1
区别在于访问根节点的时机：前序先访问根、再左再右；中序先左、再根、再右；后序先左、再右、最后根。“前、中、后”指的就是根在访问顺序中的位置。
思考题 2
因为二叉树本身是递归结构：每个节点的左、右子树仍是二叉树。因此可以自然地写成“递归处理左子树、处理自己、递归处理右子树”，代码与结构一一对应，简洁清晰。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪