数据结构课程设计报告二叉树.docx
《数据结构课程设计报告二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告二叉树.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告二叉树
湖南涉外经济学院
课程设计报告
课程名称：
数据结构
报告题目：
二叉树的基本操作
学生姓名：
肖琳桂、康政、张小东、张帆
所在学院：
信息科学与工程学院
专业班级：
软工本1402
学生学号：
1、02、14、08
指导教师：
李春庭
2015年12月31日
课程设计任务书
报告题目
二叉树的基本操作
完成时间
2周
学生姓名
肖琳桂康政
专业班级
软工本1402
指导教师
李春庭
职称
讲师
总体设计要求和主要功能
设计一个程序，实现二叉树的创建以及二叉树的遍历（包括先序遍历、中序遍历、后序遍历和层次遍历），计算并输出二叉树的深度和结点个数，功能要求：
1．二叉树以二叉链表存储，结点数据类型采用字符表示，按二叉树的先序遍历序列创建。
2．用文本编辑器编写一个的文件,包含3个以上创建按二叉树的先序遍历序列（即序列中包含空树节点），每个序列长度不少于10个，在运行程序时自动载入，也可以由键盘输入创建二叉树。
|
3．菜单功能：
创建二叉树（二级菜单说明选择文件中的第几个，输出创建二叉树的深度及结点数，若失败则有相应提示），遍历序列（显示先序，中序，后序和层次遍历结果），结点的孩子信息，退出系统。
工作内容及时间进度安排
第17周：
周1---周2：
立题、论证方案设计
周3---周5：
程序设计及程序编码
第18周：
周1---周3：
程序调试
周4---周5：
验收答辩
摘要
本课程设计主要说明如何在C++编程环境下实现二叉树的遍历，遍历方式包括:
二叉树的先序遍历、中序遍历、后序遍历，层次遍历等四种遍历方式。
同时，此次课程设计还包括了求二叉树深度和结点个数，结点的孩子信息，以及对文件的操作，用文件读取的方式实现对二叉树的建立。
以通过此次课程设计，使学生充分掌握树的基本操作，以及对线性存储结构的理解。
同时，在对树的遍历的操作过程中，同样是运用递归的方式实现遍历，在对树实现层次操作的时候，要求用循环队列的操作方式来实现层次遍历。
此次课程设计对数据结构内容综合性的运用的要求较高。
关键词：
二叉树，先序遍历，中序遍历，后序遍历，层次遍历，节点，线性存储,节点的孩子信息
课程设计任务书1
一、需求分析4
1．问题描述4
2．功能要求4
二、概要设计5
1.总体设计图5
2.数据结构设计5
3.算法设计5
4.主要模块及模块之间的关系5
三、详细设计6
1.结构体（或类）设计6
2.主要模块实现的流程图6
3.算法设计7
四、测试运行8
1．登录和主界面运行效果图8
2．运行说明8
3.运行效果图8
五、结论与心得10
1.总体评价10
2.所做的工作及体会10
六、程序附录（源代码）12
七、参考文献18
一、需求分析
1．问题描述
设计一个二叉树。
二叉树形象地说即树中每个节点最多只有两个分支，它是一种重要的数据类型。
可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表等。
二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历，层次遍历。
以及能够从输入的数据中得知二叉树的叶子结点的个数，二叉树的深度。
在此，二叉树的每一个结点中必须包括：
值域，左指针域，右指针域。
我们抽象出下列问题：
实现文件操作，运用文件输入流，将已经写好二叉树序列的txt文本文件，加载到程序中，实现文件创建二叉树。
然后采用链表存储的方式遍历二叉树（先序遍历、中序遍历、后序遍历、层次遍历）。
层次遍历运用循环队列的方法实现，需要重新定义队头和队尾，以及队列的最大长度，并且在屏幕上实现输出显示。
2．功能要求
（1）用菜单的形式实现操作界面，提供（1—4）个功能选项，功能分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。
（2）创建二叉树。
要求用文件读取和键盘输入两种不同的方式实现二叉树的创建。
二级菜单说明，输出创建二叉树的深度及结点数，若失败则有相应提示。
（3）遍历序列。
显示先序，中序，后序和层次遍历结果。
先序遍历、中序遍历、后序遍历用递归的方法实现遍历。
层次遍历，用循环队列的方法实现。
（4）每次实现一项操作之后，要有相应的提示返回菜单。
二、概要设计
1.总体设计图
键盘输入
文件输入
中序遍历
后序遍历
层次遍历
先序遍历
2.数据结构设计
数据元素为字符，逻辑结构为树形结构，存储结构为二叉链式存储，系统操作的数据元素主要是创建一个二叉树，遍历序列。
3.算法设计
本系统主要用到的算法有先序遍历、中序遍历、后序遍历、层次遍历、创建二叉树和查找节点。
从子菜单界面只能返回到主菜单界面，而不是退出程序。
4.主要模块及模块之间的关系
运行程序后直接进入“菜单主界面”模块，菜单显示分为4个模块，（1~4）分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。
主界面中的各个模块都是独立运行，每完成一项操作后，返回主菜单模块。
通过相应定义的函数（外部接口）实现，内部数据的改变由模块内部完成。
三、详细设计
1.结构体（或类）设计
typedefcharTElemType;
typedefstructBiTNode
{
TElemTypedate;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
2.主要模块实现的流程图
Case=1
Case=2
Case=3
3.算法设计
先序遍历：
voidPreOrderTraverse（BiTreeT）
{if（T）
{cout<date;
PreOrderTraverse（T->lchild）;
PreOrderTraverse（T->rchild）;}}
中序遍历：
voidInOrderTraver（BiTreeT）
{if（T）
{InOrderTraver（T->lchild）;
cout<date;
InOrderTraver（T->rchild）;}}
后序遍历：
voidPostOrderTraver（BiTreeT）
{if（T）
{PostOrderTraver（T->lchild）;
PostOrderTraver（T->rchild）;
cout<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;}}}
四、测试运行
1．登录和主界面运行效果图
2．运行说明
主程序运行后，直接到菜单选择界面。
其中有（1—4个选项可以选择）
1.创建二叉树2.遍历序列3.节点的孩子信息4.退出系统。
除退出以外,每个功能模块运行完后，返回到主菜单界面，每个界面相互独立。
3.运行效果图
表学生情况统计表
序号
姓名
性别
出生日期
学号
专业
联系电话
备注
1
康政
男
2
软件工程
组长
2
肖琳桂
男
1
软件工程
3
张小东
男
4
软件工程
4
张帆
男
8
软件工程
五、结论与心得
1.总体评价
在此次的课程设计中，由于不够细心，在程序设计中犯了一些错误，花了挺多的时间。
但是经过一番思考并且在老师的帮助下，找到了导致程序错误的原因，经过几次修改和调试，程序能正常运行，并且能够完成课程设计任务中的大部分功能。
同时在此次的课程设计中让我更深刻的了解了二叉树的基本操作，增加了对专业只是学习的兴趣。
我想在以后的学习中，我们会继续努力，希望在计算机方面有好的成绩，也感谢老师给我们这次课程设计的机会，让我们认识到了自身的不足，让我们能够不断地完善自己!
2.所做的工作及体会
肖琳桂：
编写程序和课程设计报告。
课程设计中我主要担任程序设计的编写和设计报告的编写工作，经过两个星期的上机实践学习，使我对数据结构有了更进一步的认识和理解，也知道了要想学好它要重在实践，要通过不断的上机操作才能更好地学习它。
通过实践我发现我的很多不足之处，然感觉理论上已经掌握，但在运用到实践的过程中仍有意想不到的困惑，因为自己对知识点的掌握不够熟悉，但通过学习有很大改进。
在这次课程设计中使我知道了二又树的先序、中序、后序、层次遍历。
同时，还包括了求二叉树深度和结点个数，结点的孩子信息，以及对文件的操作，用文件读取的方式实现对二叉树的建立。
充分掌握树的基本操作，以及对线性存储结构的理解。
也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。
在设计过程中，和同学们相互探讨，相互学习，相互监督。
我学会了运筹帷幌，学会了宽容，学会了理解，也学会了做人与处世，这次课程设计对找来说受益良多。
在今后的日子里，我会认真对待每一件事情，争取做到最好，努力将知识与实践相结合，不断巩固，加深所学的知识，做到学以致用。
另外感谢老师的细心教导，以及同学们的帮助。
康政：
编写程序和课程设计报告。
我在小组中做了编写程序和撰写报告的工作。
在编写程序时，遇到很多困难，例如缺少声明，调用函数错误等等。
通过网上搜查，查询资料以及老师的指点帮助，完成了很多任务。
作为基础不是很好的学生，我在克服自己知识不足的过程中也在努力学习新的知识，运用不同的原理编写出不同的算法。
也学习到，算法不能盲目抄袭，很多东西是不同的，必须通过自己的思考和努力的钻研才能写出一套完整的代码，不可心急，越是急越不可能精细的完成任务。
撰写报告的时候，很多地方因细节问题处理不好导致出了大大小小很多漏洞，不能很精细的完成指定的任务。
从中我也明白了，做一件事，尤其是耗时的编写程序的问题，不能心急也不能马虎，也许一点点出错整个程序就会崩溃，还要重新一点点的检查才能找出问题，大大降低了办事效率。
所以，今后要做的第一件事是慢慢巩固检出，打好根基。
第二件事是沉下心来认真做事，不能毛手毛脚，从头到尾认真细致的做下去，避免出错惹出更多的麻烦。
这次的程序设计使我受益匪浅，学到了很多，做了很多。
希望以后可以更多的做这种任务，巩固知识，学习新的知识，有了这些经验可以做的更好。
张小东：
查找资料和打印。
这次我在小组中做的事情是查询资料和打印排版。
虽然因为我的专业底子差一点，现在暂时只能在程序设计时查找一些需要用到的专业资料，帮助组员完成设计，但我相信下一次我不会仅此于此。
这次程序设计我的收获还是很大了，让我懂得了学好专业知识，并不是自己想象中的难，而是你自己是否去努力了。
在查找资料的过程中，我是边查边学自己不会的知识点。
查找途中也遇到了一些当时不能理解的知识点，但经过同学的细心解答，最后一些难掌握的知识点都被基本掌握。
这让我懂得编程过程需要很大的耐心，而且要有良好的思维和扎实的专业基础知识，所以我需要努力的学习，发现自身不足之处并努力改正他，逐步提高自身的能力，不断取得进步。
通过这次课程设计，我认识到知识运用的重要性，并且努力加深对基础知识的理解，从中了解自己需要学习的东西并学会自学。
作为一名计算机专业的学生，今后我会加紧学习，学好专业知识，为将来打下坚实的基础。
张帆：
查找资料和打印。
这次我在小组中做的事情是查询资料，打印排版。
虽然这些工作并不是主要任务，但是我用心对待，认真为做程序的同学查找资料，为他们挑选所需要的代码以及算法，及时反馈给他们信息。
因为基础不是很好，经常会剪裁到一些不是很合适的代码，我们通过共同分析，共同筛选，最终也获得了很多收获。
通过和他们一起分析代码，我也涨了很多知识。
懂的了二叉树的算法，数据类型等等。
报告的排版也是一项需要耐心的工作，通过晚上的时间，我认认真真的对所写的设计报告进行了排版，把一些不符合文本框架或者有代码错误的都进行了细致的修改，保证了设计报告的质量。
从这次的程序设计中，我学到了很多。
认认真真做一件事情不会有错，用什么态度做什么事会得到什么样的回报。
并且我认为数据结果也不是很难的科目，认真花时间去琢磨一定不会落下很多。
所以以后我会细致做事，并在闲暇时间补习功课，争取尽快补习好原来的知识，再学习新的知识为自己充电。
六、程序附录（源代码）
#include
#include
#include<>
usingnamespacestd;
typedefcharTElemType;
#defineMaxSize1000
inti;
typedefstructBiTNode
{
TElemTypedate;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
voidDestory（BiTree&T）;入返回主菜单\n";cout<<"\t1.继续查找节点\n";
do{cout<<"\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）;
}
voidlocate（BiTreeT,charx）建二叉树\n";
cout<<"\t\t2.遍历序列\n";
cout<<"\t\t3.结点的孩子信息\n";
cout<<"\t\t4.退出系统\n";
cout<<"\t\t请选择（1~4）：
";
cout<<"\n\t----------------------------\n";
}
voidblxljm（）序遍历二叉树\n";
cout<<"\t\t2.中序遍历二叉树\n";
cout<<"\t\t3.后序遍历二叉树\n";
cout<<"\t\t4.层次遍历二叉树\n";
cout<<"\t\t5.返回主菜单\n";
cout<<"\t\t请选择（1~5）：
";
cout<<"\n\t--------------------------------------------------\n";
}
intCount（BiTreeT）件输入3.返回主菜单）"<do{
charSelection=（）;
switch（Selection）
{
case'1':
jp（T）;break;
case'2':
wj（T）;break;
case'3':
End=true;
}
}while（!
End）;
}
voidjp（BiTree&T）程序设计（第三版）[M].北京:
清华大学出版社，2005.
严蔚敏.数据结构（C语言版），清华大学出版社。
教师评语及设计成绩
教师评语：
课程设计成绩：
指导教师：
（签名）
日期：
年月日
升级会员 