外观
4.8 二叉树的遍历
三种顺序从哪来
第4章开头问过:层层嵌套的数据,怎么走遍?
线性表一个接一个,从头走到尾就行。二叉树会分叉:A下面有B、C两条路,走了B这边,C那边还得回头再走。所以要先约定一个顺序。
按某个顺序,把每个结点访问一次,而且只访问一次,叫遍历。访问可以是打印、比较、求和,这里就是写下它的名字。
本节问题4.5节那棵二叉树有A、B、C、D、G五个结点。怎样把每个结点都走到,而且只走一次?写下来是什么序列?
顺序从哪来?回到4.5节的递归定义:
一棵二叉树是三样东西。根,左子树,右子树。走遍整棵树,就是把这三样都走遍。
根有三个位置。三样东西排先后,约定左子树在右子树前面。根只剩三个位置:最前、中间、最后。
子树也照这个顺序。左子树、右子树本身又是二叉树,照同一个顺序走。走到空树,什么也不做,直接回来。
根在最前,叫先序遍历;根在中间,叫中序遍历;根在最后,叫后序遍历。三个名字说的,都是根的位置。
学完这一节,你能写出一棵二叉树的三种遍历序列,用递归函数实现它们,还能说出每种顺序适合做什么。
先序遍历
先序遍历:二叉树是空的,什么也不做;否则先访问根,再先序遍历左子树,最后先序遍历右子树。
在这棵树上一步一步走。虚线框是正在走的子树,结点旁的数字是第几个写下的:
访问A。整棵树不空,先访问根,写下A。
走A的左子树,写下B。左子树以B为根。它也是一棵二叉树,也先访问根,写下B。
走B的左子树,写下D。只有D,写下D。D的两棵子树都是空的,什么也不做。回到B,B的右子树也是空的。B这棵走完了,回到A。
走A的右子树,写下C。右子树以C为根,先访问根,写下C。C的左子树是空的。
走C的右子树,写下G。只有G,写下G。回到C,再回到A,整棵树走完。
先序序列是ABDCG。每到一棵子树,先写下它的根,再进左边,最后进右边。
中序遍历
中序遍历:二叉树是空的,什么也不做;否则先中序遍历左子树,再访问根,最后中序遍历右子树。
和先序比,只是访问根挪到了两棵子树中间。走的路线一样,差别在根要等:左子树走完,才轮到它。
A和B先等着。到A,先走左子树,A等着。到B,又先走B的左子树,B也等着。
最先写下D。D的左子树是空的,轮到D,写下D。D的右子树也是空的。
回到B,写下B。B的左子树走完了,轮到B。B的右子树是空的。
回到A,写下A。A的左子树走完了,轮到A。
右子树同理。C的左子树是空的,先写下C;再走C的右子树,写下G。
中序序列是DBACG。根A正好站在中间:左边的D、B是左子树,右边的C、G是右子树。
后序遍历
后序遍历:二叉树是空的,什么也不做;否则先后序遍历左子树,再后序遍历右子树,最后访问根。
根挪到了最后。两棵子树都走完,才轮到它:
一路往左,先写下D。A等着,B等着。D的两棵子树都是空的,写下D。
B的两棵子树都走完了。B的右子树是空的,两棵都走完,写下B。
A还要等右子树。回到A,右子树还没走。到C,C也等着:它的左子树是空的,右子树是G。先写下G,再写下C。
最后写下A。两棵子树都走完了,轮到根。
后序序列是DBGCA。把三个序列放在一起验算:
每个结点各一次。三个序列都是5个字母,A、B、C、D、G各出现一次。
根在哪里。先序的第一个是根A,后序的最后一个是根A。中序里,A把左子树和右子树分在两边。
回到本节问题。三种顺序都能把每个结点走到,而且只走一次。写下来,先序是ABDCG,中序是DBACG,后序是DBGCA。
写成函数
遍历的规则本身就是递归的,写成函数也是递归的。用4.7节的二叉链表,访问就是打印结点的值:
c
void PreOrder(BiTree T) {
if (T == NULL) return; /* 空树:什么也不做 */
printf("%c", T->data); /* 访问根 */
PreOrder(T->lchild); /* 先序遍历左子树 */
PreOrder(T->rchild); /* 先序遍历右子树 */
}
void InOrder(BiTree T) {
if (T == NULL) return;
InOrder(T->lchild);
printf("%c", T->data); /* 访问根:挪到两棵子树中间 */
InOrder(T->rchild);
}
void PostOrder(BiTree T) {
if (T == NULL) return;
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c", T->data); /* 访问根:挪到最后 */
}三个函数只差访问根的那一行放在哪,和第一页根的三个位置一一对应。
换个角度看同一件事。每个结点在函数里都要经过三个时刻:刚进来,左子树刚走完,右子树也走完。printf放在第一个时刻是先序,放在第二个是中序,放在第三个是后序。
调用PreOrder(T)的过程,就是先序遍历那一页一步一步走的过程。PreOrder拿到A,打印A,再调用自己去走B那棵。走到D的孩子,参数是NULL,函数立刻返回,这就是"空树什么也不做"。每一次返回,就是那一页里的"回到B""回到A"。这是3.8节的递和归。
要多少时间和空间。每个结点调用一次,4.7节数过的n + 1个空指针也各调用一次,一共2n + 1次,时间是O(n)。递归最深时,从根到当前结点一路上的调用都还没返回,深度不超过树的高度h,空间是O(h)。最坏排成一条链,h等于n。
三种顺序各有用处。用哪一种,看处理一个结点时,要它的子树先做完,还是后做:
后序:先做完孩子,再做自己。释放整棵树必须用后序:先释放两棵子树,最后释放根。要是先释放根,它的两个指针跟着没了,孩子再也找不到。
先序:先做自己,再做孩子。比如把一棵树一行一个结点打印出来,孩子缩进在双亲下面。双亲要出现在它的孩子前面,就用先序。
中序:左边、自己、右边。后面讲二叉排序树时会看到:每个结点左边的都比它小,右边的都比它大。中序走一遍,正好从小到大。
完整程序搭出4.5节那棵树,打印三种序列,最后用后序释放:
c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void PreOrder(BiTree T) {
if (T == NULL) return; /* 空树:什么也不做 */
printf("%c", T->data); /* 访问根 */
PreOrder(T->lchild); /* 先序遍历左子树 */
PreOrder(T->rchild); /* 先序遍历右子树 */
}
void InOrder(BiTree T) {
if (T == NULL) return;
InOrder(T->lchild);
printf("%c", T->data); /* 访问根:挪到两棵子树中间 */
InOrder(T->rchild);
}
void PostOrder(BiTree T) {
if (T == NULL) return;
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c", T->data); /* 访问根:挪到最后 */
}
/* 释放也是后序:先释放两棵子树,再释放根 */
void Destroy(BiTree T) {
if (T == NULL) return;
Destroy(T->lchild);
Destroy(T->rchild);
free(T);
}
int main(void) {
/* 搭出4.5节那棵树,做法和4.7节一样 */
BiTree T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = 'A';
T->lchild = NULL;
T->rchild = NULL;
BiTNode *b = (BiTNode *)malloc(sizeof(BiTNode));
b->data = 'B';
b->lchild = NULL;
b->rchild = NULL;
T->lchild = b;
BiTNode *c = (BiTNode *)malloc(sizeof(BiTNode));
c->data = 'C';
c->lchild = NULL;
c->rchild = NULL;
T->rchild = c;
BiTNode *d = (BiTNode *)malloc(sizeof(BiTNode));
d->data = 'D';
d->lchild = NULL;
d->rchild = NULL;
b->lchild = d;
BiTNode *g = (BiTNode *)malloc(sizeof(BiTNode));
g->data = 'G';
g->lchild = NULL;
g->rchild = NULL;
c->rchild = g;
printf("先序:");
PreOrder(T);
printf("\n中序:");
InOrder(T);
printf("\n后序:");
PostOrder(T);
printf("\n");
Destroy(T);
return 0;
}text
先序:ABDCG
中序:DBACG
后序:DBGCA例题:6个结点的完全二叉树
题目写出4.6节那棵6个结点的完全二叉树的先序、中序、后序序列。
分析。按规则,每棵子树都照同一个顺序走。这棵树的根是A,左子树以B为根,右子树以C为根。
- 先序:根、左、右。先写A;再走左子树,先写B,再写D、E;最后走右子树,先写C,再写F:ABDECF。
- 中序:左、根、右。左子树写成DBE,再写A。右子树C只有左孩子F,写成FC:DBEAFC。
- 后序:左、右、根。左子树写成DEB,右子树写成FC,最后写A:DEBFCA。
- 核对。先序第一个、后序最后一个都是根A。中序里A左边的DBE,正好是以B为根的左子树;右边的FC,是以C为根的右子树。
答案先序ABDECF,中序DBEAFC,后序DEBFCA。
练习1:写出三种序列
填空
写出这棵二叉树的三种遍历序列:
- 先序:
- 中序:
- 后序:
D是B的右孩子,中序里D要排在B后面:BDAECF。ABCDEF是一层一层读出来的,不是这三种里的任何一种。
练习2:先序和中序一样的二叉树
单选
一棵非空二叉树,先序序列和中序序列完全相同。它一定是什么样的?
A
每个结点都没有左孩子
先序是根、左、右,中序是左、根、右。两者一样,每棵子树里根前面都不能有左子树。
B
每个结点都没有右孩子
这样的树,中序和后序一样:左、根和左、根,右子树都是空的。
C
只有一个结点
只有一个结点时确实一样,可是一条只往右下走的链也一样,不一定只有一个结点。
D
是满二叉树
满二叉树里根有左子树,先序先写根,中序先写左子树,第一个就不同。
用根的位置去想:先序和中序只差根和左子树谁先。
练习3:释放一棵二叉树用哪种顺序?
单选
用递归释放一棵用二叉链表存的二叉树,每个结点都要free一次。应该按哪种顺序释放?
A
先序:先释放根,再释放左子树、右子树
根释放以后,它的lchild、rchild不能再读,两棵子树都找不到了。
B
中序:先释放左子树,再释放根,最后释放右子树
释放根的时候,右子树还没释放,根一没,右子树就找不到了。
C
后序:先释放左子树、右子树,最后释放根
两棵子树都释放完,根的两个指针已经用不着了,这时再释放根。
D
哪种都可以,反正每个结点都要释放一次
顺序不对,有的结点根本走不到,就漏掉了。
释放一个结点之前,先想一想:它的指针还要不要用。
到这里你有了遍历:按某个顺序把每个结点访问一次,而且只访问一次。一棵二叉树是根、左子树、右子树,约定先左后右,根放在最前、中间、最后,就是先序、中序、后序。递归函数只差访问根的那一行放在哪,时间O(n),空间O(h)。先做自己再做孩子用先序,先做完孩子再做自己用后序,释放整棵树就是后序。下一步遍历是每到一个结点做一件事。要是想要一个数,比如整棵树有几个结点、有多高,就要让子树把答案带回来。