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

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

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

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

4、的孩子信息目录课程设计任务书 2一、需求分析 51问题描述 52功能要求 5二、概要设计 61. 总体设计图 62. 数据结构设计 63. 算法设计 64. 主要模块及模块之间的关系 7三、详细设计 71. 结构体（或类）设计 72. 主要模块实现的流程图 73. 算法设计 9四、测试运行 101登录和主界面运行效果图 102运行说明 103. 运行效果图 10五、结论与心得 111. 总体评价 112. 所做的工作及体会 11六、程序附录（源代码） 15七、参考文献 17一、需求分析1问题描述设计一个二叉树。 二叉树形象地说即树中每个节点最多只有两个分支， 它是 一种重要的数据类型。 可以运

5、用于建立家谱， 公司所有的员工的职位图， 以及各 种事物的分类和各种机构的职位图表等。二叉树是通过建立一个链式存储结构， 达到能够实现前序遍历，中序遍历，后序遍历，层次遍历。以及能够从输入的数 据中得知二叉树的叶子结点的个数， 二叉树的深度。 在此， 二叉树的每一个结点 中必须包括： 值域，左指针域，右指针域。我们抽象出下列问题： 实现文件操作， 运用文件输入流， 将已经写好二叉树序列的 txt 文本文件，加载到程序中， 实现 文件创建二叉树。然后采用链表存储的方式遍历二叉树(先序遍历、中序遍历、 后序遍历、层次遍历)。层次遍历运用循环队列的方法实现，需要重新定义队头 和队尾，以及队列的最大长

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

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

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

9、rderTraverse(T->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 *

10、b) BiTNode *p;BiTNode *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; 四、测试运行 1登录和主界面运行效果图2运行说明主程序运行后，直接到菜单选择界面。其中有 (14 个选项可以

11、选择 )1. 创建二叉树 2. 遍历序列 3. 节点的孩子信息 4. 退出系统。除退出以外 , 每个功能模块运行完后，返回到主菜单界面，每个界面相互独3. 运行效果图表 学生情况统计表序 号姓名性出生日期别学号专业联系电话备注1康政男2软件工程组长2肖琳桂男1软件工程3张小东男4软件工程4张帆男8软件工程五、结论与心得1. 总体评价在此次的课程设计中， 由于不够细心， 在程序设计中犯了一些错误， 花了挺 多的时间。但是经过一番思考并且在老师的帮助下， 找到了导致程序错误的原因， 经过几次修改和调试， 程序能正常运行， 并且能够完成课程设计任务中的大部分 功能。同时在此次的课程设计中让我更深刻的

12、了解了二叉树的基本操作， 增加了 对专业只是学习的兴趣。 我想在以后的学习中， 我们会继续努力， 希望在计算机 方面有好的成绩， 也感谢老师给我们这次课程设计的机会， 让我们认识到了自身 的不足，让我们能够不断地完善自己 !2. 所做的工作及体会肖琳桂：编写程序和课程设计报告。 课程设计中我主要担任程序设计的编写和设计报 告的编写工作， 经过两个星期的上机实践学习， 使我对数据结构有了更进一步的 认识和理解， 也知道了要想学好它要重在实践， 要通过不断的上机操作才能更好 地学习它。 通过实践我发现我的很多不足之处， 然感觉理论上已经掌握， 但在运 用到实践的过程中仍有意想不到的困惑， 因为自己

13、对知识点的掌握不够熟悉， 但 通过学习有很大改进。在这次课程设计中使我知道了二又树的先序、 中序、后序、层次遍历。 同时， 还包括了求二叉树深度和结点个数， 结点的孩子信息， 以及对文件的操作， 用文 件读取的方式实现对二叉树的建立。 充分掌握树的基本操作， 以及对线性存储结 构的理解。 也培养了我如何去把握一件事情， 如何去做一件事情， 又如何完成一 件事情的方法和技巧。在设计过程中，和同学们相互探讨，相互学习，相互监督。我学会了运筹帷 幌，学会了宽容，学会了理解，也学会了做人与处世，这次课程设计对找来说受 益良多。在今后的日子里， 我会认真对待每一件事情， 争取做到最好， 努力将知识与 实

14、践相结合，不断巩固，加深所学的知识，做到学以致用。另外感谢老师的细心教导，以及同学们的帮助。康政：编写程序和课程设计报告。 我在小组中做了编写程序和撰写报告的工作。 在 编写程序时，遇到很多困难，例如缺少声明，调用函数错误等等。 通过网上搜查， 查询资料以及老师的指点帮助， 完成了很多任务。 作为基础不是很好的学生， 我 在克服自己知识不足的过程中也在努力学习新的知识， 运用不同的原理编写出不 同的算法。也学习到，算法不能盲目抄袭，很多东西是不同的，必须通过自己的 思考和努力的钻研才能写出一套完整的代码， 不可心急， 越是急越不可能精细的 完成任务。撰写报告的时候， 很多地方因细节问题处理不好

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

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

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

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

19、 namespace std;typedef char TElemType;#define MaxSize 1000int i;typedef struct BiTNodeTElemType date;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Destory(BiTree &T); 入返回主菜单 n"cout<<"t1. 继续查找节点 n"docout<<"t 请选择： "cin>>q;if(q!=0&&q!=1) cout<<" 输入格式不对请重新输入 n"while(q!=0&&q!=1);while(q);break;case'4':End=true;system("pause");while(!End);void locate(BiTree T,char x)建二叉树 n"cout<<"tt2.遍历序列 n"cout<<&