线索化二叉树的实现

2021年1月25日发(作者：单纯形)




数据结构课程设计

设
计
说
明
书




线索二叉树算法的实现





学
生
姓
名

学
班
成
号

级

绩

XX
XXXXXXX
XXXXX

XXX
指
导
教
师



计算机科学与技术系

XXXX
年
X
月
X
日



数据结构
课程设计评阅书

题




目

学生姓名

线索二叉树算法的实现

XX
学号

XXXXXXX
指导教师评语及成绩

成绩：











教师签名：


















年


月


日

答辩教师评语及成绩

成绩：











教师签名：


















年


月


日

教研室意见

总成绩：









室主任签名：
















年


月


日

注
:
指导老师成绩
60%
，
答辩成绩
40%，
总成绩合成后按五级制计入。




课程设计任务书

2011
—
2012
学年第
1
学期

专业：

计算机科学与技术

学号：
XXXXXXX
姓名：

XXXX
课程设计名称：

数据结构课程设计

设

计

题

目：

线索二叉树的实现

完

成

期

限：
自
2011
年
8
月
29
日至
2011
年
9
月
9
日共
2
周

设计内容：

n
个结点的二叉链表中含有
n+1
个空指针域 。利用二叉链表中的空
指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这
种 附加的指针称为

线索

）。这种加上了线索的二叉树称为线索二叉树
( Threaded BinaryTree)
。
对一棵非线索二叉树以某种次序遍历使其变为 一
棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉
链表中的空指针改为指 向结点前驱或后继的线索，而一个结点的前驱或
后继结点的信息只有在遍历时才能得到，因此线索化的过 程即为在遍历
过程中修改空指针的过程。根据线索性质的不同，线索二叉树可分为前
序线索二叉 树、中序线索二叉树和后序线索二叉树三种。

运用
VC++
编写一个程序实 现前序线索二叉树、中序线索二叉树和后
序线索二叉树，其中遍历要求用先左后右的递归或非递归算法来 实现。

要求
:
1
）

阐
述设计思想，画出流程图；

2
）

任
意建立一棵二叉树，采用前序、中序、后序三种方法线索化二
叉树；

3
）

说
明测试方法，写出完整的运行结果；

4
）

从
时间、空间对算法分析；

5
）

较
好的界面设计；

6
）

编
写课程设计报告。


以上要求中第一个阶段的任务完成后，先 将设计说明书的草稿交
指导老师面审，
审查合格后方可进入后续阶段的工作。
设计工作 结束后，
经指导老师验收合格后将设计说明书打印装订，并进行答辩。









指导教师（签字）：

教研室主任（签字）：

批准日期：

年

月

日


摘

要

这是一个关于线索二叉树的程序，该程序具有创建二叉树、遍历二
叉树、 线索化二叉树。其中，遍历和线索化都包含了先、中、后三种序
列，
而且对三种序列线索化后的 二叉树也进行了遍历。
该程序采用
VC
6.0
作为软件开发环境，采用C
语言的各种语句和结构实现二叉树的一系列
操作，并采用友好的界面向用户提供所操作的 过程和数据状态，操作简
单，界面清晰，易于被用户所接受。

关键字：
线索化；遍历；二叉树；先序；中序；后序


目



录

1
课题描述

....... ...........................................
1
2

任务分析

....................... ...........................
2
3

逻辑设计及描述

............................................
3

3.1
二叉树的存储
...........................................
3
3.2

二叉树的遍历

...........................................
4
3.3

二叉树的线索化

.........................................
5
3.4

线索化二叉树的遍历

.....................................
9
3.5

主函数

..................... ..........................
14
4
程序编码

................................. ................
16

总结

....... ................................................
26

参考文献

...................... .............................
27



1
课题描述

本程序重在设计二叉树的各种线索化实现，以
C语言作为编程语
言，实现对二叉树的先、中、后三种序列的线索化。旨在使用户在使用
过程 中能直接调用各种所需函数，以及了解二叉树的各种线索化过程。
其中各函数分别为：

BiThrTree CreateBiTree()
；
//
创建二叉树
;
BiThrTree CopyBiTree(BiThrTree &rt)
//
复制一棵二叉树
;
void
PreOrderTraverse(BiThrTree T)
//
先序遍历二叉树
;
void
InOrderTraverse(BiThrTree T)
//
中序遍历二叉树
;

void
PostOrderTraverse(BiThrTree T)
//
后序遍历二叉树
;
bool

PreOrderThreading(BiThrTree
&Thrt,
BiThrTree
T)
//
先序线索
化二叉树
;
void
PreThreading(BiThrTree p)
//
先序搜索结点的建立
;
bool
InOrderThreading(BiThrTree &Thrt, BiThrTree T)
//
中序线索化
二叉树
;
void
InThreading(BiThrTree p)
//
中序搜索结点的建立
;
void
backThreading(BiThrTree p)
//
后序搜索结点的建立
;
BiThrTree backorderThreading(BiThrTree &rt)
//
后序线索化二叉树
;
BiThrTree

parent(BiThrTree &thrt,BiThrTree &p)
//
查找结点

void
PreOrderTraverse_Thr(BiThrTree Thrt)//
遍历先序线索化二叉树
;
void
InOrderTraverse_Thr(BiThrTree Thrt)
//
遍历中序线索化二叉树
;
void
backorderTraver(BiThrTree Thrt)
//
遍历后序线索化二叉树
;
void
InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T)
//
将线索化后的
二叉树还原
;
开发工具
：
C
语言

运行环境
：
Visual c++
6.0
。

1



2
任务分析

这是一个能对二叉树线索化 的程序，其中包括对二叉树的先序、中
序、后序线索化，最后遍历线索化并输出遍历结果。其中线索化要 实现
对同一个树的线索化，即应具备还原线索化后二叉树的程序，并重新对
二叉树线索化。主要 的功能模块流程图如图
2.1
所示。


创建一棵二叉树
递
归
先
序
遍
历
递
归
中
序
遍
历
递
归
后
序
遍
历
先
序
线
索
化
中
序
线
索
化
后
序
线
索
化
遍
历
先
序
线
索
化
遍
历
中
序
线
索
化
遍
历
后
序
线
索
化


图

2.1
模块流程图

2



3
逻辑设计及描述

3.1
二叉树的存储

1.
创建二叉树
（

CreateBiTree(T)
）< br>设计思想：
在用户需要创建二叉
树时，屏幕提醒输入树的各个结点，包括空结点的输入， 完成输入后，
程序自动依次读入各个结点，以空结点作为判断结点位置的主要依据，
对每个结点 申请一定的存放空间，然后依次存放各结点。设计流程如图
3.1
所示。


begin
begin
charch;
BiThrTreetree;
ch=='#'
Y
N
rt==NULL
N
!(tree=(Bi ThrTree)malloc(si
zeof(BiThrNode)))
Y
T=N ULL
!(T=(BiThrTree)malloc(size
of(BiThrNode) ))
Y
N
Tree=NULL
Y
N
Return 0;
Return 0;
T->data=ch;
tree->data=rt->d ata;
Return T
returntree;
结束
结束





图
3.1

CreateBiTree(T )

创建二叉树

图
3.2
CopyBiTree(rt)


复制一棵二叉树
2.
复制二叉树
（
CopyBiTree(rt)
）
设计思想：
该函数的功能主要是为
了避免前后两次的线索化混乱，
其实质是重建二叉树以方便下一 次的线
索化。复制的方法无外乎将各个结点拷贝至另一棵树，因为是完全一样
3



的二叉树
,
所以连左右标志域也要一起复制
,
结点位置不能发生任何变
化。设计流程如图
3.2
所示，算法如算法
3.1< br>所示。

BiThrTree CopyBiTree(BiThrTree &rt){





BiThrTree tree;if(rt==NULL) tree=NULL;





else{


if(!(tree=(BiThrTree) malloc(sizeof(BiThrNode)))) return 0;


tree->data=rt->data;
//
复制结点



tree->LTag=rt->LTag;tree->RTag=rt->RTag;/
/
复制左右标志域



tree->lchild=CopyBiTree(rt->lchild);


tree->rchild=CopyBiTree(rt->rchild);//
复制左右 孩子
}


return tree;}
算法
3.1
3.2
二叉树的遍历

1.

先、中、后遍历二叉树，因 为三种遍历方法的区别只是将输出
结点的位置调换一下就可以实现，
所以在此只列举先序遍历方 法的设计
思想，该函数是用递归的方法依次遍历根结点、左子、右子，中序遍历
则是左子、根结 点、右子，后序遍历只需将根结点的访问放在最后面执
行即可。设计流程如图
3.3
， 主要算法如算法
3.2
所示。

void PreOrderTraverse(BiThrTree T){//
前序遍历







if (T!=NULL){printf(



/*
访问根结点
*/

PreOrderTraverse(T- >lchild);PreOrderTraverse(T->rchild); }}
算法
3.2
4



begin
Void PreThreading(BiThrTreep);
beg in
!T
Y
N
Thrt->lchild=T;
T!=NULLY
N
Thrt->lchild=Thrt;
PreThreading(Thr t)
Pre->rchild=Thrt;
Pre->Rtag=1;
Thrt->r child=Pre;
printf(
PreOrderTraverse(T->lchil d)
PreOrderTraverse(T->rchild)
Return 1;
结束


结束














图
3.4

图

3.3


PreOrderTraverse(T)
先序遍历二叉树




PreOrderThreading(Thrt,T)
先序线索化二叉树

3.3
二叉树的线索化

1.

先序线索化二叉树（
PreOrderThreading(Thrt ,T)
）设计思想：由
于线索化的实质是将二叉链表中的空指针改为指向遍历时得到的前驱或后继的线索，因此线索化的过程即为在遍历过程中修改空指针的过
程，附设一个指针
pr e
始终指向刚刚访问过的结点，若指针
p
指向当前
结点，则
pre< br>指向他的前驱。由此可得先序遍历建立先序线索化的算法
如算法
3.3
和
3.4
所示。

5



begin
p
Y
!p->lchild
Y
p->lchild=pre;
beg in
N
N
!pre->rchild
Y
pre->rchild=p ;
N
p
Y
InThreading(p->lchild);
Npre=p;
!p->lchild
N
p->LTag==0
Y
PreThreading(p->lchile);
N
Y
p->lchild=pr e;
!pre->rchild
N
p->RTag==0
Y
PreT hreading(p->rchile);
N
Y
pre->rchild=p;pre=p;
结束



















结束

图
3.5

PreThreading(p)

先序搜索结点的建立


图
3.6
InThreading(p
)
中序搜索结点的建立

2
．
中序搜索结点的建立以及线索化如图3
．
6
和
3
．
7
所示
;
后序 搜
索结点的建立和线索化如图
3
．
8
和
3
．
9
所示。流程图不再多作说明。

6



b egin
p
Y
N
begin
voidInThreading(Bi ThrTreep);
PostThreading(p->lchild);
!p->lch ild
Y
N
!T
Y
N
p->LTag=1;
Thr t->lchild=T;
Pre=Thrt;
!pre->rchild
Y
N
InThreading(T);
Pre->rchild=Thrt;
Pre-> Rtag=1;
Thrt->rchild=Pre;
pre->RTag=1;
pr e=p;
结束











结束

图
3.7
InOrderThreading(Thrt,T)

中序线索化二叉树

图
3.8



backThreading(p)
后序搜索结点的建立


bool PreOrderThreading(BiThrTree &Thrt,BiThrTree T)
{//
前序线索化二叉树







void PreThreading(BiThrTree p);//
先序遍历进行先序线索化








Thrt = (BiThrTree)malloc(sizeof(BiThrNode));







Thrt->LTag=0; Thrt->RTag=1; //
创建头结点


Thrt->rchild=Thrt;//
右指针回指







if (!T) Thrt->lchild=Thrt; //
空二叉树







else {












Thrt->lchild = T;pre = Thrt;


//pre:
刚刚访问过的结点




PreThreading(T);pre->rchild=Thrt; pre->RTag=1;//
最后一个结点
7



线索化



Thrt->rchild=pre; }

return 1;}





算法
3.3
void PreThreading(BiThrTree p){











if (p) {




if(!p->lchild){ p->lchild=pre; p->LTag=1;} //
前驱线索





if(!pre->rchild){ pre->rchild=p;pre->RTag=1;}//
后继线索







pre = p;//
保持
pre
指向
p
的前驱





if(p->LTag==0)PreThreading(p->lchild);


//
左子树线索化














if(p->RTag ==0)PreThreading(p->rchild);

//
右子树线索
化
}





} //
前序建立节点的搜索化

算法
3.4
begin
begin
BiThrTreethrt;
BiThrTreetemp;
! (thrt=(BiThrTree)malloc(size
of(BiThrNode)))
Y
thrt->LTag=0;
N
temp->lchild==p
YN
temp=temp->lchild;
!rt
Y
Thrt->lch ild=thrt;
N
thrt->lchild=rt;
0==temp->RTa g
Pre=thrt;
Y
N
PostThreading(rt);
temp=temp-
>rchild;
temp=temp-
>lchild;Thrt->rchild=pre;
returntemp;
return(thrt) ;
结束








8


N
temp->lchild!=p&&temp-
>rchild!=p
Y


图
3.9
backOrderThreading
(Thrt,T)

后序线索化二叉树

图
3.10
BiThrTree
parent(thrt,p)
查找结点


3.4
线索化二叉树的遍历

在程序设计中
,
实现线索化二叉树的遍历,
实质上就是在查找每个
结点的前驱和后继
,
而结点是否有前驱和后继、
他们分别是什么
,
就要分
情况去讨论。

1.
中序 遍历线索化二叉树
(InOrderTraverse_Thr(Thrt))
时
,< br>结点的前
驱应是遍历左子树时访问的第一个结点
,
既左子树最左下方的结点,
结点
的后继应是遍历右子树时访问的第

9



begin
BiThrTreep;
begin
p!=Thrt< br>Y
N
BiThrTreep;
printf(
→

p! =Thrt
Y
N
p->LTag==0
Y
N
p->LTag ==0
Y
N
p=p->lchild;
p=p->lchild;
( p->RTag==1)&&(p-
>rchild!=Thrt)
Y
N
pr intf(
→

p=p->rchild;
(p->RTag==1)&&(p -
>rchild!=Thrt)
Y
N
p->LTag==0
YN
p=p->rchild;
p=p->lchild;
p=p->rchild ;
p=p->rchild;
结束
图
3.11
图

3.12
PreOrderTraverse_Thr(Thrt)

InOrderTraverse_Thr(Thrt)

遍历先序线索化二叉树

遍历中序线索化二叉树

一个结点
,
既右子树最左下方的结点。二叉树最左下方的结点没有前驱，
最右下方的结点没有后继。设计 该函数的流程如图
3.12
所示。

2.
在后序线索树
(P ostOrderTraverse_Thr(Thrt))
中找结点后继比较复
杂，分三种情 况（
1
）根结点没有后继；（
2
）若结点是其双亲的右孩子
或是其双 亲的左孩子且其双亲没有右子树，则后继为双亲；（
3
）若结
点是其双亲的左孩子且其 双亲有右子树，则后继为其

10





结束

















双亲的右子树 上按后序遍历访问的第一个结点。
设计该函数的流程如图
3
．
13
所 示。

3.
还原线索化二叉树
(InOrder_Thr_T(Thrt,T )):
涉及该函数的主要目
的是在每次线索后

11