线索二叉树课程设计说明书模板范本

年4月19日线索二叉树课程设计说明书模板文档仅供参考数学与计算机学院课程设计说明书课程名称:数据结构与算法课程设计课程代码:6014389题目:线索二叉树的应用年级/专业/班:级软件1班学生姓名:学号:31开始时间:年12月9日完成时间:年12月23日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书（计算书、图纸、分析报告）撰写质量（45）总分（100）指导教师签名：年月日摘要首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：线索化；先序遍历；中序遍历；后续遍历

引言数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“线索二叉树的应用”，完成将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树的操作。本课程设计采用的编程环境为MicrosoftVisualStdio。

TOC\o"1-2"\h\z目录TOC\o"1-2"\h\z1需求分析 32开发及运行平台 43概要设计 54详细设计 75调试分析 126测试结果 137结论 18致谢 19参考文献 20附录 21

1、需求分析为了能更熟练精准的掌握二叉树的各种算法和操作，同时也为了开拓视野，综合运用所学的知识。为此，需要将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树，以实现线索树建立、插入、删除、恢复线索等。1.1任务与分析中次系统要实现对二叉树的建立，以及线索化该二叉树，同时实现对其先序、中序、后序线索话的并输出结果。1.2测试数据表1：入的二叉树结点序号和数据结点序号数据111222333444555666777888999

2开发及运行平台开发平台：MicrosoftVisualStudio运行平台：WindowsXP//7

3概要设计3.1ADT描述ADTBiTree{数据对象：D={“树节点”}；数据关系：R＝{H}若D=∮为空，则R=∮,Tree为空树；若D仅有一个数据元素，则R=∮；否则R={H}详细描述如下：D中存在唯一的称之为根的节点root，它在关系H下无前驱；若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的边。对应于D-{root}的划分，关系集H-{<root,x1>，<root,x2>，<root,xm>}也有唯一的划分H1、H2Hm(m>0)，而且对任意的j≠k（1≦j≦m，1≦k≦m）有Hj∩Hk=∮，对任意的i（1≦i≦m），Hi是Di上的二元关系，则（Di，{H}）是一颗树，且是root的子树。基本操作：voidcreat();//创立一个二叉树。voidinorder();//中序便利。voidThTree::threpreorder();//先序遍历二叉树。voidThTree::threinorder();//中序遍历二叉树。voidThTree::threpostorder();//后序遍历二叉树。voidThTree::destroy();//删除线索二叉树。intmain();//主函数。}3.2程序模块结构图2程序模块结构结构体定义书的结构体定义如下：structThreNode//定义结点结构体{ ElemTypedata;ThreNode*lch; ThreNode*rch; intltag,rtag;};3.3各功能模块新建模块:voidThTree::creat()新建二叉树并储存。树类模块:voidThTree()定义书的结点，孩子以及各成员函数。先序遍历模块:voidThTree::threpreorder()对树进行先序线索遍历。中序遍历模块:voidThTree::threinorder()对树进行中序线索遍历。后序遍历模块:voidThTree::threpostorder()对树进行后序线索遍历。删除模块:voidThTree::destroy()：删除所有节点。

4详细设计4.1结构体定义树的结构体定义如下：structThreNode//定义结点结构体{ ThreTypedata;ThreNode*lch; ThreNode*rch; intltag,rtag;};4.2初始化构造函数初始化变量，定义双亲结点和左右标志域以及根结点：voidThTree::creat()//建立二叉树{ ThreNode*q,*s[20];ElemTypex;inti,j; cout<<"\n请按二叉树的层序自上而下自左至右顺序组织数据"<<endl; cout<<"\n每次输入结点的序号和数据，假设根结点值是11；"<<endl; cout<<"\n那么输入应该是：111"<<endl; cout<<"\ni,x="; cin>>i>>x; while(i!=0&&x!=0) { q=newThreNode;//产生一个接点 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;elses[j]->rch=q;//j为双亲结点编号 } cout<<"\ni,x=";cin>>i>>x;}}4.3新建操作voidThTree::creat()//建立二叉树{ ThreNode*q,*s[20];ElemTypex;inti,j; cout<<"\n请按二叉树的层序自上而下自左至右顺序组织数据"<<endl; cout<<"\n每次输入结点的序号和数据，假设根结点值是11；"<<endl; cout<<"\n那么输入应该是：111"<<endl; cout<<"\ni,x="; cin>>i>>x; while(i!=0&&x!=0) { q=newThreNode;//产生一个接点 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;elses[j]->rch=q;//j为双亲结点编号 } cout<<"\ni,x=";cin>>i>>x;}}voidThTree::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、录入信息intmain(){ intk;ThTreeroot0; do{cout<<"\n\n"; cout<<"\n\n1.建立二叉树"; cout<<"\n\n2.中序递归线索二叉树"; cout<<"\n\n3.先序线索化二叉树"; cout<<"\n\n4.后续线索化二叉树"; cout<<"\n\n5.结束程序运行"; cout<<"\n\n请输入您的选择:";cin>>k; switch(k)}4.5先序遍历线索化操作voidThTree::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.6中序遍历线索化操作voidThTree::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后续遍历线索化操作voidThTree::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主函数intmain(){ intk;ThTreeroot0; do{cout<<"\n\n"; cout<<"\n\n1.建立二叉树"; cout<<"\n\n2.中序递归线索二叉树"; cout<<"\n\n3.先序线索化二叉树"; cout<<"\n\n4.后续线索化二叉树"; cout<<"\n\n5.结束程序运行"; cout<<"\n\n请输入您的选择:";cin>>k; switch(k) {case1:{cout<<"\n建立二叉树："; root0.creat(); }break; case2:{cout<<"\n中序递归线索二叉树的结果："; root0.threinorder(); }break; case3:{cout<<"\n先序递归线索二叉树的结果："; root0.threpreorder(); }break; case4:{cout<<"\n后续递归线索化二叉树的结果："; root0.threpostorder(); }break; } }while(k>=0&&k<5); _getch(); return0;}5调试分析5.1测试数据测试数据见表1.5.2调试问题在测试过程中没有给测试者提供相关的录入信息要求，导致录入要求不合格，程序不能正常运行，经过添加了录入信息提示之后就解决了这个问题。5.3算法时间复杂度录入：时间复杂度为O(n);先根线索化二叉树:时间复杂度为O(n);中根线索化二叉树:时间复杂度为O(n);后根线索化二叉树:时间复杂度为O(n);删除结点:时间复杂度为O(n)；5.4经验和体会在本次课程设计中主要是对图的数据结构操作，所有刚开始对知识不是很熟悉操作起来有一定难度，容易在程序的关键地方但经过翻阅教材能较好的解决问题。

6测试结果6.1录入信息图3录入信息界面

6.2新建模块图5查询景点信息界面

6.3中序递归线索化模块图6中序递归线索化界面6.4先序递归线索化模块图7先序递归线索化界面

6.5后序递归线索化模块图8后序递归线索化界面

结论本次课程设计“二叉树的线索化”按照任务书相应的要求成功的完成了任务，由于本课程设计涉及先序、后序、中序的线索化，以及相应的相关插入删除的操作，因此对算法的设计以及相关函数的调用要求很高，需要经过重复的查看相关书籍才能完成。

致谢在本次课程设计过程中，首先感谢辅导老师周立章，在数据结构课堂上为课程设计需要的前期知识打下了基础，在课程设计过程中抽出休息时间来做相应的课程设计指导。同时在这次课程设计中，也要感谢许多乐意同学对我不懂的地方的指导和耐心讲解

参考文献[1]严蔚敏，吴伟民.数据结构.北京.清华大学出版社出版。[2]严蔚敏，吴伟民.