数据结构课程设计报告二叉树.docx
- 文档编号:10748143
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:22
- 大小:88.40KB
数据结构课程设计报告二叉树.docx
《数据结构课程设计报告二叉树.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告二叉树.docx(22页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告二叉树
湖南涉外经济学院
课程设计报告
课程名称:
数据结构
报告题目:
二叉树的基本操作
学生姓名:
肖琳桂、康政、张小东、张帆
所在学院:
信息科学与工程学院
专业班级:
软工本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)用菜单的形式实现操作界面,提供(1—4)个功能选项,功能分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。
(2)创建二叉树。
要求用文件读取和键盘输入两种不同的方式实现二叉树的创建。
二级菜单说明,输出创建二叉树的深度及结点数,若失败则有相应提示。
(3)遍历序列。
显示先序,中序,后序和层次遍历结果。
先序遍历、中序遍历、后序遍历用递归的方法实现遍历。
层次遍历,用循环队列的方法实现。
(4)每次实现一项操作之后,要有相应的提示返回菜单。
二、概要设计
1.总体设计图
2.数据结构设计
数据元素为字符,逻辑结构为树形结构,存储结构为二叉链式存储,系统操作的数据元素主要是创建一个二叉树,遍历序列。
3.算法设计
本系统主要用到的算法有先序遍历、中序遍历、后序遍历、层次遍历、创建二叉树和查找节点。
从子菜单界面只能返回到主菜单界面,而不是退出程序。
4.主要模块及模块之间的关系
运行程序后直接进入“菜单主界面”模块,菜单显示分为4个模块,(1~4)分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。
主界面中的各个模块都是独立运行,每完成一项操作后,返回主菜单模块。
通过相应定义的函数(外部接口)实现,内部数据的改变由模块内部完成。
三、详细设计
1.结构体(或类)设计
typedefcharTElemType;
typedefstructBiTNode
{
TElemTypedate;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
2.主要模块实现的流程图
Case=3
3.算法设计
先序遍历:
voidPreOrderTraverse(BiTreeT)
{if(T)
{cout<
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);}}
中序遍历:
voidInOrderTraver(BiTreeT)
{if(T)
{InOrderTraver(T->lchild);
cout<
InOrderTraver(T->rchild);}}
后序遍历:
voidPostOrderTraver(BiTreeT)
{if(T)
{PostOrderTraver(T->lchild);
PostOrderTraver(T->rchild);
cout<
层次遍历:
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
康政
男
1994.12
144300202
软件工程
组长
2
肖琳桂
男
1996.08
144300211
软件工程
3
张小东
男
1994.07
144300214
软件工程
4
张帆
男
1995.08
144300208
软件工程
五、结论与心得
1.总体评价
在此次的课程设计中,由于不够细心,在程序设计中犯了一些错误,花了挺多的时间。
但是经过一番思考并且在老师的帮助下,找到了导致程序错误的原因,经过几次修改和调试,程序能正常运行,并且能够完成课程设计任务中的大部分功能。
同时在此次的课程设计中让我更深刻的了解了二叉树的基本操作,增加了对专业只是学习的兴趣。
我想在以后的学习中,我们会继续努力,希望在计算机方面有好的成绩,也感谢老师给我们这次课程设计的机会,让我们认识到了自身的不足,让我们能够不断地完善自己!
2.所做的工作及体会
肖琳桂:
编写程序和课程设计报告。
课程设计中我主要担任程序设计的编写和设计报告的编写工作,经过两个星期的上机实践学习,使我对数据结构有了更进一步的认识和理解,也知道了要想学好它要重在实践,要通过不断的上机操作才能更好地学习它。
通过实践我发现我的很多不足之处,然感觉理论上已经掌握,但在运用到实践的过程中仍有意想不到的困惑,因为自己对知识点的掌握不够熟悉,但通过学习有很大改进。
在这次课程设计中使我知道了二又树的先序、中序、后序、层次遍历。
同时,还包括了求二叉树深度和结点个数,结点的孩子信息,以及对文件的操作,用文件读取的方式实现对二叉树的建立。
充分掌握树的基本操作,以及对线性存储结构的理解。
也培养了我如何去把握一件事情,如何去做一件事情,又如何完成一件事情的方法和技巧。
在设计过程中,和同学们相互探讨,相互学习,相互监督。
我学会了运筹帷幌,学会了宽容,学会了理解,也学会了做人与处世,这次课程设计对找来说受益良多。
在今后的日子里,我会认真对待每一件事情,争取做到最好,努力将知识与实践相结合,不断巩固,加深所学的知识,做到学以致用。
另外感谢老师的细心教导,以及同学们的帮助。
康政:
编写程序和课程设计报告。
我在小组中做了编写程序和撰写报告的工作。
在编写程序时,遇到很多困难,例如缺少声明,调用函数错误等等。
通过网上搜查,查询资料以及老师的指点帮助,完成了很多任务。
作为基础不是很好的学生,我在克服自己知识不足的过程中也在努力学习新的知识,运用不同的原理编写出不同的算法。
也学习到,算法不能盲目抄袭,很多东西是不同的,必须通过自己的思考和努力的钻研才能写出一套完整的代码,不可心急,越是急越不可能精细的完成任务。
撰写报告的时候,很多地方因细节问题处理不好导致出了大大小小很多漏洞,不能很精细的完成指定的任务。
从中我也明白了,做一件事,尤其是耗时的编写程序的问题,不能心急也不能马虎,也许一点点出错整个程序就会崩溃,还要重新一点点的检查才能找出问题,大大降低了办事效率。
所以,今后要做的第一件事是慢慢巩固检出,打好根基。
第二件事是沉下心来认真做事,不能毛手毛脚,从头到尾认真细致的做下去,避免出错惹出更多的麻烦。
这次的程序设计使我受益匪浅,学到了很多,做了很多。
希望以后可以更多的做这种任务,巩固知识,学习新的知识,有了这些经验可以做的更好。
张小东:
查找资料和打印。
这次我在小组中做的事情是查询资料和打印排版。
虽然因为我的专业底子差一点,现在暂时只能在程序设计时查找一些需要用到的专业资料,帮助组员完成设计,但我相信下一次我不会仅此于此。
这次程序设计我的收获还是很大了,让我懂得了学好专业知识,并不是自己想象中的难,而是你自己是否去努力了。
在查找资料的过程中,我是边查边学自己不会的知识点。
查找途中也遇到了一些当时不能理解的知识点,但经过同学的细心解答,最后一些难掌握的知识点都被基本掌握。
这让我懂得编程过程需要很大的耐心,而且要有良好的思维和扎实的专业基础知识,所以我需要努力的学习,发现自身不足之处并努力改正他,逐步提高自身的能力,不断取得进步。
通过这次课程设计,我认识到知识运用的重要性,并且努力加深对基础知识的理解,从中了解自己需要学习的东西并学会自学。
作为一名计算机专业的学生,今后我会加紧学习,学好专业知识,为将来打下坚实的基础。
张帆:
查找资料和打印。
这次我在小组中做的事情是查询资料,打印排版。
虽然这些工作并不是主要任务,但是我用心对待,认真为做程序的同学查找资料,为他们挑选所需要的代码以及算法,及时反馈给他们信息。
因为基础不是很好,经常会剪裁到一些不是很合适的代码,我们通过共同分析,共同筛选,最终也获得了很多收获。
通过和他们一起分析代码,我也涨了很多知识。
懂的了二叉树的算法,数据类型等等。
报告的排版也是一项需要耐心的工作,通过晚上的时间,我认认真真的对所写的设计报告进行了排版,把一些不符合文本框架或者有代码错误的都进行了细致的修改,保证了设计报告的质量。
从这次的程序设计中,我学到了很多。
认认真真做一件事情不会有错,用什么态度做什么事会得到什么样的回报。
并且我认为数据结果也不是很难的科目,认真花时间去琢磨一定不会落下很多。
所以以后我会细致做事,并在闲暇时间补习功课,争取尽快补习好原来的知识,再学习新的知识为自己充电。
六、程序附录(源代码)
#include
#include
#include
usingnamespacestd;
typedefcharTElemType;
#defineMaxSize1000
inti;
typedefstructBiTNode
{
TElemTypedate;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
voidDestory(BiTree&T);//函数声明
charinput[255];
voidInterface();
voidsjecs(BiTree&T);
voidjp(BiTree&T);//键盘
voidwj(BiTree&T);//文件
voidCreateBiTree(BiTree&T);
intCount(BiTreeT);
intDeep(BiTreeT);
voidPreOrderTraverse(BiTreeT);//先序
voidInOrderTraver(BiTreeT);//中序
voidPostOrderTraver(BiTreeT);//后序
voidccbl(BiTNode*b);//层次遍历
voidblxljm();
voidlocate(BiTreeT,charx);
voidmain()//主函数
{
Interface();
BiTreeT=NULL;
boolEnd=false;
charsel;
charx;
intp=1;
intq=1;
do{
Interface();
fflush(stdin);
charselect=cin.get();
system("cls");
switch(select)
{
case'1':
cout<<"创建二叉树:
\n";sjecs(T);break;
case'2':
{
cout<<"\n\t遍历序列\n";
do{blxljm();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<<"\n\t0.输入返回主菜单\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)//在二叉树T中查找值为x的节点
{
BiTreep;
p=T;
if(T==NULL)return;
elseif(T->date==x)
{
cout<
if(T->lchild){cout<<"\t"<<"节点的左孩子:
"<
else{cout<<"\t"<<"节点没有左孩子\n";}
if(T->rchild){cout<<"\t节点的右孩子:
"<
else{cout<<"\t"<<"节点没有右孩子\n";}
}
else{
p=T->lchild;
if(p){locate(T->lchild,x);
locate(T->rchild,x);}
}
}
voidInterface()//菜单界面函数
{
system("cls");
cout<<"\n\t-----------遍历序列------------\n";
cout<<"\t\t1.创建二叉树\n";
cout<<"\t\t2.遍历序列\n";
cout<<"\t\t3.结点的孩子信息\n";
cout<<"\t\t4.退出系统\n";
cout<<"\t\t请选择(1~4):
";
cout<<"\n\t----------------------------\n";
}
voidblxljm()//遍历序列界面函数
{
system("cls");
cout<<"\n\t----------------------二叉树-----------------------\n";
cout<<"\t(如果没创建二叉树,不返回任何信息,按5返回主菜单)\n";
cout<<"\t\t1.先序遍历二叉树\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)//计算节点数量
{
if(T==NULL)return0;
return1+Count(T->lchild)+Count(T->rchild);
}
intDeep(BiTreeT)//计算二叉树的度
{
if(T==NULL)return0;
intu=Deep(T->lchild);
intv=Deep(T->rchild);
if(u>v)return(u+1);
return(v+1);
}
voidsjecs(BiTree&T)//选择输入模式,新建二叉树
{
boolEnd=false;
if(T){Destory(T);T=NULL;}
cout<<"请选择输入二叉树序列模式:
(1:
键盘输入2.文件输入3.返回主菜单)"< do{ charSelection=cin.get(); switch(Selection) { case'1': jp(T);break; case'2': wj(T);break; case'3': End=true; } }while(! End); } voidjp(BiTree&T)//键盘输入 { cout<<"输入按先序建立二叉树结点序列: \t"; cout<<"例如: ABD@@E@@CFH@@@GI@J@@@\n"; cout<<"输入: "; cin>>input; inti=0; CreateBiTree(T); intnum=Count(T); intdeep=Deep(T); cout<<"二叉树创建成功! \n"; cout<<"此二叉树共有"< cout<<"且该二叉树的深度为: "< cout<<"请输入选项: "; } voidwj(BiTree&T)//文件输入 { ifstreamfi("a.txt"); if(! fi){cout<<"数据文件不存在! \n";exit(0);} fi>>input; inti=0; CreateBiTree(T); intnum=Count(T); intdeep=Deep(T); cout<<"二叉树创建成功! \n"; cout<<"此二叉树共有"< cout<<"且该二叉树的深度为: "< cout<<"请输入选项: "; } voidCreateBiTree(BiTree&T)//新建树 { if(input[i]=='@') {i++;T=NULL;} else { T=newBiTNode; if(! T)return; T->date=input[i++]; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } voidPreOrderTraverse(BiTreeT)//先序遍历 { if(T) { cout< PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } voidInOrderTraver(BiTreeT)//中序遍历 { if(T)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 二叉