数据结构与算法课程设计线索二叉树的应用.doc

数学与计算机学院课程设计说明书课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 6014389 题 目: 线索二叉树的应用 年级/专业/班: 2010级软件1班 学 生 姓 名: 学 号: 127 开 始 时 间: 2011 年 12 月 9 日完 成 时 间: 2011 年 12 月 23 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5） 说明书（计算书、图纸、分析报告）撰写质量（45）总 分（100）指导教师签名： 年 月 日摘 要首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：线索化；先序遍历；中序遍历；后续遍历引 言 数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“线索二叉树的应用”，完成将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树的操作。本课程设计采用的编程环境为Microsoft Visual Stdio 2008。目 录 1需求分析32开发及运行平台43 概要设计54 详细设计75 调试分析126 测试结果137 结论18致 谢19参考文献20附 录21 1、需求分析 为了能更熟练精准的掌握二叉树的各种算法和操作，同时也为了开拓视野，综合运用所学的知识。为此，需要将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树，以实现线索树建立、插入、删除、恢复线索等。 中次系统要实现对二叉树的建立，以及线索化该二叉树，同时实现对其先序、中序、后序线索话的并输出结果。1.2测试数据 表1：入的二叉树结点序号和数据结点序号数据1 112 223 334 445 556 667778889992开发及运行平台开发平台：Microsoft Visual Studio 2008运行平台：Windows XP/2003/73 概要设计 3.1 ADT描述 ADT BiTree 数据对象：D=“树节点”； 数据关系：RH 若D=为空，则R=,Tree为空树； 若D仅有一个数据元素，则R=； 否则R=H详细描述如下：D中存在唯一的称之为根的节点root，它在关系H下无前驱；1. 若D-root，则存在对根以外剩余元素的一个划分D1、 D2.，Dm（m>0），并对任意jk（1jm，1km）有DjDk=；且对任意i（1im）唯一存在数据元素xiDi，有二元关系<root,xi>H。这里描述的是从总节点到各个子树根节点xi的边。2. 对应于D-root的划分，关系集H-<root,x1>， <root,x2>，.<root,xm>也有唯一的划分H1、H2.Hm(m>0)，并且对任意的jk（1jm，1km）有HjHk=，对任意的i（1im），Hi是Di上的二元关系，则（Di，H）是一颗树，且是root的子树。基本操作： void creat ();/创建一个二叉树。void inorder ();/中序便利。void ThTree:threpreorder ();/先序遍历二叉树。void ThTree:threinorder ();/中序遍历二叉树。void ThTree:threpostorder ();/后序遍历二叉树。void ThTree:destroy ();/删除线索二叉树。int main();/主函数。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,*s20; 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; /左右标志域si=q;if(i=1)root=q; /q为根接点elsej=i/2;if(i%2)=0)sj->lch=q;else sj->rch=q; /j为双亲结点编号cout<<"ni,x="cin>>i>>x; 4.3 新建操作void ThTree:creat() /建立二叉树ThreNode *q,*s20; 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; /左右标志域si=q;if(i=1)root=q; /q为根接点elsej=i/2;if(i%2)=0)sj->lch=q;else sj->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;docout<<"nn"cout<<"nn 1.建立二叉树"cout<<"nn 2.中序递归线索二叉树"cout<<"nn 3.先序线索化二叉树 "cout<<"nn 4.后续线索化二叉树"cout<<"nn 5.结束程序运行"cout<<"nn 请输入您的选择:"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);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;docout<<"nn"cout<<"nn 1.建立二叉树"cout<<"nn 2.中序递归线索二叉树"cout<<"nn 3.先序线索化二叉树 "cout<<"nn 4.后续线索化二叉树"cout<<"nn 5.结束程序运行"cout<<"nn 请输入您的选择:"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 调试分析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 严蔚敏，吴伟民. 数据结构题集(C语言版) .北京.清华大学出版社.2003年5月。3 杨秀金，数据结构(C+版) .北京.。4 朱战立.数据结构(C+语言描述)（第二版本）.北京.。5 胡学钢.数据结构(C语言版) . 北京.高等教育出版社. 2004年8月。6 杨金秀.数据结构（C语言版）.西安.电子科技大学出版社.2004年8月。 西华大学本科课程设计说明书规范化要求第一条说明书格式说明书（或计算书）手写、打印均可，需采用统一的课程设计用纸或模版。纸张大小A4，上下右各留，左边距的页边距。手写时用黑墨水工整书写；打印：1.5倍行距，正文字体使用小四号宋体，小标题使用小四号黑体，大标题使用四号黑体，章节标题使用小三号黑体、居中。页眉按“ XXXXXX（课程设计题目）”（5号）注写，但封面不能有页眉；页脚居中。第二条 课程设计说明书字数要求按学院根据本学科特点确定的字数。 第三条 装订课程设计资料装订顺序为：（1）封面（2）任务书（由指导教师填写）（3）目录、摘要及关键词摘要是说明书内容的简短陈述，一般200字左右。关键词是反映论文主题内容的通用技术词汇，一般为35词，并出现在摘要中。（4）正文（含引言及正文内容）（5）结论（6）致谢（7）参考文献（不少于6篇）参考文献必须是学生在课程设计中真正阅读过和运用过的，文献按照在正文中的出现顺序编号排列。各类文献的标注格式如下：著作：序号著者.译者.书名.出版社.出版时间.引用部分起止页期刊：序号 著者.译者.文章题目.期刊名.年份.卷号（期刊数）.引用部分起止页会议论文集：序号作者.译者.文章名.文集名.会址.开会年.出版者.出版时间.引用