二叉树的遍历
三种深度优先遍历（递归）
- 前序遍历（根左右）：先访问根，再遍历左子树，最后遍历右子树
- 中序遍历（左根右）：先遍历左子树，再访问根，最后遍历右子树
- 后序遍历（左右根）：先遍历左子树，再遍历右子树，最后访问根
// 前序遍历
void PreOrder(BiTree T) {
if (T != NULL) {
visit(T); // 访问根结点
PreOrder(T->lchild); // 遍历左子树
PreOrder(T->rchild); // 遍历右子树
}
}
// 中序遍历
void InOrder(BiTree T) {
if (T != NULL) {
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
// 后序遍历
void PostOrder(BiTree T) {
if (T != NULL) {
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}时间复杂度：（每个结点访问一次）。空间复杂度：最坏 （递归栈深度等于树高，最坏为链状）。
层序遍历
按层次从上到下、从左到右访问，需要借助队列实现：
void LevelOrder(BiTree T) {
InitQueue(Q);
EnQueue(Q, T);
while (!QueueEmpty(Q)) {
DeQueue(Q, p);
visit(p);
if (p->lchild != NULL) EnQueue(Q, p->lchild);
if (p->rchild != NULL) EnQueue(Q, p->rchild);
}
}由遍历序列构造二叉树
- 前序 + 中序：前序确定根，中序划分左右子树，递归构造
- 后序 + 中序：后序确定根（最后一个），中序划分左右子树，递归构造
- 前序 + 后序：不能唯一确定一棵二叉树
习题
习题 1
某二叉树的前序遍历序列为 A、B、C，后序遍历序列为 C、B、A，则中序遍历序列为（ ）
A. A、B、C B. C、B、A C. B、A、C D. 不能唯一确定
答案与解析
答案：D
解析：仅由前序+后序序列不能唯一确定一棵二叉树。例如 A 为根，BC 既可构成 A 的左子树（中序为 B、C、A），也可构成右子树（中序为 A、B、C），无法唯一确定。
习题 2
已知某二叉树的中序遍历序列为 JGDHKBAELIMCF，后序遍历序列为 JGKHDBLMIEFCA，则其前序遍历序列为（ ）
A. ABDGHJKCEFILM B. ABDGJHKCEILMF C. ABDHKGJCEILMF D. ABDGJHKCEIMLF
答案与解析
答案
B
解析
第 1 步：确定根结点。 后序遍历的最后一个元素是整棵树的根，即 A。
第 2 步：用中序序列划分左右子树。 中序遍历为 JGDHKB | A | ELIMCF，所以：
- 左子树中序：
JGDHKB - 右子树中序：
ELIMCF
第 3 步：递归构造左子树。
- 后序序列去掉根 A 后，左子树部分为
JGKHDB（在LMIEFC之前），其最后一个元素B是左子树的根。 - 在左子树中序
JGDHKB中，B右边为空，所以B没有右子树；B左边是JGDHK。 - 继续：
JGDHK对应后序JGKHD，根为D；中序JGDHK中D左边是JG，右边是HK。 JG对应后序JG，根为G；中序JG中G右边是J，所以G的左孩子为空、右孩子为J。前序得到ABDGJ。HK对应后序KH，根为H；中序HK中H左边是K，所以H的左孩子为K、右孩子为空。前序追加得到ABDGJHK。
第 4 步：递归构造右子树。
- 右子树后序为
LMIEFC，最后一个元素C是右子树的根。 - 右子树中序
ELIMCF中，C右边为空，C左边是ELIMF。 ELIMF对应后序LMIEF，根为F；中序ELIMF中F右边是E，F左边是LIM。LIM对应后序LMI，根为I；中序LIM中I左边是L、右边是M。前序追加得到CEILM。- 最后
F的右孩子为E，前序得到CEILMF。
第 5 步：合并前序序列。
前序遍历 = 根 + 左子树前序 + 右子树前序 = A + BDGJHK + CEILMF = ABDGJHKCEILMF，即选项 B。
习题 3
二叉树的前序、中序、后序遍历顺序分别是什么？
答案与解析
前序（根左右）：先访问根，再遍历左子树，最后遍历右子树。
中序（左根右）：先遍历左子树，再访问根，最后遍历右子树。
后序（左右根）：先遍历左子树，再遍历右子树，最后访问根。
三者的区别在于”访问根结点”的时机：前序最先访问根，中序在中间，后序最后。