数据结构课程设计-线索二叉树的应用

安徽省巢湖学院计算机与信息工程学院

课程设计报告

课程名称《数据结构》

课题名称线索二叉树的应用

专业计算机科学与技术

班级 10计本2班

学号10012084

姓名王春雷

联系方式150********

指导教师江家宝蔡敏

20 11 年 12 月 25 日

目录

1、数据结构课程设计任务书 (1)

1.1、题目 (1)

1.2、要求 (1)

2、总体设计 (1)

2.1、数据输入输出 (1)

2.2、设计算法测试用例 (1)

2.2、流程图 (2)

3、详细设计 (2)

3.1、程序中所采用的数据结构及存储结构的说明 (4)

3.2、算法的设计思想 (5)

4、调试与测试： (6)

4.1、调试方法与步骤： (6)

4.2、测试结果的分析与讨论： (6)

6、源程序清单和执行结果 (9)

7、C程序设计总结 (17)

8、致谢 (17)

9、参考文献 (18)

1、数据结构课程设计任务书

1.1、题目

线索二叉树的应用

1.2、要求

实现线索树建立、插入、删除、恢复线索的实现。

2、总体设计

2.1、数据输入输出：

原始数据要求输入二叉树的7个结点：1234567，输出的是一个二叉树，这就实现了二叉树的建立过程。然后对二叉树进行线索化。对其进行插入：在7结点处插入结点8；删除：删除结点8;恢复线索等功能。

进行二叉树的初始化，依次输入，以*结束：

1234567*

线索二叉树的应用

****************************

1、进行二叉树线索化

2、进行插入操作

3、删除

4、中序输出

5、线索输出

0、退出

请选择：1

已经实现二叉树的线索化，可选择5查看线索。

2.2、设计算法测试用例：

（1）输入结点:1234567;(2)对输入的二叉树进行线索化；（3）查看二叉树的中序线索输出：4->2->5->1->6->3->7；（4）在7结点处插入结点8，此时完成线索化恢复，查看二叉树的中序线索输出：4->2->5->1->6->3->8->7;(5)删除结点8，此时完成线索化恢复，发现结点8，ltag=1,rtag=1,查看二叉树的中序线索输出：4->2->5->1->6->3->7;(6)继续删除结点r，发现无该结点，则输入错误。

2.3、流程图

3、详细设计

（1）、主函数

void main()

{

Bithptr *T;

int i;

//system("color 1a");

T=CreatTree();

printf("\n"); 开始

定义二叉树

T=CreatTree( )

1=>i

输入i!=0

输入选择菜单

输入i

i=1

preThred(T)

i=2

Insert(T)

i=3

DeleteNode(T)

i=4

Inorder(T) 退出

while(i)

{

printf("\t1 进行二叉树线索化\n");

printf("\t2 进行插入操作\n");

printf("\t3 进入删除操作\n");

printf("\t4 中序输出\n");

printf("\t5 线索输出\n");

printf("\t0 退出\n");

printf("\t 请选择:");

scanf("%d",&i);

printf("\n");

switch(i)

{

case 1:PreThread(T);

printf("\t已经实现二叉树的线索化\n");

printf("\n");

break;

case 2:Insert(T);printf("\n");break;

case 3:T=DeleteNode(T);printf("\n");break;

case 4:Inorder(T);

printf("\n");

break;

case 5:PrintIndex(T);break;

case 0:exit(1);

default:printf("error\n\t请继续选择:");

}

}

}

（2）、中序线索化算法：

void PreThread(Bithptr *root) //中序线索化算法，函数实现{

Bithptr *p;

p=root;

if(p){

PreThread(p->lchild);//线索化左子树

if(pre&&pre->rtag==1)pre->rchild=p; //前驱结点后继线索化

if(p->lchild==NULL)

{

p->ltag=1;

p->lchild=pre;

}

if(p->rchild==NULL) //后继结点前驱线索化p->rtag=1;

pre=p;

PreThread(p->rchild);

} 3.1、程序中所采用的数据结构及存储结构的说明

二叉树是由n （n>=0）个结点组成的有限集合，其中：（1）当n ＝0时，为空二叉树。（2）当n>0时，有且仅有一个特定的结点，称为二叉树的根，不相交的子集，其中每一个子集本身又是一棵二叉树，分别称为左子树和右子树。线索化是将二叉树转换成线索二叉树的过程。按某种遍历将二叉树线索化，只需在遍历过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继结点。

（1）线索二叉树的结点的结构如下：

约定：

Ltag=0 //表示lchild 域指示该结点的左孩子 Ltag=1 //表示lchild 域指示该结点的前驱 Rtag=0 //表示rchild 域指示该结点的右孩子 Rtag=1 //表示rchild 域指示该结点的后继

(2)线索链表中结点类型说明：

Typedef char datatype;

Typedef struct node{

Int ltag,rtag;

Datatype data;

Struct node *lchild,*rchild;

}bithptr;

(3)线索化算法：结点*pre 是结点*p 的前驱，而*p 是*pre 的后继。这样，当遍历到结点*p 时，可以进行以下三步操作：

1）若*p 有空指针域，则将相应的标志置1.

2）若*p 的左线索标志已经建立（p->ltag=1）,则可使其前驱线索化，令p->lchild=pre.

3)若*pre 的右线索标志已经建立（pre->rtag=1）,则可使其后继线索化，令pre->rchild=p. ltag

lchild data rtag rchild

如此，二叉树的线索化可以在二叉树的遍历过程完成，该算法应为相应顺序的遍历算法的一种变化形式。

（4）二叉链表的建立：其算法描述如下：

Bitree *crt_bt_pre(bitree *bt){

Char ch;

Ch=getchar( );

If(ch==‘＃’)

Bt=null;

Else{

Bt=(bitree *)malloc(sizeof(bitree));

Bt->data=c;

Bt->lchild=crt_bt_pre(bt->lchild);

Bt->rchild=crt_bt_pre(bt->rchild);

}

Return(bt);

}

3.2、算法的设计思想

建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。

关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。

操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0;

（2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。

（3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。

二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。

结点插入算法：由线索二叉树的定义易知插入的节点定是个叶子节点，需注意线索的修改，可分为两种情况：

1）：插入的节点t是右儿子，t的中序后继是其父亲的中序后继，中序前驱是其父亲。

2）：插入的节点t是左儿子，t的中序前驱是其父亲的中序前驱，中序后继是其父亲。

结点删除算法：删除的情况与搜索二叉树的删除的类似

1）：删除的节点p是叶子节点，直接删除，修改其父亲的线索。

2）：删除的节点p有一个儿子，p有一个左儿子，以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继，中序前驱不变；p有一个右儿子，以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱，中序后继不变。

3）：删除的节点p有二个儿子，转化为叶子节点或只有一个儿子节点的删除。

4、调试与测试：

4.1、调试方法与步骤：

1、当用二叉链表作为二叉树的存储结构时。可以方便地找到某个结点的左右孩子，但一般情况下，无法直接摘到该结点在没中遍历序列中的前驱和后继接待你。为了解决这个问题，所以采用线索二叉树。但是在编写过程中，忽略了线索二叉树的改变，没有改变空的左孩子指针域，而后再看了一遍数据结构的相关指导教材，发现了错误，及时改正，将空的左孩子指针域改为指向其前驱。

2、在进行线索化的编写过程中，出现了问题。开始只能对几点进行前驱线索化，而不能进行后继线索化。为此做了相应调整：

（1）若*p有空指针域，则将相应的标志置1。

（2）若*p的左线索标志已经建立，则可使其前驱线索化，令p->lchild=pre。

（3）若*pre的右线索标志已经建立，则可使其后继线索化，令pre->rchild=p。

3、在编写中序线索二叉树中的后继查找算法时，只编写了其中一种情况，应该有两种情况(1)*p的右子树为空，则p->rchild为右线索，指向*p的后继结点。（2）若*p的右子树非空，根据中序遍历的顺序，*p的后继结点为其右子树中最左下的结点。

4.2、测试结果的分析与讨论：

如图1所示，初始化输入二叉树，实现线索化，查看线索输出：

图1

如图2所示，在7结点处插入结点8，恢复线索化，查看中序线索输出为：

图2

如图3所示，删除结点8，恢复线索化，查看中序线索输出为：

图3

如图4所示，删除结点r，发现无该结点，则输出为：

图4

6、源程序清单和执行结果

#include

#include "malloc.h"

#include "windows.h"

#define maxsize 30 //规定树中结点的最大数目typedef struct node{ //定义数据结构

int ltag,rtag; //表示child域指示该结点是否孩子char data; //记录结点的数据

struct node *lchild,*rchild; //记录左右孩子的指针

}Bithptr;

Bithptr *Q[maxsize]; //建队，保存已输入的结点的地址Bithptr *CreatTree(){ //建树函数，返回根指针

char ch;

int front,rear;

Bithptr *T,*s;

T=NULL;

front=1;rear=0; //置空二叉树

printf("进行初始化，请依次输入\n");

ch=getchar(); //输入第一个字符

while(ch!='#') //判断是否为结束字符

{

s=NULL;

if(ch!='@') //判断是否为虚结点

{

s=(Bithptr *)malloc(sizeof(Bithptr));

s->data=ch;

s->lchild=NULL;

s->rchild=NULL;

s->rtag=0;

s->ltag=0;

}

rear++;

Q[rear]=s; //将结点地址加入队列中

if(rear==1)T=s; //输入为第一个结点为根结点

else

{

if(s!=NULL&&Q[front]!=NULL) //孩子和双亲结点均不是虚结点

if(rear%2==0)

Q[front]->lchild=s;

else Q[front]->rchild=s;

if(rear%2==1)front++;

}

ch=getchar();

}

return T;

}

void Inorder(Bithptr *T) //中序遍历

{

if(T)

{

if(T->ltag!=1)Inorder(T->lchild);

printf("%c→",T->data);

if(T->rtag!=1)Inorder(T->rchild);

}

}

Bithptr *pre=NULL;

void PreThread(Bithptr *root) //中序线索化算法，函数实现{

Bithptr *p;

p=root;

if(p){

PreThread(p->lchild);//线索化左子树

if(pre&&pre->rtag==1)pre->rchild=p; //前驱结点后继线索化

if(p->lchild==NULL)

{

p->ltag=1;

p->lchild=pre;

}

if(p->rchild==NULL) //后继结点前驱线索化

p->rtag=1;

pre=p;

PreThread(p->rchild);

}

}

void PrintIndex(Bithptr *t) //输出线索

{

Bithptr *f;

f=t;

if(f)

{

if(f->ltag==1&&f->lchild==NULL&&f->rtag==1)printf("【%c】",f->data); //如果是第一个结点

if(f->ltag==1&&f->lchild!=NULL)printf("%c→【%c】",f->lchild->data,f->data); //如果此结点有前驱就输出前驱和此结点

if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)printf("→%c",f->rchild->data); //如果此结点有前驱也有后继，就输出后继

else if(f->rtag==1&&f->rchild!=NULL)printf("【%c】→%c",f->data,f->rchild->data);//如果没有前驱，就输出此结点和后继

printf("\n");

if(f->ltag!=1)PrintIndex(f->lchild);

if(f->rtag!=1)PrintIndex(f->rchild);

}

}

Bithptr *SearchChild(Bithptr *point,char findnode) //查找孩子结点函数

{

Bithptr *point1,*point2;

if(point!=NULL)

{

if(point->data==findnode) return point;

else

if(point->ltag!=1) {point1=SearchChild(point->lchild,findnode);if(point1!=NULL)return point1;}

if(point->rtag!=1) {point2=SearchChild(point->rchild,findnode);if(point2!=NULL)return point2;}

return NULL;

}

else

return NULL;

}

Bithptr *SearchPre(Bithptr *point,Bithptr *child) //查找父亲结点函数

{

Bithptr *point1,*point2;

if(point!=NULL)

{

if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rchild==child))

return point;

else

if(point->ltag!=1)

{

point1=SearchPre(point->lchild,child);

if(point1!=NULL)

return point1;

}

if(point->rtag!=1)

{

point2=SearchPre(point->rchild,child);

if(point2!=NULL)

return point2;

}

return NULL;

}

else

return NULL;

}

void Insert(Bithptr *root)

{

char ch;

char c;

Bithptr *p1,*child,*p2;

printf("请输入要插入的结点的信息:");

scanf("%c",&c);

scanf("%c",&c);

p1=(Bithptr *)malloc(sizeof(Bithptr)); //插入的结点信息

p1->data=c;

p1->lchild=NULL;

p1->rchild=NULL;

p1->rtag=0;

p1->ltag=0;

printf("输入查找的结点信息:");

scanf("%c",&ch);

scanf("%c",&ch);

child=SearchChild(root,ch); //查孩子结点的地址

if(child==NULL){

printf("没有找到结点\n");

system("pause");

return ;

}

else printf("发现结点%c\n",child->data);

if(child->ltag==0) //当孩子结点有左孩子的时候

{

p2=child;

child=child->lchild;

while(child->rchild&&child->rtag==0) //找到左子树下，最右结点child=child->rchild;

printf("发现结点%c\n",child->data);

p1->rchild=child->rchild; //后继化

p1->rtag=1;

child->rtag=0;

child->rchild=p1; //连接

p1->lchild=child; //前驱化

p1->ltag=1;

}

else //当孩子结点没有左孩子的时候

{

p1->lchild=child->lchild; //前驱化

child->ltag=0;

p1->ltag=1;

child->lchild=p1;

p1->rchild=child;

p1->rtag=1;

}

printf("\n\t插入结点操作已经完成，并同时完成了线索化的恢复\n");

}

Bithptr * DeleteNode(Bithptr *t)

{

Bithptr *child,*pre,*s,*q;

char ch;

printf("输入查找的结点信息:");

ch=getchar();

ch=getchar();

child=SearchChild(t,ch);

printf("发现结点:%c\n",child->data);

printf("ltag=%d,rtag=%d\n",child->ltag,child->rtag);

pre=SearchPre(t,child);

printf("发现结点:%c\n",pre->data);

if(NULL==child)

{

printf("没有找到结点:");

return t;

}

system("pause");

if(child==pre->lchild||child==pre) //是父亲结点的左孩子{

if(1==child->ltag&&1==child->rtag)//孩子结点无左右

{

pre->lchild=child->lchild;

pre->ltag=1;

if(child->lchild!=NULL)

if(child->lchild->rtag==1)child->lchild->rchild=pre;

free(child);

}

else if(1!=child->ltag&&1==child->rtag)//孩子结点有左无右

{

pre->lchild=child->lchild;

s=child->lchild;

while(s->rchild)

s=s->rchild;

s->rchild=child->rchild;

free(child);

}

else if(1==child->ltag&&1!=child->rtag)//孩子结点有右无左

{

pre->lchild=child->rchild;

s=child->rchild;

while(s->lchild)

s=s->lchild;

s->lchild=child->lchild;

if(child->lchild!=NULL)

if(child->lchild->rtag==1)child->lchild->rchild=pre;

free(child);

}

else if(1!=child->ltag&&1!=child->rtag)//孩子结点左右都有

{

pre->lchild=child->lchild;

s=child->rchild;

while(s->lchild)

s=s->lchild;

s->lchild=child->lchild->rchild;//把孩子结点的左孩子的右子树接到孩子右子树的最左下结点

if(child->lchild->rtag!=1)s->ltag=0;

q=child->lchild;

while(q->rchild)

q=q->rchild;

q->rchild=s;

child->lchild->rchild=child->rchild;

child->lchild->rtag=0;

free(child);

}

}

if(child==pre->rchild) //是父亲结点的右孩子

{

if(1==child->ltag&&1==child->rtag)//孩子结点无左右

{

pre->rchild=child->rchild;

pre->rtag=1;

if(child->rchild!=NULL)

if(child->rchild->ltag==1)child->rchild->lchild=pre;

free(child);

}

else if(1!=child->ltag&&1==child->rtag)//孩子结点有左无右

{

pre->rchild=child->lchild;

s=child->lchild;

while(s->rchild)

s=s->rchild;

s->rchild=child->rchild;

if(child->rchild!=NULL)

if(child->rchild->ltag==1)child->rchild->lchild=pre;

free(child);

}

else if(1==child->ltag&&1!=child->rtag)//孩子结点有右无左

{

pre->rchild=child->rchild;

s=child->rchild;

while(s->lchild)

s=s->lchild;

s->lchild=child->lchild;

free(child);

}

else if(1!=child->ltag&&1!=child->rtag)//孩子结点左右都有

{

/* pre->lchild=child->lchild;

s=child->rchild;

while(s->lchild)

s=s->lchild;

s->lchild=child->lchild->rchild;//把孩子结点的左孩子的右子树接到孩子右子树的最左下结点

if(child->lchild->rtag!=1)s->ltag=0;

q=child->lchild;

while(q->rchild)

q=q->rchild;

q->rchild=s;

child->lchild->rchild=child->rchild;

child->lchild->rtag=0;*/

pre->rchild=child->rchild;

s=child->lchild;

while(s->rchild)

s=s->rchild;

s->rchild=child->rchild->lchild;//把孩子结点的左孩子的右子树接到孩子右子树的最右下结点

if(child->rchild->ltag!=1)s->rtag=0;

q=child->rchild;

while(q->lchild)

q=q->lchild;

q->lchild=s;

child->rchild->lchild=child->lchild;

child->rchild->ltag=0;

free(child);

}

}

printf("\n\t插入结点操作已经完成，并同时完成了线索化的恢复\n");

printf("find %c",child->data);

return t;

}

void main()

{

Bithptr *T;

int i;

//system("color 1a");

T=CreatTree();

printf("\n");

i=1;

while(i)

{

printf("\t1 进行二叉树线索化\n");

printf("\t2 进行插入操作\n");

printf("\t3 进入删除操作\n");

printf("\t4 中序输出\n");

printf("\t5 线索输出\n");

printf("\t0 退出\n");

printf("\t 请选择:");

scanf("%d",&i);

printf("\n");

switch(i)

{

case 1:PreThread(T);

printf("\t已经实现二叉树的线索化\n");

printf("\n");

break;

case 2:Insert(T);printf("\n");break;

case 3:T=DeleteNode(T);printf("\n");break;

case 4:Inorder(T);

printf("\n");

break;

case 5:PrintIndex(T);break;

case 0:exit(1);

default:printf("error\n\t请继续选择:");

}

}

}

7、C程序设计总结

本次课程设计，使我对《数据结构》这门课程有了更深入的理解。《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。我的课程设计题目是线索二叉树的应用。刚开始做这个程序的时候，感到完全无从下手，甚至让我觉得完成这次程序设计根本就是不可能的，于是开始查阅各种资料以及参考文献，之后便开始着手写程序，写完运行时有很多问题。特别是实现线索二叉树的删除运算时很多情况没有考虑周全，经常运行出现错误，但通过同学间的帮助最终基本解决问题。

在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对VC有了更深入的了解。《数据结构》是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。上机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教学内容的目的；另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。此外，还有更重要的一点是：机器是比任何教师更严厉的检查者。因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。

通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。

总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。

8、致谢

能够完成这次课程设计必须感谢C++课程老师蔡敏、各位热心帮助我的同学们。

9、参考文献

[1] 贾宗璞、许合利，C语言程序设计，江苏：中国矿业大学出版社，2007.6

[2] 谭浩强，C程序设计（第二版），北京：清华大学出版社，2001.1

[3] https://www.wendangku.net/doc/f79477988.html,