二叉树的建立与遍历及二叉树的线索化及线索化遍历.doc

精选文档

昆明理工大学信息工程与自动化学院学生实验报告
（2011—2012学年 第1学期）
课程名称：数据结构 开课实验室：信自楼442 2011年 11月 06日
年级、专业、班

学号

姓名

成绩

实验项目名称
二叉树的建立与遍历及二叉树的线索化及线索化遍历

指导教师

教师
评语

教师签名：
年 月 日
一、 程序功能：
（1）.线索二叉树的主要函数设置如下：
1.树的存储的类型为：typedef struct bithrnode
{
char data;
struct bithrnode *lchild,*rchild;
int ltag,rtag;
}bithrnode,*bithrtree;

2.主程序：
bithrtree T, p,T1;
int k;
Do
{
switch(k)
{
case 1:
creat(T); --------建立二叉树
T1=copy(T); ---------复制建立后的二叉树
case 2:
T=copy(T1); -------复制建立后的二叉树
PreOrderThreading(p,T); ---------先序线索化
first(p); --------------先序遍历
case 3: T=copy(T1); ---------复制建立后的二叉树
InOrderThreading(p,T); ----------中序线索化
mid(p); ---------------中序遍历
case 4: T=copy(T1); --------复制建立后的二叉树
backorderThreading(p,T); -------------后序线索化
last(p); --------------后序遍历
}
}while(k!=0);

3.子程序：
bithrtree creat(bithrtree &T) --------建立二叉树
Status PreOrderThreading(bithrtree &thrt,bithrtree T) ---------先序线索化
{void PreThreading(bithrtree p)} ---------先序线索化子函数
Status InOrderThreading(bithrtree &thrt,bithrtree T) ----------中序线索化
{void inthreading(bithrtree &p)} ----------中序线索化子函数
Status backorderThreading(bithrtree &thrt,bithrtree T) -------------后序线索化
{void backthreading(bithrtree p)} -------------后序线索化子函数
void first(bithrtree thrt) --------------先序遍历
void mid(bithrtree thrt) ---------------中序遍历
void last(bithrtree t) --------------后序遍历
bithrtree copy(bithrtree &r) ---------复制建立后的二叉树
bithrtree creat(bithrtree &T)

（2）.程序代码如下：
#include
#include
#include
#include
#define OVERFLOW -2
#define OK 1
#define error 0
typedef int Status;
typedef enum pointertag{ link=0,thread=1 }; //link==0; 指针 thread==1；线索
typedef struct bithrnode
{ char data;
struct bithrnode *lchild,*rchild; //左右孩子指针
int ltag,rtag;
}bithrnode,*bithrtree;
bithrtree pre;
bithrtree creat(bithrtree &T) //构造二叉树
{ char ch;
fflush(stdin);
scanf("%c",&ch);
if(ch==' '||ch=='#')
T=NULL;
else
{ if(!(T=(bithrnode *)malloc(sizeof(bithrnode))))
return error;
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);
}
return T;
}
void PreThreading(bithrtree p) //先序线索化
{ 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); //右子树线索化
}
}
Status PreOrderThreading(bithrtree &thrt,bithrtree T) //先序线索二叉树
{ if(!(thrt=(bithrtree)malloc(sizeof(bithrnode))))
return error;
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;
}
return OK;
}
void inthreading(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); //右子树线索化
}
}
Status InOrderThreading(bithrtree &thrt,bithrtree T) //中序线索化二叉树
{
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;
}
void backthreading(bithrtree p) //后序线索化
{
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;
}
}
Status backorderThreading(bithrtree &thrt,bithrtree T) //后序线索化二叉树
{
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;
}
return OK;
}
void first(bithrtree thrt) //先序遍历二叉树
{
bithrtree p;
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");
}
void mid(bithrtree thrt) //中序遍历二叉树
{
bithrtree p;
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");
}
bithrtree parents(bithrtree &thrt,bithrtree &p){
bithrtree t;
t=thrt;
if(t->lchild==p)
return t; //父节点是头结点
else{
t=t->lchild;
while( t->lchild!=p && t->rchild!=p )
{ if(link==t->rtag)
t=t->rchild; //结点有右结点，往右
else
t=t->lchild
} //如果结点没有右孩子，去左孩子，没有左孩子，去前驱
return t;}
}
void last(bithrtree t) { //后序遍历二叉树
bithrtree p,q;
p=t->lchild;
while(1)
{ while(p->ltag==link)
p=p->lchild;
if(p->rtag==link)
p=p->rchild; //p指向第一个被访问的结点
else break;
}
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");
}
bithrtree copy(bithrtree &r) //复制一棵二叉树
{
bithrtree tr;
if(r==NULL) tr=NULL;
else{ if(!(tr=(bithrtree)malloc(sizeof(bithrnode))))
return 0;
tr->data=r->data;
tr->ltag=r->ltag;
tr->rtag=r->rtag;
tr->lchild=copy(r->lchild);
tr->rchild=copy(r->rchild);
}
return tr;
}
void main() //主函数

{
bithrtree T, p,T1;
int k;
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)
{
case 1:
printf("\t--------结束为 '#'--------------------- \n");
printf("请输入树的根结点:");
creat(T); T1=copy(T);
system("cls");
break;
case 2:
T=copy(T1);PreOrderThreading(p,T);
first(p);
system("pause");
system("cls");
break;
case 3:
T=copy(T1);InOrderThreading(p,T);
mid(p);system("pause");system("cls");
break;
case 4:
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

a

b
c

g
d

f
e

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

（范文素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）