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

湖南涉外经济学院课程设计报告课程名称：数据结构报告题目：二叉树的基本操作学生姓名：肖琳桂、康政、张小东、张帆所在学院：信息科学与工程学院专业班级：软工本1402学生学号：144300211、02、14、08指导教师：李春庭2015年12月31日课程设计任务书报告题目二叉树的基本操作完成时间2周学生姓名肖琳桂康政专业班级软工本1402指导教师李春庭职称讲师总体设计要求和主要功能设计一个程序，实现二叉树的创建以及二叉树的遍历（包括先序遍历、中序遍历、后序遍历和层次遍历），计算并输出二叉树的深度和结点个数，功能要求：1．二叉树以二叉链表存储，结点数据类型采用字符表示，按二叉树的先序遍历序列创建。2．用文本编辑器编写一个data.txt的文件,包含3个以上创建按二叉树的先序遍历序列(即序列中包含空树节点)，每个序列长度不少于10个，在运行程序时自动载入，也可以由键盘输入创建二叉树。|3．菜单功能：创建二叉树（二级菜单说明选择文件中的第几个，输出创建二叉树的深度及结点数，若失败则有相应提示），遍历序列（显示先序，中序，后序和层次遍历结果），结点的孩子信息，退出系统。工作内容及时间进度安排第17周：周1---周2：立题、论证方案设计周3---周5：程序设计及程序编码第18周：周1---周3：程序调试周4---周5：验收答辩摘要本课程设计主要说明如何在C++编程环境下实现二叉树的遍历，遍历方式包括:二叉树的先序遍历、中序遍历、后序遍历，层次遍历等四种遍历方式。同时，此次课程设计还包括了求二叉树深度和结点个数，结点的孩子信息，以及对文件的操作，用文件读取的方式实现对二叉树的建立。以通过此次课程设计，使学生充分掌握树的基本操作，以及对线性存储结构的理解。同时，在对树的遍历的操作过程中，同样是运用递归的方式实现遍历，在对树实现层次操作的时候，要求用循环队列的操作方式来实现层次遍历。此次课程设计对数据结构内容综合性的运用的要求较高。关键词：二叉树，先序遍历，中序遍历，后序遍历，层次遍历，节点，线性存储,节点的孩子信息目录课程设计任务书......................................................1一、需求分析........................................................41．问题描述.....................................................42．功能要求.....................................................4二、概要设计........................................................51.总体设计图....................................................52.数据结构设计..................................................53.算法设计......................................................54.主要模块及模块之间的关系......................................5三、详细设计........................................................61.结构体（或类）设计............................................62.主要模块实现的流程图.........................................63.算法设计......................................................7四、测试运行........................................................81．登录和主界面运行效果图.......................................82．运行说明.....................................................83.运行效果图...................................................8五、结论与心得.....................................................101.总体评价.....................................................102.所做的工作及体会.............................................10六、程序附录（源代码）.............................................13七、参考文献.......................................................204一、需求分析1．问题描述设计一个二叉树。二叉树形象地说即树中每个节点最多只有两个分支，它是一种重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表等。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历，层次遍历。以及能够从输入的数据中得知二叉树的叶子结点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。我们抽象出下列问题：实现文件操作，运用文件输入流，将已经写好二叉树序列的txt文本文件，加载到程序中，实现文件创建二叉树。然后采用链表存储的方式遍历二叉树（先序遍历、中序遍历、后序遍历、层次遍历）。层次遍历运用循环队列的方法实现，需要重新定义队头和队尾，以及队列的最大长度，并且在屏幕上实现输出显示。2．功能要求(1)用菜单的形式实现操作界面，提供（1—4）个功能选项，功能分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。(2)创建二叉树。要求用文件读取和键盘输入两种不同的方式实现二叉树的创建。二级菜单说明，输出创建二叉树的深度及结点数，若失败则有相应提示。(3)遍历序列。显示先序，中序，后序和层次遍历结果。先序遍历、中序遍历、后序遍历用递归的方法实现遍历。层次遍历，用循环队列的方法实现。(4)每次实现一项操作之后，要有相应的提示返回菜单。5二、概要设计1.总体设计图2.数据结构设计数据元素为字符，逻辑结构为树形结构，存储结构为二叉链式存储，系统操作的数据元素主要是创建一个二叉树，遍历序列。3.算法设计本系统主要用到的算法有先序遍历、中序遍历、后序遍历、层次遍历、创建二叉树和查找节点。从子菜单界面只能返回到主菜单界面，而不是退出程序。4.主要模块及模块之间的关系运行程序后直接进入“菜单主界面”模块，菜单显示分为4个模块，（1~4）分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。主界面中的各个模块都是独立运行，每完成一项操作后，返回主菜单模块。通过相应定义的函数（外部接口）实现，内部数据的改变由模块内部完成。主菜单遍历序列创建二叉树节点的孩子信息退出系统键盘输入文件输入中序遍历后序遍历层次遍历先序遍历6三、详细设计1.结构体（或类）设计typedefcharTElemType;typedefstructBiTNode{TElemTypedate;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;2.主要模块实现的流程图开始主菜单界面输入选择（1~4）Case=sel？退出系统创建二叉树遍历序列中序遍历层次遍历先序遍历后序遍历结点的孩子信息Case=1Case=2Case=4Case=373.算法设计先序遍历：voidPreOrderTraverse(BiTreeT){if(T){coutT-date;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);}}中序遍历：voidInOrderTraver(BiTreeT){if(T){InOrderTraver(T-lchild);coutT-date;InOrderTraver(T-rchild);}}后序遍历：voidPostOrderTraver(BiTreeT){if(T){PostOrderTraver(T-lchild);PostOrderTraver(T-rchild);coutT-date;}}层次遍历：voidccbl(BiTNode*b){BiTNode*p;BiTNode*q[MaxSize];intqm,h;qm=h=-1;h++;q[h]=b;while(qm!=h){qm=(qm+1)%MaxSize;p=q[qm];printf(%c,p-date);if(p-lchild!=NULL){h=(h+1)%MaxSize;q[h]=p-lchild;}if(p-rchild!=NULL){h=(h+1)%MaxSize;q[h]=p-rchild;}}}8四、测试运行1．登录和主界面运行效果图2．运行说明主程序运行后，直接到菜单选择界面。其中有(1—4个选项可以选择)1.创建二叉树2.遍历序列3.节点的孩子信息4.退出系统。除退出以外,每个功能模块运行完后，返回到主菜单界面，每个界面相互独立。3.运行效果图9表学生情况统计表序号姓名性别出生日期学号专业联系电话备注1康政男1994.12144300202软件工程15717488160组长2肖琳桂男1996.08144300211软件工程157175144943张小东男1994.07144300214软件工程4张帆男1995.08144300208软件工程10五、结论与心得1.总体评价在此次的课程设计中，由于不够细心，在程序设计中犯了一些错误，花了挺多的时间。但是经过一番思考并且在老师的帮助下，找到了导致程序错误的原因，经过几次修改和调试，程序能正常运行，并且能够完成课程设计任务中的大部分功能。同时在此次的课程设计中让我更深刻的了解了二叉树的基本操作，增加了对专业只是学习的兴趣。我想在以后的学习中，我们会继续努力，希望在计算机方面有好的成绩，也感谢老师给我们这次课程设计的机会，让我们认识到了自身的不足，让我们能够不断地完善自己!2.所做的工作及体会肖琳桂：编写程序和课程设计报告。课程设计中我主要担任程序设计的编写和设计报告的编写工作，经过两个星期的上机实践学习，使我对数据结构有了更进一步的认识和理解，也知道了要想学好它要重在实践，要通过不断的上机操作才能更好地学习它。通过实践我发现我的很多不足之处，然感觉理论上已经掌握，但在运用到实践的过程中仍有意想不到的困惑，因为自己对知识点的掌握不够熟悉，但通过学习有很大改进。在这次课程设计中使我知道了二又树的先序、中序、后序、层次遍历。同时，还包括了求二叉树深度和结点个数，结点的孩子信息，以及对文件的操作，用文件读取的方式实现对二叉树的建立。充分掌握树的基本操作，以及对线性存储结构的理解。也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在设计过程中，和同学们相互探讨，相互学习，相互监督。我学会了运筹帷幌，学会了宽容，学会了理解，也学会了做人与处世，这次课程设计对找来说受益良多。在今后的日子里，我会认真对待每一件事情，争取做到最好，努力将知识与实践相结合，不断巩固，加深所学的知识，做到学以致用。另外感谢老师的细心教导，以及同学们的帮助。11康政：编写程序和课程设计报告。我在小组中做了编写程序和撰写报告的工作。在编写程序时，遇到很多困难，例如缺少声明，调用函数错误等等。通过网上搜查，查询资料以及老师的指点帮助，完成