数据结构课程设计报告-二叉树

1、湖南涉外经济学院课程设计报告课程名称：数据结构报告题目：二叉树的基本操作学生姓名：肖琳桂、康政、张小东、张帆所在学院：信息科学与工程学院专业班级：软工本1402学生学号： 144300211、02、14、08指导教师：李春庭2015年 12 月 31日课程设计任务书报告题目二叉树的基本操作完成时间2 周肖琳桂专 业软工本学生姓名指导教师李春庭职称讲师康政班级1402总体设计要求和主要功能设计一个程序，实现二叉树的创建以及二叉树的遍历（包括先序遍历、中序遍历、后序遍历和层次遍历），计算并输出二叉树的深度和结点个数，功能要求：1二叉树以二叉链表存储，结点数据类型采用字符表示，按二叉树的先序遍历序列

2、创建。2用文本编辑器编写一个data.txt的文件 , 包含 3 个以上创建按二叉树的先序遍历序列 ( 即序列中包含空树节点 ) ，每个序列长度不少于10 个，在运行程序时自动载入，也可以由键盘输入创建二叉树。|3菜单功能：创建二叉树（二级菜单说明选择文件中的第几个，输出创建二叉树的深度及结点数，若失败则有相应提示），遍历序列（显示先序，中序，后序和层次遍历结果），结点的孩子信息，退出系统。工作内容及时间进度安排第 17 周：周 1- 周 2：立题、论证方案设计周 3- 周 5 ：程序设计及程序编码第 18周：周 1- 周 3 ：程序调试周 4- 周 5 ：验收答辩摘要本课程设计主要说明如何在

3、C+编程环境下实现二叉树的遍历，遍历方式包括 : 二叉树的先序遍历、中序遍历、后序遍历，层次遍历等四种遍历方式。同时，此次课程设计还包括了求二叉树深度和结点个数， 结点的孩子信息， 以及对文件的操作，用文件读取的方式实现对二叉树的建立。 以通过此次课程设计， 使学生充分掌握树的基本操作， 以及对线性存储结构的理解。 同时，在对树的遍历的操作过程中，同样是运用递归的方式实现遍历， 在对树实现层次操作的时候， 要求用循环队列的操作方式来实现层次遍历。 此次课程设计对数据结构内容综合性的运用的要求较高。关键词：二叉树，先序遍历， 中序遍历，后序遍历， 层次遍历，节点，线性存储 , 节点的孩子信息目录

4、课程设计任务书1一、需求分析41问题描述42功能要求4二、概要设计51. 总体设计图52. 数据结构设计53. 算法设计54. 主要模块及模块之间的关系5三、详细设计61. 结构体（或类）设计62.主要模块实现的流程图63. 算法设计7四、测试运行81登录和主界面运行效果图82运行说明83.运行效果图8五、结论与心得101. 总体评价102. 所做的工作及体会10六、程序附录（源代码）13七、参考文献20一、需求分析1问题描述设计一个二叉树。 二叉树形象地说即树中每个节点最多只有两个分支， 它是一种重要的数据类型。 可以运用于建立家谱， 公司所有的员工的职位图， 以及各种事物的分类和各种机构的

5、职位图表等。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历，层次遍历。以及能够从输入的数据中得知二叉树的叶子结点的个数， 二叉树的深度。 在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。我们抽象出下列问题： 实现文件操作，运用文件输入流， 将已经写好二叉树序列的 txt 文本文件，加载到程序中， 实现文件创建二叉树。然后采用链表存储的方式遍历二叉树（先序遍历、中序遍历、后序遍历、层次遍历）。层次遍历运用循环队列的方法实现，需要重新定义队头和队尾，以及队列的最大长度，并且在屏幕上实现输出显示。2功能要求(1) 用菜单的形式实现操作界面，提供（ 14）个功

6、能选项，功能分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。(2) 创建二叉树。要求用文件读取和键盘输入两种不同的方式实现二叉树的创建。二级菜单说明，输出创建二叉树的深度及结点数，若失败则有相应提示。(3) 遍历序列。显示先序，中序，后序和层次遍历结果。先序遍历、中序遍历、后序遍历用递归的方法实现遍历。层次遍历，用循环队列的方法实现。(4) 每次实现一项操作之后，要有相应的提示返回菜单。4二、概要设计1. 总体设计图主菜单创建二叉树遍历序列节点的孩子信退出系统息键文先中后层盘件序序序次输输遍遍遍遍入入历历历历2. 数据结构设计数据元素为字符， 逻辑结构为树形结构， 存储结构为二叉链式存储

7、， 系统操作的数据元素主要是创建一个二叉树，遍历序列。3. 算法设计本系统主要用到的算法有先序遍历、中序遍历、后序遍历、层次遍历、创建二叉树和查找节点。从子菜单界面只能返回到主菜单界面，而不是退出程序。4. 主要模块及模块之间的关系运行程序后直接进入“菜单主界面”模块，菜单显示分为4 个模块，（14）分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。主界面中的各个模块都是独立运行，每完成一项操作后， 返回主菜单模块。通过相应定义的函数（外部接口）实现，内部数据的改变由模块内部完成。5三、详细设计1. 结构体（或类）设计typedef char TElemType;typedef struc

8、t BiTNodeTElemType date;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;2. 主要模块实现的流程图开始主菜单界面输入选择（ 14）Case=sel？Case=4退出系统Case=1创建二叉树Case=2遍历序列先序遍历中序遍历后序遍历层次遍历Case=3结点的孩子信 息63. 算法设计先序遍历：void PreOrderTraverse(BiTree T) if(T) cout<<T->date; PreOrderTraverse(T->lchild); PreOrderTraverse(T->

9、;rchild); 中序遍历：void InOrderTraver(BiTree T) if(T) InOrderTraver(T->lchild); cout<<T->date; InOrderTraver(T->rchild); 后序遍历：void PostOrderTraver(BiTree T) if(T) PostOrderTraver(T->lchild); PostOrderTraver(T->rchild); cout<<T->date; 层次遍历：void ccbl(BiTNode *b) BiTNode *p;Bi

10、TNode *qMaxSize;int qm,h;qm=h=-1;h+; qh=b;while(qm != h) qm=(qm+1)%MaxSize; p=qqm; printf("%c ",p->date); if(p->lchild!=NULL) h=(h+1)%MaxSize;qh=p->lchild; if(p->rchild!=NULL) h=(h+1)%MaxSize; qh=p->rchild; 7四、测试运行1登录和主界面运行效果图2运行说明主程序运行后，直接到菜单选择界面。其中有(1 4 个选项可以选择 )1. 创建二叉树 2

11、. 遍历序列 3. 节点的孩子信息4. 退出系统。除退出以外 , 每个功能模块运行完后，返回到主菜单界面，每个界面相互独立。3. 运行效果图8表 学生情况统计表序姓名性出生日期学号专业联系电话备注号别1康政男1994.12144300202软件工长2肖琳桂男1996.08144300211软件工程157175144943张小东男1994.07144300214软件工程4张帆男1995.08144300208软件工程9五、结论与心得1. 总体评价在此次的课程设计中， 由于不够细心， 在程序设计中犯了一些错误， 花了挺多的时间。但是经过一番思考并且在老师的帮助下， 找到了

12、导致程序错误的原因，经过几次修改和调试， 程序能正常运行， 并且能够完成课程设计任务中的大部分功能。同时在此次的课程设计中让我更深刻的了解了二叉树的基本操作， 增加了对专业只是学习的兴趣。 我想在以后的学习中， 我们会继续努力， 希望在计算机方面有好的成绩， 也感谢老师给我们这次课程设计的机会， 让我们认识到了自身的不足，让我们能够不断地完善自己 !2.所做的工作及体会肖琳桂：编写程序和课程设计报告。 课程设计中我主要担任程序设计的编写和设计报告的编写工作， 经过两个星期的上机实践学习， 使我对数据结构有了更进一步的认识和理解，也知道了要想学好它要重在实践， 要通过不断的上机操作才能更好地学习

13、它。通过实践我发现我的很多不足之处， 然感觉理论上已经掌握， 但在运用到实践的过程中仍有意想不到的困惑， 因为自己对知识点的掌握不够熟悉， 但通过学习有很大改进。在这次课程设计中使我知道了二又树的先序、 中序、后序、层次遍历。同时，还包括了求二叉树深度和结点个数， 结点的孩子信息， 以及对文件的操作， 用文件读取的方式实现对二叉树的建立。 充分掌握树的基本操作， 以及对线性存储结构的理解。也培养了我如何去把握一件事情， 如何去做一件事情， 又如何完成一件事情的方法和技巧。在设计过程中，和同学们相互探讨，相互学习，相互监督。我学会了运筹帷幌，学会了宽容，学会了理解，也学会了做人与处世，这次课程设

14、计对找来说受益良多。在今后的日子里， 我会认真对待每一件事情， 争取做到最好， 努力将知识与实践相结合，不断巩固，加深所学的知识，做到学以致用。另外感谢老师的细心教导，以及同学们的帮助。10康政：编写程序和课程设计报告。 我在小组中做了编写程序和撰写报告的工作。 在编写程序时，遇到很多困难， 例如缺少声明，调用函数错误等等。 通过网上搜查，查询资料以及老师的指点帮助， 完成了很多任务。 作为基础不是很好的学生， 我在克服自己知识不足的过程中也在努力学习新的知识， 运用不同的原理编写出不同的算法。也学习到，算法不能盲目抄袭，很多东西是不同的，必须通过自己的思考和努力的钻研才能写出一套完整的代码，

15、 不可心急，越是急越不可能精细的完成任务。撰写报告的时候， 很多地方因细节问题处理不好导致出了大大小小很多漏洞，不能很精细的完成指定的任务。从中我也明白了，做一件事，尤其是耗时的编写程序的问题，不能心急也不能马虎，也许一点点出错整个程序就会崩溃，还要重新一点点的检查才能找出问题， 大大降低了办事效率。 所以，今后要做的第一件事是慢慢巩固检出， 打好根基。第二件事是沉下心来认真做事， 不能毛手毛脚，从头到尾认真细致的做下去， 避免出错惹出更多的麻烦。 这次的程序设计使我受益匪浅，学到了很多，做了很多。希望以后可以更多的做这种任务，巩固知识，学习新的知识，有了这些经验可以做的更好。张小东：查找资料

16、和打印。 这次我在小组中做的事情是查询资料和打印排版。 虽然因为我的专业底子差一点， 现在暂时只能在程序设计时查找一些需要用到的专业资料，帮助组员完成设计， 但我相信下一次我不会仅此于此。 这次程序设计我的收获还是很大了， 让我懂得了学好专业知识， 并不是自己想象中的难， 而是你自己是否去努力了。在查找资料的过程中， 我是边查边学自己不会的知识点。 查找途中也遇到了一些当时不能理解的知识点， 但经过同学的细心解答， 最后一些难掌握的知识点都被基本掌握。 这让我懂得编程过程需要很大的耐心， 而且要有良好的思维和扎实的专业基础知识，所以我需要努力的学习，发现自身不足之处并努力改正他，逐步提高自身的

17、能力， 不断取得进步。 通过这次课程设计， 我认识到知识运用的重要性，并且努力加深对基础知识的理解， 从中了解自己需要学习的东西并学会自学。作为一名计算机专业的学生，今后我会加紧学习，学好专业知识，为将来打下坚实的基础。11张帆：查找资料和打印。 这次我在小组中做的事情是查询资料， 打印排版。 虽然这些工作并不是主要任务， 但是我用心对待， 认真为做程序的同学查找资料， 为他们挑选所需要的代码以及算法， 及时反馈给他们信息。 因为基础不是很好， 经常会剪裁到一些不是很合适的代码， 我们通过共同分析， 共同筛选， 最终也获得了很多收获。通过和他们一起分析代码， 我也涨了很多知识。 懂的了二叉树的

18、算法，数据类型等等。 报告的排版也是一项需要耐心的工作， 通过晚上的时间， 我认认真真的对所写的设计报告进行了排版， 把一些不符合文本框架或者有代码错误的都进行了细致的修改， 保证了设计报告的质量。 从这次的程序设计中， 我学到了很多。认认真真做一件事情不会有错， 用什么态度做什么事会得到什么样的回报。并且我认为数据结果也不是很难的科目，认真花时间去琢磨一定不会落下很多。所以以后我会细致做事，并在闲暇时间补习功课，争取尽快补习好原来的知识，再学习新的知识为自己充电。12六、程序附录（源代码）#include<iostream>#include<fstream>#incl

19、ude<stdlib.h>using namespace std;typedef char TElemType;#define MaxSize 1000int i;typedef struct BiTNodeTElemType date;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Destory(BiTree &T);/函数声明char input255;void Interface();void sjecs(BiTree &T);void jp(BiTree &T);/键盘void wj(BiTr

20、ee &T);/文件void CreateBiTree(BiTree &T);int Count(BiTree T);int Deep(BiTree T);void PreOrderTraverse(BiTree T);/先序void InOrderTraver(BiTree T);/中序void PostOrderTraver(BiTree T);/后序void ccbl(BiTNode *b);/层次遍历void blxljm();void locate(BiTree T,char x);void main()/主函数Interface();BiTree T=NULL;bo

21、ol End=false;char sel;13char x;int p=1;int q=1;doInterface();fflush(stdin);char select=cin.get();system("cls");switch(select)case'1':cout<<" 创建二叉树： n"sjecs(T);break; case'2': cout<<"nt遍历序列 n"doblxljm();cout<<"n选择： "fflush(stdi

22、n);sel=cin.get();p=1;switch(sel)case'1':cout<<"n先序遍历二叉树的输出顺序：n"PreOrderTraverse(T);cout<<"n"system("pause");system("cls");break;case'2':cout<<"n中 序 遍 历 二 叉 树 的 输 出 顺 序 ：n"InOrderTraver(T);cout<<"n"sys

23、tem("pause");system("cls");break;case'3':cout<<"n后 序 遍 历 二 叉 树 的 输 出 顺 序 ：n"PostOrderTraver(T);cout<<"n"system("pause");system("cls");break ;case'4':cout<<"n层 次 遍 历 二 叉 树 的 输 出 顺 序 ： n"ccbl(T);cou

24、t<<"n"system("pause");system("cls");break;case'5': p=0;while(p);break;case'3': do system("cls");q=1;14cout<<"n-结点的孩子信息：-n"cout<<"（如果节点不存在 , 不返回任何信息，按任意键返回子菜单） n"cout<<"输入要查找的节点： "cin>>

25、x;locate(T,x);system("pause");system("cls");cout<<"n-菜单信息： -n"cout<<"nt0.输入返回主菜单 n"cout<<"t1.继续查找节点 n"docout<<"t请选择： "cin>>q;if(q!=0&&q!=1) cout<<"输入格式不对请重新输入n"while(q!=0&&q!=1);

26、while(q);break;case'4':End=true;system("pause");while(!End);void locate(BiTree T,char x) /在二叉树 T 中查找值为 x 的节点BiTree p;p=T;if(T=NULL) return;else if(T->date=x)cout<<p->date;if(T->lchild)cout<<"t"<<"节点的左孩子："<<T->lchild->date&l

27、t;<"n"else cout<<"t"<<"节点没有左孩子 n"if(T->rchild)cout<<"t节点的右孩子："<<T->rchild->date<<"n"else cout<<"t"<<"节点没有右孩子 n"else p=T->lchild;15if(p) locate(T->lchild,x);locate(T->r

28、child,x);void Interface()/菜单界面函数system("cls");cout<<"nt-遍历序列 -n"cout<<"tt1.创建二叉树 n"cout<<"tt2.遍历序列 n"cout<<"tt3.结点的孩子信息 n"cout<<"tt4.退出系统 n"cout<<"tt请选择（ 14）： "cout<<"nt-n"void b

29、lxljm()/遍历序列界面函数system("cls");cout<<"nt-二叉树-n"cout<<"t（如果没创建二叉树 , 不返回任何信息，按5 返回主菜单） n"cout<<"tt1.先序遍历二叉树 n"cout<<"tt2.中序遍历二叉树 n"cout<<"tt3.后序遍历二叉树 n"cout<<"tt4.层次遍历二叉树 n"cout<<"tt5.返回

30、主菜单 n"cout<<"tt请选择（ 15）： "cout<<"nt-n"int Count(BiTree T)/计算节点数量if(T=NULL)return 0;return 1+Count(T->lchild)+Count(T->rchild);16int Deep(BiTree T)/计算二叉树的度if(T=NULL)return 0;int u=Deep(T->lchild);int v=Deep(T->rchild);if(u>v)return (u+1);return (v+1

31、);void sjecs(BiTree &T)/选择输入模式 , 新建二叉树bool End=false;if(T)Destory(T);T=NULL;cout<<" 请选择输入二叉树序列模式：（ 1：键盘输入 2. 文件输入 3. 返回主菜单） "<<endl;dochar Selection=cin.get();switch( Selection)case'1': jp(T);break;case'2':wj(T);break;case'3':End=true;while (!End);vo

32、id jp(BiTree &T)/键盘输入cout<<" 输入按先序建立二叉树结点序列:t"cout<<" 例如 :ABDECFHGIJn"cout<<" 输入 :"cin>>input;int i=0;CreateBiTree(T);int num=Count(T);int deep=Deep(T);17cout<<"二叉树创建成功！ n"cout<<"此二叉树共有 "<<num<<&quo

33、t;个结点 n"cout<<"且该二叉树的深度为： "<< deep<<"（按 3 返回主菜单界面）n"cout<<" 请输入选项： "void wj(BiTree &T)/文件输入ifstream fi("a.txt");if(!fi)cout<<"数据文件不存在！ n"exit(0);fi>>input;int i=0;CreateBiTree(T);int num=Count(T);int deep=Deep(T);cout<<"二叉树创建成功！ n"cout<<"此二叉树共有 "<<num<<"个结点 n"cout<<"且该二叉树的深度为： "<< dee