二叉树的遍历
- 前序遍历(根左右):先访问根,再遍历左子树,最后遍历右子树
- 中序遍历(左根右):先遍历左子树,再访问根,最后遍历右子树
- 后序遍历(左右根):先遍历左子树,再遍历右子树,最后访问根
// 前序遍历
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. 不能唯一确定
解题思路:
本题考查由前序与后序序列能否唯一确定二叉树。关键在于这两种遍历都无法单独确定根的两棵子树各含哪些结点,必须借助中序序列中根的位置来划分左右子树,因此缺少中序序列时答案不唯一。
详细步骤:
- 前序序列的首元素是根,后序序列的末元素是根,两者的根一致,都为 A。
- 但前序与后序都只给出“根—左—右”和“左—右—根”的次序,无法指出剩余的 B、C 究竟属于左子树还是右子树。
- 例如把 BC 作为 A 的左子树时中序为 B、C、A;把 BC 作为 A 的右子树时中序为 A、B、C。
- 两种不同的二叉树都符合给定的前序与后序序列,故不能唯一确定。
最终答案:
D。
习题 2
已知某二叉树的中序遍历序列为 JGDHKBAELIMCF,后序遍历序列为 JGKHDBLMIEFCA,则其前序遍历序列为( )
A. ABDGHJKCEFILM B. ABDGJHKCEILMF C. ABDHKGJCEILMF D. ABDGJHKCEIMLF
解题思路:
本题已知中序与后序序列,要求前序序列。思路是反复使用“后序末元素为根、中序中根的位置把序列切成左右两半”这一规律,递归确定每棵子树,再把各子树的前序序列拼接起来。
详细步骤:
- 第 1 步:确定根结点。后序遍历的最后一个元素是整棵树的根,即
A。 - 第 2 步:用中序序列划分左右子树。中序遍历为
JGDHKB | A | ELIMCF,所以左子树中序为JGDHKB,右子树中序为ELIMCF。 - 第 3 步:递归构造左子树。后序序列去掉根 A 后,左子树部分为
JGKHDB,其最后一个元素B是左子树的根;在左子树中序JGDHKB中B右边为空,所以B没有右子树,B左边是JGDHK。继续:JGDHK对应后序JGKHD,根为D,中序中D左边是JG、右边是HK;JG对应后序JG,根为G,中序中G右边是J,所以G的左孩子为空、右孩子为J,前序得到ABDGJ;HK对应后序KH,根为H,中序中H左边是K,所以H的左孩子为K、右孩子为空,前序追加得到ABDGJHK。 - 第 4 步:递归构造右子树。右子树后序为
LMIEFC,最后一个元素C是右子树的根;在右子树中序ELIMCF中C右边为空、C左边是ELIMF。ELIMF对应后序LMIEF,根为F,中序中F右边是E、F左边是LIM;LIM对应后序LMI,根为I,中序中I左边是L、右边是M,前序追加得到CEILM;最后F的右孩子为E,前序得到CEILMF。 - 第 5 步:合并前序序列。前序遍历 = 根 + 左子树前序 + 右子树前序 =
A+BDGJHK+CEILMF= ABDGJHKCEILMF,即选项 B。
最终答案:
B(ABDGJHKCEILMF)。
习题 3
二叉树的前序、中序、后序遍历顺序分别是什么?
解题思路:
本题考查二叉树三种深度优先遍历的访问次序。思路是抓住三者唯一的差别——“访问根结点的时机”,其余部分都是“递归地先遍历左子树、再遍历右子树”。
详细步骤:
- 前序遍历(根左右):先访问根结点,再遍历左子树,最后遍历右子树。
- 中序遍历(左根右):先遍历左子树,再访问根结点,最后遍历右子树。
- 后序遍历(左右根):先遍历左子树,再遍历右子树,最后访问根结点。
- 三者的区别只在于访问根结点的时机:前序最先访问根,中序在中间访问根,后序最后访问根。
最终答案:
前序(根左右):先访问根,再遍历左子树,最后遍历右子树。中序(左根右):先遍历左子树,再访问根,最后遍历右子树。后序(左右根):先遍历左子树,再遍历右子树,最后访问根。三者的区别在于访问根结点的时机:前序最先访问根,中序在中间,后序最后。
