数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码:题目: 线索二叉树的应用年级/专业/班: 2010级软件1班学生姓名:学号: 1127开始时间:2011 年12 月9 日完成时间:2011 年12 月23 日课程设计成绩：1指导教师签名：年月日摘要首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。

其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。

然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。

再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。

然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。

关键词：线索化；先序遍历；中序遍历；后续遍历线索二叉树的运用引言数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。

数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。

本课程设计的题目为“线索二叉树的应用”，完成将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树的操作。

本课程设计采用的编程环境为Microsoft Visual Stdio 2008。

目录1需求分析 (3)2开发及运行平台 (4)3 概要设计 (5)4 详细设计 (7)5 调试分析 (12)6 测试结果 (13)7 结论 (18)致谢 (19)参考文献 (20)附录 (21)1、需求分析为了能更熟练精准的掌握二叉树的各种算法和操作，同时也为了开拓视野，综合运用所学的知识。

为此，需要将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树，以实现线索树建立、插入、删除、恢复线索等。

1.1任务与分析中次系统要实现对二叉树的建立，以及线索化该二叉树，同时实现对其先序、中序、后序线索话的并输出结果。

1.2测试数据表1：入的二叉树结点序号和数据线索二叉树的运用- 3 -2开发及运行平台开发平台：Microsoft Visual Studio 2008运行平台：Windows XP/2003/73 概要设计3.1 ADT描述ADT BiTree{数据对象：D={“树节点”}；数据关系：R＝{H}若D=∮为空，则R=∮,Tree为空树；若D仅有一个数据元素，则R=∮；否则R={H}详细描述如下：D中存在唯一的称之为根的节点root，它在关系H下无前驱；1.若D-{root}≠∮，则存在对根以外剩余元素的一个划分D1、D2......，Dm（m>0），并对任意j≠k（1≦j≦m，1≦k≦m）有Dj∩Dk=∮；且对任意i（1≦i≦m）唯一存在数据元素xi∈Di，有二元关系<root,xi>∈H。

这里描述的是从总节点到各个子树根节点xi的边。

2.对应于D-{root}的划分，关系集H-{<root,x1>，<root,x2>，......<root,xm>}也有唯一的划分H1、H2......Hm(m>0)，并且对任意的j≠k（1≦j≦m，1≦k≦m）有Hj∩Hk=∮，对任意的i（1≦i≦m），Hi是Di上的二元关系，则（Di，{H}）是一颗树，且是root的子树。

基本操作：void creat ();//创建一个二叉树。

void inorder ();//中序便利。

void ThTree::threpreorder ();//先序遍历二叉树。

void ThTree::threinorder ();//中序遍历二叉树。

void ThTree::threpostorder ();//后序遍历二叉树。

void ThTree::destroy ();//删除线索二叉树。

int main();//主函数。

}线索二叉树的运用- 5 -3.2程序模块结构图2 程序模块结构3.2.1 结构体定义书的结构体定义如下：struct ThreNode //定义结点结构体 {ElemType data;ThreNode *lch;ThreNode *rch;int ltag,rtag;};3.3 各功能模块新建模块: void ThTree::creat ()新建二叉树并储存。

树类模块:void ThTree ()定义书的结点，孩子以及各成员函数。

先序遍历模块: void ThTree::threpreorder ()对树进行先序线索遍历。

中序遍历模块: void ThTree::threinorder ()对树进行中序线索遍历。

后序遍历模块: void ThTree::threpostorder()对树进行后序线索遍历。

删除模块: void ThTree::destroy ()：删除所有节点。

4 详细设计4.1结构体定义树的结构体定义如下：struct ThreNode //定义结点结构体{ThreType data;ThreNode *lch;ThreNode *rch;int ltag,rtag;};4.2 初始化构造函数初始化变量，定义双亲结点和左右标志域以及根结点：void ThTree::creat() //建立二叉树{ThreNode *q,*s[20]; ElemType x; int i,j;cout<<"\n请按二叉树的层序自上而下自左至右顺序组织数据"<<endl;cout<<"\n每次输入结点的序号和数据，假设根结点值是11；"<<endl;cout<<"\n那么输入应该是：1 11"<<endl;cout<<"\ni,x=";cin>>i>>x;while(i!=0&&x!=0){q=new ThreNode; //产生一个接点q->data=x;q->lch=NULL;q->rch=NULL;q->ltag=0;q->rtag=0; //左右标志域s[i]=q;if(i==1)root=q; //q为根接点else{j=i/2;if((i%2)==0)s[j]->lch=q;else s[j]->rch=q; //j为双亲结点编号线索二叉树的运用- 7 -} cout<<"\ni,x=";cin>>i>>x;}}4.3 新建操作void ThTree::creat() //建立二叉树 {ThreNode *q,*s[20]; ElemType x; int i,j;cout<<"\n 请按二叉树的层序自上而下自左至右顺序组织数据"<<endl;cout<<"\n 每次输入结点的序号和数据，假设根结点值是11；"<<endl;cout<<"\n 那么输入应该是：1 11"<<endl;cout<<"\ni,x=";cin>>i>>x;while(i!=0&&x!=0){q=new ThreNode; //产生一个接点q->data=x;q->lch=NULL;q->rch=NULL;q->ltag=0;q->rtag=0; //左右标志域s[i]=q;if(i==1)root=q; //q 为根接点else{j=i/2;if((i%2)==0)s[j]->lch=q;else s[j]->rch=q; //j 为双亲结点编号} cout<<"\ni,x=";cin>>i>>x;}}void ThTree::threpreorder(ThreNode *p,ThreNode *pre) //先根线索化二叉树 {if(p!=NULL){cout<<p->data<<" ";if(p->lch==NULL){p->lch=pre;p->ltag=1;}pre=p;if(p->ltag==0)threpreorder(p->lch,pre);threpreorder(p->rch,pre);4.4、录入信息int main (){int k;ThTree root0;do{cout<<"\n\n";cout<<"\n\n 1.建立二叉树";cout<<"\n\n 2.中序递归线索二叉树";cout<<"\n\n 3.先序线索化二叉树";cout<<"\n\n 4.后续线索化二叉树";cout<<"\n\n 5.结束程序运行";cout<<"\n\n 请输入您的选择:";cin>>k;switch(k)}4.5先序遍历线索化操作void ThTree::threpreorder(ThreNode *p,ThreNode *pre) //先根线索化二叉树{if(p!=NULL){cout<<p->data<<" ";if(p->lch==NULL){p->lch=pre;p->ltag=1;}pre=p;if(p->ltag==0)threpreorder(p->lch,pre);threpreorder(p->rch,pre);}}线索二叉树的运用- 9 -4.6中序遍历线索化操作void ThTree::threinorder(ThreNode *p,ThreNode *pre) //中根线索化二叉树 {if(p!=NULL){threinorder(p->lch,pre);{p->lch=pre;p->ltag=1;}if(pre!=0&&pre->rch==0){pre->rch=p;pre->rtag=1;}pre=p;threinorder(p->rch,pre);}}4.7后续遍历线索化操作void ThTree::threpostorder(ThreNode *p,ThreNode *pre)//后根线索化二叉树 {if(p!=NULL){threpostorder(p->lch,pre);threpostorder(p->rch,pre);cout<<p->data<<" ";if(p->lch==NULL){p->lch=pre;p->ltag=1;}pre=p;}}4.8主函数int main (){int k;ThTree root0;do{cout<<"\n\n";cout<<"\n\n 1.建立二叉树";cout<<"\n\n 2.中序递归线索二叉树";cout<<"\n\n 3.先序线索化二叉树 ";cout<<"\n\n 4.后续线索化二叉树";cout<<"\n\n 5.结束程序运行";cout<<"\n\n 请输入您的选择:";cin>>k;switch(k){case 1:{cout<<"\n 建立二叉树：";root0.creat();}break;case 2:{cout<<"\n 中序递归线索二叉树的结果：";root0.threinorder();}break;case 3:{cout<<"\n 先序递归线索二叉树的结果：";root0.threpreorder();}break;case 4:{cout<<"\n 后续递归线索化二叉树的结果：";root0.threpostorder();}break;}}while(k>=0&&k<5);_getch();return 0;}5 调试分析线索二叉树的运用- 11 -5.1测试数据测试数据见表1.5.2调试问题在测试过程中没有给测试者提供相关的录入信息要求，导致录入要求不合格，程序不能正常运行，经过添加了录入信息提示之后就解决了这个问题。