13.3.4 二叉树的遍历

遍历是从树的某个节点出发，按某种规则访问每个节点一次且仅一次。二叉树遍历的本质是递归：一棵树可以拆成“根、左子树、右子树”，每棵子树又按同样规则处理。

四种遍历

遍历方式	顺序	记忆
先序/前序	根 -> 左 -> 右	根在前
中序	左 -> 根 -> 右	根在中间
后序	左 -> 右 -> 根	根在后
层序	从上到下、从左到右	按层访问

“前、中、后”说的是根节点在三个部分中的位置，左子树永远在右子树之前。

遍历的递归结构

flowchart TD
  T["一棵二叉树"] --> R["根"]
  T --> L["左子树"]
  T --> Right["右子树"]
  Pre["先序"] --> PR["访问根"]
  PR --> PL["遍历左子树"]
  PL --> PRight["遍历右子树"]
  In["中序"] --> IL["遍历左子树"]
  IL --> IR["访问根"]
  IR --> IRight["遍历右子树"]
  Post["后序"] --> PoL["遍历左子树"]
  PoL --> PoR["遍历右子树"]
  PoR --> PoRoot["访问根"]

先序遍历怎么读

先序是“根左右”。做题时不要只看整棵树的根，进入左子树后仍然按“根左右”。

步骤：

1. 访问当前根。
2. 对左子树递归执行先序。
3. 对右子树递归执行先序。

课程示例中的前序结果形如：1 2 4 5 7 8 3 6。这个结果不是横着扫出来的，而是每次进入子树继续“根左右”。

中序遍历怎么读

中序是“左根右”。如果节点没有左子树，就访问根；如果有左子树，就先钻到最左侧。

中序遍历在二叉排序树中特别重要，因为它会得到递增序列。

后序遍历怎么读

后序是“左右根”。它的根最后访问，所以常用于表达“先处理子问题，再汇总当前节点”的逻辑。例如删除一棵树时，通常先删除左右子树，再删除根。

层序遍历

层序遍历不递归拆“根左右”，而是按层访问：

1. 访问第 1 层根。
2. 访问第 2 层从左到右的节点。
3. 继续访问下一层。

实现时通常使用队列：根入队，出队访问后把左右孩子入队。

遍历序列还原二叉树

已知序列	能否唯一确定二叉树	原因
先序 + 中序	可以	先序定根，中序分左右
后序 + 中序	可以	后序定根，中序分左右
层序 + 中序	可以	层序找根，中序分左右
先序 + 后序	通常不可以	缺少左右子树划分依据

本节例题

单选

二叉树先序遍历的访问顺序是：

A根、左、右B左、根、右C左、右、根D从上到下、从左到右

自查清单

1. 能否解释“前中后”为什么说的是根的位置？
2. 能否对每个子树递归套用同一种遍历规则？
3. 能否判断哪些遍历序列组合可以唯一还原二叉树？