二叉树的建立与遍历及二叉树的线索化及线索化遍历.docx
《二叉树的建立与遍历及二叉树的线索化及线索化遍历.docx》由会员分享，可在线阅读，更多相关《二叉树的建立与遍历及二叉树的线索化及线索化遍历.docx（17页珍藏版）》请在冰点文库上搜索。
二叉树的建立与遍历及二叉树的线索化及线索化遍历
理工大学信息工程与自动化学院学生实验报告
（2011—2012学年第1学期）
课程名称：
数据结构开课实验室：
信自楼4422011年11月06日
年级、专业、班
学号
成绩
实验项目名称
二叉树的建立与遍历及二叉树的线索化及线索化遍历
指导教师
教师
评语
教师签名：
年月日
1、程序功能：
（1）.线索二叉树的主要函数设置如下：
1.树的存储的类型为：
typedefstructbithrnode
{
chardata;
structbithrnode*lchild,*rchild;
intltag,rtag;
}bithrnode,*bithrtree;
2.主程序：
bithrtreeT,p,T1;
intk;
Do
{
switch（k）
{
case1:
creat（T）;--------建立二叉树
T1=copy（T）;---------复制建立后的二叉树
case2:
T=copy（T1）;---------复制建立后的二叉树
PreOrderThreading（p,T）;---------先序线索化
first（p）;--------------先序遍历
case3:
T=copy（T1）;---------复制建立后的二叉树
InOrderThreading（p,T）;----------中序线索化
mid（p）;---------------中序遍历
case4:
T=copy（T1）;---------复制建立后的二叉树
backorderThreading（p,T）;-------------后序线索化
last（p）;--------------后序遍历
}
}while（k!
=0）;
3.子程序：
bithrtreecreat（bithrtree&T）--------建立二叉树
StatusPreOrderThreading（bithrtree&thrt,bithrtreeT）---------先序线索化
{voidPreThreading（bithrtreep）}---------先序线索化子函数
StatusInOrderThreading（bithrtree&thrt,bithrtreeT）----------中序线索化
{voidinthreading（bithrtree&p）}----------中序线索化子函数
StatusbackorderThreading（bithrtree&thrt,bithrtreeT）-------------后序线索化
{voidbackthreading（bithrtreep）}-------------后序线索化子函数
voidfirst（bithrtreethrt）--------------先序遍历
voidmid（bithrtreethrt）---------------中序遍历
voidlast（bithrtreet）--------------后序遍历
bithrtreecopy（bithrtree&r）---------复制建立后的二叉树
bithrtreecreat（bithrtree&T）
（2）.程序代码如下：
#include
#include
#include
#include
#defineOVERFLOW-2
#defineOK1
#defineerror0
typedefintStatus;
typedefenumpointertag{link=0,thread=1};//link==0;指针thread==1；线索
typedefstructbithrnode
{chardata;
structbithrnode*lchild,*rchild;//左右孩子指针
intltag,rtag;
}bithrnode,*bithrtree;
bithrtreepre;
bithrtreecreat（bithrtree&T）//构造二叉树
{charch;
fflush（stdin）;
scanf（"%c",&ch）;
if（ch==''||ch=='#'）
T=NULL;
else
{if（!
（T=（bithrnode*）malloc（sizeof（bithrnode））））
returnerror;
T->data=ch;
T->ltag=0;
T->rtag=0;
printf（"输入父结点%c的左孩子：
",ch）;
T->lchild=creat（T->lchild）;
printf（"输入父结点%c的右孩子：
",ch）;
T->rchild=creat（T->rchild）;
}
returnT;
}
voidPreThreading（bithrtreep）//先序线索化
{if（p）
{
if（!
p->lchild）
{p->ltag=thread;
p->lchild=pre;
}//前驱线索
if（!
pre->rchild）
{pre->rtag=thread;
pre->rchild=p;
}//后继线索
pre=p;
if（p->ltag==link）
PreThreading（p->lchild）;//左子树线索化
if（p->rtag==link）
PreThreading（p->rchild）;//右子树线索化
}
}
StatusPreOrderThreading（bithrtree&thrt,bithrtreeT）//先序线索二叉树
{if（!
（thrt=（bithrtree）malloc（sizeof（bithrnode））））
returnerror;
thrt->ltag=link;
thrt->rtag=thread;//建头结点
thrt->rchild=thrt;//右指针回指
if（!
T）
thrt->lchild=thrt;//空二叉树
else
{thrt->lchild=T;
pre=thrt;
PreThreading（T）;//先序遍历进行先序线索化
pre->rchild=thrt;pre->rtag=thread;//最后一个结点线索化
thrt->rchild=pre;
}
returnOK;
}
voidinthreading（bithrtree&p）//中序线索化
{
if（p）
{inthreading（p->lchild）;//左子树线索化
if（!
p->lchild）
{p->lchild=pre;
p->ltag=thread;
}
if（!
pre->rchild）
{pre->rchild=p;
pre->rtag=thread;
}
pre=p;
inthreading（p->rchild）;//右子树线索化
}
}
StatusInOrderThreading（bithrtree&thrt,bithrtreeT）//中序线索化二叉树
{
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;
}
returnOK;
}
voidbackthreading（bithrtreep）//后序线索化
{
if（p）
{backthreading（p->lchild）;
backthreading（p->rchild）;
if（!
p->lchild）
{p->ltag=thread;
p->lchild=pre;}//前驱线索
if（!
pre->rchild）
{pre->rtag=thread;
pre->rchild=p;}//后继线索
pre=p;
}
}
StatusbackorderThreading（bithrtree&thrt,bithrtreeT）//后序线索化二叉树
{
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;
backthreading（T）;//中序遍历进行中序线索化
pre->rchild=thrt;
pre->rtag=thread;//最后一个结点线索化
thrt->rchild=pre;
}
returnOK;
}
voidfirst（bithrtreethrt）//先序遍历二叉树
{
bithrtreep;
printf（"先序遍历结果为：
"）;
p=thrt->lchild;
while（p!
=thrt）
{printf（"%c",p->data）;
while（p->ltag==link）
{
p=p->lchild;
printf（"%c",p->data）;
}
while（（p->rtag==thread）&&（p->rchild!
=thrt））
{p=p->rchild;
printf（"%c",p->data）;
}
p=p->rchild;
}
printf（"\n"）;
}
voidmid（bithrtreethrt）//中序遍历二叉树
{
bithrtreep;
printf（"中序遍历结果为：
"）;
p=thrt->lchild;
while（p!
=thrt）
{while（p->ltag==link）
p=p->lchild;
printf（"%c",p->data）;
while（（p->rtag==thread）&&（p->rchild!
=thrt））
{p=p->rchild;
printf（"%c",p->data）;
}
p=p->rchild;
}
printf（"\n"）;
}
bithrtreeparents（bithrtree&thrt,bithrtree&p）{
bithrtreet;
t=thrt;
if（t->lchild==p）
returnt;//父节点是头结点
else{
t=t->lchild;
while（t->lchild!
=p&&t->rchild!
=p）
{if（link==t->rtag）
t=t->rchild;//结点有右结点，往右
else
t=t->lchild;
}//如果结点没有右孩子，去左孩子，没有左孩子，去前驱
returnt;}
}
voidlast（bithrtreet）{//后序遍历二叉树
bithrtreep,q;
p=t->lchild;
while
（1）
{while（p->ltag==link）
p=p->lchild;
if（p->rtag==link）
p=p->rchild;//p指向第一个被访问的结点
elsebreak;
}
while（p!
=t）
{printf（"%c",p->data）;
q=parents（t,p）;//parent是p的双亲:
if（t==q）p=t;//若parent是thrt，即p是根结点，则无后继
else
if（p==q->rchild||thread==q->rtag）
p=q;//若p是双亲的右孩子，或者是独生左孩子，则后继为双亲
else
{
while（q->rtag==link）
{//若p是有兄弟的左孩子，则后继为双亲的右子树上后序遍历访问的第一个节点。
q=q->rchild;
while（q->ltag==link）
{q=q->lchild;}
}
p=q;
}
}
printf（"\n"）;
}
bithrtreecopy（bithrtree&r）//复制一棵二叉树
{
bithrtreetr;
if（r==NULL）tr=NULL;
else{if（!
（tr=（bithrtree）malloc（sizeof（bithrnode））））
return0;
tr->data=r->data;
tr->ltag=r->ltag;
tr->rtag=r->rtag;
tr->lchild=copy（r->lchild）;
tr->rchild=copy（r->rchild）;
}
returntr;
}
voidmain（）//主函数
{
bithrtreeT,p,T1;
intk;
do{printf（"\t-------------线索二叉树---------------\n\n"）;
printf（"\t建二叉树1"）;
printf（"\t\t\t先序遍历线索化二叉树2\n"）;
printf（"\t中序遍历线索化二叉树3"）;
printf（"\t后序遍历线索化二叉树4\n"）;
printf（"\t结束输入0\n"）;
printf（"\n\t------------------------------------\n\n"）;
printf（"请输入您的选择:
"）;
scanf（"%d",&k）;
switch（k）
{
case1:
printf（"\t--------结束为'#'---------------------\n"）;
printf（"请输入树的根结点:
"）;
creat（T）;T1=copy（T）;
system（"cls"）;
break;
case2:
T=copy（T1）;PreOrderThreading（p,T）;
first（p）;
system（"pause"）;
system（"cls"）;
break;
case3:
T=copy（T1）;InOrderThreading（p,T）;
mid（p）;system（"pause"）;system（"cls"）;
break;
case4:
T=copy（T1）;backorderThreading（p,T）;
last（p）;system（"pause"）;system（"cls"）;
default:
break;
}
}while（k!
=0）;
printf（"\n\t使用！
\n"）;
}
二、实验报告：
（1）.运行过程
1.如图6.1所示的二叉树线索化的理论结果：
先序遍历线索化二叉树结果为：
abdefcg
中序遍历线索化二叉树结果为：
edfbacg
后序遍历线索化二叉树结果为：
efdba
图6.1创建的二叉树
2.如图6.21所示的二叉树的实际结果：
1）创建二叉树的实际结果如下图：
2）先序遍历线索化二叉树的实际结果如下图所示：
3）中序遍历线索化二叉树的实际结果如下所示：
4）后序遍历线索化二叉树的实际结果如下图所示：
5）结束界面如下图所示：
（2）.算法分析
1.当对树进行线索和遍历时，首先必须建立二叉树，没有建立二叉树、当遍历时树为空，其次遍历的过程必须在线索化的后面进行，这样才能够体现出本次试验的目的—线索化二叉树。
遍历的实现还需要与其对应的线索化进行一一对应，否则遍历的结果是错误的。
2.线索二叉树的时间复杂度和空间复杂度,因为在线索的过程都必须要申请存储空间，就是需要多少存储空间，就申请空间，但是在后面需要复制本二叉树的信息，所以也要求与建立的书的存储空间相同，即空间复杂度为（n）。
（3）.时间复杂度
1.遍历和线索的时间复杂度都是O（n），因为在其过程中线索一个走其下一个节点，过程依次将所有节点线索完成。
2.遍历同样是该过程进行的，所以遍历的时间复杂度同样为O（n）。
（4）.总结
在写本次实验报告的过程中，通过上机我对二叉树有了深刻的了解：
n个结点的二叉链表中含有n+1个空指针域。
利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。
这种加上了线索的二叉树称为线索二叉树（Threaded BinaryTree）。
对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。
由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
升级会员 