6.3遍历二叉树和线索二叉树
? 6.3.1遍历二叉树
? 如果按某条搜索路径巡
访树中每个结点, 使得
每个结点均被访问一次,
而且仅被访问一次 。
A
B
C D
G
E F
先序遍历二叉树的操作定义为：
? 若二叉树为空, 则空操作；
否则
? （ 1） 访问根结点；
? （ 2） 先序遍历左子树；
? （ 3） 先序遍历右子树 。
? A B C D F E G
A
B
C D G
E
F
先序遍历二叉树的递归算法
? Status PreOrderTraverse(BiTree T,Status(*
Visit)(TElemType e)){
? if (T){
? if (Visit(T->data))
? if (PreOrderTraverse(T->lchild,Visit))
? if (PreOrderTraverse(T->rchild,Visit))
? return OK;
? return ERROR;
? }else return OK;
? }//PreOrderTraverse
中序遍历二叉树的操作定义为：
? 若二叉树为空, 则空操作；
否则
? （ 1） 中序遍历左子树；
? （ 2） 访问根结点；
? （ 3） 中序遍历右子树 。
? C B D F A G E
A
B
C D G
E
F
中序遍历二叉树示例
?中序遍历二叉树得,
?a+b*(c-d)-e/f
-
+
a * e
/
-
f
b
dc
中序遍历二叉树的递归算法
? Status InOrderTraverse(BiTree T,Status(*
Visit)(TElemType e)){
if (T){
if (InOrderTraverse(T->lchild,Visit))
if (Visit(T->data))
if (InOrderTraverse(T->rchild,Visit))
? return OK;
return ERROR;
}else return OK;
}//InOrderTraverse
后序遍历二叉树的操作定义为：
? 若二叉树为空, 则空操作；
否则
? （ 1） 后序遍历左子树；
? （ 2） 后序遍历右子树；
? （ 3） 访问根结点 。
? C F D B G E A
A
B
C D G
E
F
后序遍历二叉树的递归算法
? Status PostOrderTraverse(BiTree T,Status(*
Visit)(TElemType e)){
if (T){
if (PostOrderTraverse(T->lchild,Visit))
if (PostOrderTraverse(T->rchild,Visit))
if (Visit(T->data)) return OK;
return ERROR;
}else return OK;
}//PostOrderTraverse
中序遍历二叉树的 非 递归算法
? Status InOrderTraverse(BiTree T,Status(* Visit)
(TElemType e)){
InitStack(S); Push(S,T);
? while(!StackEmpty(S)){
? while(GetTop(S,p) && p)Push(S,p->lchild);
Pop(S,p);
if (!StackEmpty(S)){
Pop(S,p); if (!Visite(p->data)) return ERROR;
? Push(S,p->rchild);
} } return OK;
}//InOrderTraverse
中序遍历二叉树的 非 递归算法
示意图
? C B D F A G E
A
B
C D G
E
F
A
B
C
NULL
S
GetTop<--
p
A
S
Pop
p
? C B D F A
例,已知结点的先序序列和中序
序列,求整棵二叉树。
?先序序列,A B C D E F G
?中序序列,C B E D A F G
A
C
B
E
D
F
G
A
B
C D
E
F
G
A
B
C
F
D
E
G
构造二叉链表表示的二叉树
的递归算法
? Status CreateBiTree(BiTree &T)
?{ scanf(“%c”,&ch);
if (ch==?#?) T=NULL;
? else {
if (!(T=(BiTNode *) malloc(sizeof (BiTNode))))
? exit(OVERFLOW);
T->data = ch ;
? CreateBiTree(T->lchild);
? CreateBiTree(T->rchild);
? }
? return OK;
}//CreateBiTree
构造二叉链表
A
B
C D
G
E F
按下列次序输入字符,
ABC??DE?G??F???
(其中 ?表示空格字符 )
可建立如右图的二叉链表,
6.3.2 线索二叉树
? 遍历是非线性结构的线性化操作
保留遍历过程的顺序信息 -----
? 线索二叉树的表示,
? 若结点有左子树, 则其 LCHILD域指示其左孩子,
否则令 LCHILD域指示其前驱；
? 若结点有右子树, 则其 RCHILD域指示其右孩子,
否则令 RCHILD域指示其后继 。
线索二叉树结点的结构,
? 0 lchild域指示其左孩子
? ltag ={
? 1 lchild域指示其前驱
? 0 rchild域指示其右孩子
? rtag ={
? 1 rchild域指示其后继
? 线索二叉树
? 线索化
? 线索链表
? 线索
datalchild rchildrtagltag
中序线索二叉树
-
+
a * e
/
-
f
b
dc
NILNIL
b
*
11
+
/
f
00
e
中 序 线 索 二 叉 树 中
查找结点的后继和前驱,
? 如何在中序线索二叉树中找结点的后继：
? rtag = 1时, rchild所指的结点即为后继；
? rtag = 0时, 其后继为遍历其右子树时的第一个结点
（ 最左下结点 ） 。
? 如结点, *” 的后继是, c” 。
? 如何在中序线索二叉树中找结点的前驱：
? ltag = 1时, lchild所指的结点即为前驱；
? ltag = 0时, 其前驱为遍历其左子树时的最后一个结
点 （ 最右下结点 ） 。
? 如根结点, -”的前驱是, d” 。
中序线索二叉树
// 二叉树的二叉线索存储表示
typedef enum {Link,Thread} PointerTag;
//Link==0:指针,Thread==1:线索
typedef struct BiThrNode {
TElemType data;
struct BiThrNode *lchild,*rchild;
//左右孩子指针
PointerTag LTag,RTag; //左右标志
}BiThrNode,*BiThrTree;
中序遍历二叉树 T，并将其中序线索化,
(为了记下遍历过程中访问结点的先后次序，附设一个全程
指针 pre)
Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{ // Thrt指向头结点。
if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))
exit (OVERFLOW);
Thrt->LTag=Link; Thrt->RTag=Thread; //建头结点
Thrt->rchild=Thrt; //右指针回指
if (!T)Thrt->lchild=Thrt; //若二叉树空，则左指针回指
else{
Thrt->lchild=T; pre=Thrt;
InThreading(T); //中序遍历进行中序线索化
pre->rchild=Thrt;
pre->RTag=Thread; //最后一个结点线索化
Thrt->rchild=pre;
}
return OK;
}//InOrderThreading
中序遍历进行中序线索化
void InThreading(BiThrTree p){
// 一个全程指针 pre
if (p){
InThreading(p->lchild); //左子树线索化
if (!p->lchild){
p->LTag=Thread;p->lchild=pre;} //前驱线索
if (!pre->rchild){
pre->RTag=Thread; pre->rchild=p;} //后继线索
pre=p; //保持 pre指向 p的前驱
InThreading(p->rchild); //右子树线索化
}
}//InThreading
例如,
将下列二叉链表改为中序线索链表
I n f o A B C D E F G H I J K L M N
L t ag
L ch i l d 2 4 6 0 7 0 10 0 12 13 0 0 0 0
R t ag
R ch i l d 3 5 0 0 8 9 11 0 0 0 14 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14
上例树的形态
Info L t a g L c hi l d Rt a gRc hi l d
A 0 2 0 3
B 0 4 0 5
C 0 6 1 T hrt
D 1 T hrt 1 2
E 0 7 0 8
F 1 1 0 9
G 0 10 0 11
H 1 5 1 1
I 0 12 1 3
J 0 13 1 7
K 1 7 0 14
L 1 6 1 9
M 1 2 1 10
N 1 11 1 5
Thrt 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
A
B
D E F
C
H IG
KJ
M N
L
中序遍历二叉线索树 T的非递归算法,
Status InOrderTraverse_Thr(BiThrTree T,
Status(*Visit)(TElemType e)){
// T指向头结点，头结点的左链 lchild 指向根结点，
//可参见线索化算法。中序遍历二叉线索树 T的非递归算法，
// 对每个数据元素调用函数 Visit.
p=T->lchild; //p指向根结点
while(p!=T){ //空树或遍历结束时,p==T
while(p->LTag==Link)p=p->lchild;//p寻找最左下结点
if (!Visit(p->data))
return ERROR; //访问其左子树为空的结点
while(p->RTag==Thread&&p->rchild!=T){
p=p->rchild; Visit(p->data); //访问后继结点
}
p=p->rchild;
}
return OK;
}//InOrderTraverse_Thr
实验与习题
?理论习题 6.12-6.16,6.23
?实验算法题, 6.37