数据结构课程设计报告-二叉树(共31页).doc

精选优质文档-倾情为你奉上湖南涉外经济学院课程设计报告课程名称： 数据结构 报告题目： 二叉树的基本操作 学生姓名： 肖琳桂、康政、张小东、张帆 所在学院： 信息科学与工程学院 专业班级： 软工本1402 学生学号： 、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问题描述设计一个二叉树。二叉树形象地说即树中每个节点最多只有两个分支，它是一种重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表等。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历，层次遍历。以及能够从输入的数据中得知二叉树的叶子结点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。我们抽象出下列问题：实现文件操作，运用文件输入流，将已经写好二叉树序列的txt文本文件，加载到程序中，实现文件创建二叉树。然后采用链表存储的方式遍历二叉树（先序遍历、中序遍历、后序遍历、层次遍历）。层次遍历运用循环队列的方法实现，需要重新定义队头和队尾，以及队列的最大长度，并且在屏幕上实现输出显示。2功能要求(1)用菜单的形式实现操作界面，提供（14）个功能选项，功能分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。(2)创建二叉树。要求用文件读取和键盘输入两种不同的方式实现二叉树的创建。二级菜单说明，输出创建二叉树的深度及结点数，若失败则有相应提示。(3)遍历序列。显示先序，中序，后序和层次遍历结果。先序遍历、中序遍历、后序遍历用递归的方法实现遍历。层次遍历，用循环队列的方法实现。(4)每次实现一项操作之后，要有相应的提示返回菜单。二、概要设计1.总体设计图主菜单遍历序列创建二叉树节点的孩子信息退出系统2.数据结构设计 数据元素为字符，逻辑结构为树形结构，存储结构为二叉链式存储，系统操作的数据元素主要是创建一个二叉树，遍历序列。3.算法设计本系统主要用到的算法有先序遍历、中序遍历、后序遍历、层次遍历、创建二叉树和查找节点。从子菜单界面只能返回到主菜单界面，而不是退出程序。4.主要模块及模块之间的关系 运行程序后直接进入“菜单主界面”模块，菜单显示分为4个模块，（14）分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。主界面中的各个模块都是独立运行，每完成一项操作后，返回主菜单模块。通过相应定义的函数（外部接口）实现，内部数据的改变由模块内部完成。三、详细设计1.结构体（或类）设计typedef char TElemType;typedef struct BiTNodeTElemType date;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;2. 主要模块实现的流程图Case=1Case=2Case=4Case=33.算法设计先序遍历：void PreOrderTraverse(BiTree T) if(T) cout<<T->date;PreOrderTraverse(T->lchild);PreOrderTraverse(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 *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个选项可以选择)1.创建二叉树 2.遍历序列 3.节点的孩子信息 4.退出系统。除退出以外,每个功能模块运行完后，返回到主菜单界面，每个界面相互独立。3. 运行效果图表 学生情况统计表序号姓名性别出生日期学号专业联系电话备注1康政男1994.12软件工程 组长2肖琳桂男1996.08软件工程 3张小东男1994.07软件工程 4张帆 男1995.08软件工程五、结论与心得1.总体评价在此次的课程设计中，由于不够细心，在程序设计中犯了一些错误，花了挺多的时间。但是经过一番思考并且在老师的帮助下，找到了导致程序错误的原因，经过几次修改和调试，程序能正常运行，并且能够完成课程设计任务中的大部分功能。同时在此次的课程设计中让我更深刻的了解了二叉树的基本操作，增加了对专业只是学习的兴趣。我想在以后的学习中，我们会继续努力，希望在计算机方面有好的成绩，也感谢老师给我们这次课程设计的机会，让我们认识到了自身的不足，让我们能够不断地完善自己!2. 所做的工作及体会肖琳桂：编写程序和课程设计报告。课程设计中我主要担任程序设计的编写和设计报告的编写工作，经过两个星期的上机实践学习，使我对数据结构有了更进一步的认识和理解，也知道了要想学好它要重在实践，要通过不断的上机操作才能更好地学习它。通过实践我发现我的很多不足之处，然感觉理论上已经掌握，但在运用到实践的过程中仍有意想不到的困惑，因为自己对知识点的掌握不够熟悉，但通过学习有很大改进。在这次课程设计中使我知道了二又树的先序、中序、后序、层次遍历。同时，还包括了求二叉树深度和结点个数，结点的孩子信息，以及对文件的操作，用文件读取的方式实现对二叉树的建立。充分掌握树的基本操作，以及对线性存储结构的理解。也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在设计过程中，和同学们相互探讨，相互学习，相互监督。我学会了运筹帷幌，学会了宽容，学会了理解，也学会了做人与处世，这次课程设计对找来说受益良多。在今后的日子里，我会认真对待每一件事情，争取做到最好，努力将知识与实践相结合，不断巩固，加深所学的知识，做到学以致用。另外感谢老师的细心教导，以及同学们的帮助。康政：编写程序和课程设计报告。我在小组中做了编写程序和撰写报告的工作。在编写程序时，遇到很多困难，例如缺少声明，调用函数错误等等。通过网上搜查，查询资料以及老师的指点帮助，完成了很多任务。作为基础不是很好的学生，我在克服自己知识不足的过程中也在努力学习新的知识，运用不同的原理编写出不同的算法。也学习到，算法不能盲目抄袭，很多东西是不同的，必须通过自己的思考和努力的钻研才能写出一套完整的代码，不可心急，越是急越不可能精细的完成任务。撰写报告的时候，很多地方因细节问题处理不好导致出了大大小小很多漏洞，不能很精细的完成指定的任务。从中我也明白了，做一件事，尤其是耗时的编写程序的问题，不能心急也不能马虎，也许一点点出错整个程序就会崩溃，还要重新一点点的检查才能找出问题，大大降低了办事效率。所以，今后要做的第一件事是慢慢巩固检出，打好根基。第二件事是沉下心来认真做事，不能毛手毛脚，从头到尾认真细致的做下去，避免出错惹出更多的麻烦。这次的程序设计使我受益匪浅，学到了很多，做了很多。希望以后可以更多的做这种任务，巩固知识，学习新的知识，有了这些经验可以做的更好。张小东：查找资料和打印。这次我在小组中做的事情是查询资料和打印排版。虽然因为我的专业底子差一点，现在暂时只能在程序设计时查找一些需要用到的专业资料，帮助组员完成设计，但我相信下一次我不会仅此于此。这次程序设计我的收获还是很大了，让我懂得了学好专业知识，并不是自己想象中的难，而是你自己是否去努力了。在查找资料的过程中，我是边查边学自己不会的知识点。查找途中也遇到了一些当时不能理解的知识点，但经过同学的细心解答，最后一些难掌握的知识点都被基本掌握。这让我懂得编程过程需要很大的耐心，而且要有良好的思维和扎实的专业基础知识，所以我需要努力的学习，发现自身不足之处并努力改正他，逐步提高自身的能力，不断取得进步。通过这次课程设计，我认识到知识运用的重要性，并且努力加深对基础知识的理解，从中了解自己需要学习的东西并学会自学。作为一名计算机专业的学生，今后我会加紧学习，学好专业知识，为将来打下坚实的基础。张帆：查找资料和打印。这次我在小组中做的事情是查询资料，打印排版。虽然这些工作并不是主要任务，但是我用心对待，认真为做程序的同学查找资料，为他们挑选所需要的代码以及算法，及时反馈给他们信息。因为基础不是很好，经常会剪裁到一些不是很合适的代码，我们通过共同分析，共同筛选，最终也获得了很多收获。通过和他们一起分析代码，我也涨了很多知识。懂的了二叉树的算法，数据类型等等。报告的排版也是一项需要耐心的工作，通过晚上的时间，我认认真真的对所写的设计报告进行了排版，把一些不符合文本框架或者有代码错误的都进行了细致的修改，保证了设计报告的质量。从这次的程序设计中，我学到了很多。认认真真做一件事情不会有错，用什么态度做什么事会得到什么样的回报。并且我认为数据结果也不是很难的科目，认真花时间去琢磨一定不会落下很多。所以以后我会细致做事，并在闲暇时间补习功课，争取尽快补习好原来的知识，再学习新的知识为自己充电。六、程序附录（源代码）#include<iostream>#include<fstream>#include<stdlib.h>using namespace std;typedef char TElemType;#define MaxSize 1000 int 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(BiTree &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;bool End=false;char sel;char 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(stdin);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"system("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);cout<<"n"system("pause");system("cls");break; case'5': p=0;while(p);break;case'3': do system("cls");q=1;cout<<"n-结点的孩子信息：-n" cout<<"（如果节点不存在,不返回任何信息，按任意键返回子菜单）n" cout<<"输入要查找的节点：" cin>>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);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<<"n"else cout<<"t"<<"节点没有左孩子n"if(T->rchild)cout<<"t节点的右孩子："<<T->rchild->date<<"n"else cout<<"t"<<"节点没有右孩子n"else p=T->lchild;if(p) locate(T->lchild,x);locate(T->rchild,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 blxljm()/遍历序列界面函数system("cls");cout<<"nt-二叉树-n" cout<<"t（如果没创建二叉树,不返回任何信息，按5返回主菜单）n"cout<<"tt1.先序遍历二叉树n"cout<<"tt2.中序遍历二叉树n"cout<<"tt3.后序遍历二叉树n"cout<<"tt4.层次遍历二叉树n"cout<<"tt5.返回主菜单n"cout<<"tt请选择（15）："cout<<"nt-n"int Count(BiTree T)/计算节点数量if(T=NULL)return 0;return 1+Count(T->lchild)+Count(T->rchild);int 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);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);void jp(BiTree &T)/键盘输入cout<<"输入按先序建立二叉树结点序列:t"cout<<"例如:ABDECFHGIJn"cout<<"输入:"cin>>input;int i=0;CreateBiTree(T);int num=Count(T);int deep=Deep(T);cout<<" 二叉树创建成功！n"cout<<" 此二叉树共有"<<num<<"个结点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<<" 且该二叉树的深度为：" <<deep<< " （按3返回主菜单界面）n"cout<<"请输入选项："void CreateBiTree(BiTree &T)/新建树if(inputi='') i+;T=NULL; elseT=new BiTNode;if(!T)return;T->date=inputi+;CreateBiTree(T->lchild);CreateBiTree(T->rchild);void PreOrderTraverse(BiTree T)/先序遍历if(T)cout<<T->date;PreOrderTraverse(T->lchild);PreOrderTraverse(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 *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; void Destory(BiTree &T)/删除树if(T)Destory(T->lchild);Destory(T->rchild);free(T);七、参考文献 郑莉，董渊，何江舟编著，C+语言程序设计，北京；清华大学出版社，2010 谭浩强.C程序设计(第三版)M.北京:清华大学出版社，2005. 严蔚敏.数据结构（C语言版），清华大学出版社。教师评语及设计成绩教师评语：课程设计成绩： 指导教师： （签名） 日期： 年 月 日