数据结构课程设计二叉树.docx
- 文档编号:3849623
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:22
- 大小:222.86KB
数据结构课程设计二叉树.docx
《数据结构课程设计二叉树.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计二叉树.docx(22页珍藏版)》请在冰点文库上搜索。
数据结构课程设计二叉树
安徽理工大学
数据结构
课程设计说明书
题目:
二叉树的遍历算法集成
院系:
计算机科学与工程学院
专业班级:
学号:
学生姓名:
指导教师:
2010年1月11日
安徽理工大学课程设计〔论文〕任务书
计算机科学与工程学院计算机软件教研室
学号
2008303003
学生姓名
刘威
专业〔班级〕
信息08-1
设计题目
二叉树的遍历算法集成
设
计
技
术
参
数
系统平台:
WindowsXP
设
计
要
求
〔1〕界面友好,易于操作。
可采用菜单或其它人机对话方式进行选择
〔2〕实现各种二叉树的遍历。
包括先序遍历、中序遍历、后序遍历的递归或非递归算法。
〔3〕要求能查找任一结点在某种遍历序列中的前驱和后继。
〔4〕演示程序以人机对话的形式进行。
每次测试完毕正确显示各种遍历序列。
工
作
量
课程设计报告要求不少于3000字。
源程序要求不少于300行
工
作
计
划
12月14日-12月16日查找相关资料
12月18日-12月21日思考相关问题
12月22日-12月28日设计算法
12月29日-1月05日编写代码
1月06日-1月09日撰写课程设计报告
参
考
资
料
[1]秦锋.数据结构(C语言版).合肥:
中国科学技术大学出版社,2007
[2]温秀梅.VisualC++面象对象程序设计教程与实验.北京:
清华大学出版社2006
[3]何钦铭.C语言程序设计.北京:
高等教育出版社,2008
指导教师签字
教研室主任签字
2009年11月16日
学生姓名:
刘威学号:
2008303003专业班级:
信息08-1
课程设计题目:
二叉树的遍历算法集成
指导教师评语:
成绩:
指导教师:
年月日
安徽理工大学课程设计〔论文〕成绩评定表
目 录
2、概要设计2
2.1功能设计2
2.2算法流程图3
3.3调试分析14
调试结果14
算法分析18
4、总结18
参考文献19
1、需求分析
数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业根底课程,掌握好数据结构的知识将直接关系到后续专业课程的学习。
数据结构只要研究四个方面的问题:
(1)数据的逻辑结构,即数据之间的逻辑关系;
(2)数据的物理结构,即数据在计算机内的存储方式;(3)对数据的加工,即基于某种存储方式的操作算法;(4)算法的分析;即评价算法的优劣。
本实验是用链式存储结构来存储二叉树并进行一系列的算法,且结点内容的数据类型为字符型。
本程序用VC++6.0编写,可以实现各种二叉树的遍历。
包括先序遍历、中序遍历、后序遍历的递归算法,先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。
根据题目知,程序主要是根据给定二叉树的先序遍历结果,构造出二叉树并输出按中,后序遍历的结果,以及求二叉树的叶子个数等。
其中二叉树的结点用字符表示。
(1)先创立二叉树:
按先序次序输入,构造二叉链表表示的二叉树。
(2)设计算法:
先序遍历,中序遍历,后序遍历.在做到层序遍历时,应注意算法如下:
根结点入队,队头元素出队,左孩子不为空入队右孩子不为空入队的顺序进行。
(3)可以参加求二叉树的深度二叉树的叶子数二叉树的结点总数等一些简单的算法。
(4)设计main()函数调用以上步骤实现相关功能。
2、概要设计
2.1功能设计
〔1〕typedefstructBTNode
定义一个用链式存储结构存储的二叉树,其中包括左孩子和右孩子以及数据元素的内容。
和单链表类似,一个二叉链表由头指针唯一确定,假设二叉树为空,那么头指针指向空。
并且结点内容的数据类型为字符型。
〔2〕CreateBiTree(BiTree&T)
此函数的功能是构建二叉树。
从键盘上按先序次序输入字符构造二叉链表表示的二叉树T,其中用星号表示空树。
〔3〕NRPreOrder(BiTreebt)
此函数的功能是用非递归的方法实现二叉树的先序遍历算法。
调用此函数可以获得二叉树的非递归的先序遍历的结果。
〔4〕NRInOrder(BiTreebt)
此函数的功能是用非递归的方法实现二叉树的中序遍历算法。
调用此函数可以获得二叉树的非递归的中序遍历的结果。
〔5〕NRPostOrder(BiTreebt)
此函数的功能是用非递归的方法实现二叉树的后序遍历算法。
调用此函数可以获得二叉树的非递归的后序遍历的结果。
其中bt是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法,结点入栈时,配一个标志tag一同入栈1:
遍历左子树的现场保护,2:
遍历右子树前的现场保护。
首先将bt和tag(为1)入栈,遍历左子树;返回后,修改栈顶tag为2,遍历右子树;最后访问根结点。
〔6〕PreOrderTraverse(BiTreeT)
函数功能是用递归的方法对二叉树进行先序遍历,调用此函数可以获得二叉树的递归的先序遍历的结果。
〔7〕InOrderTraverse(BiTreeT)
函数功能是用递归的方法对二叉树进行中序遍历,调用此函数可以获得二叉树的递归的中序遍历的结果。
〔8〕PostOrderTraverse(BiTreeT)
函数功能是用递归的方法对二叉树进行后序遍历,调用此函数可以获得二叉树的递归的后序遍历的结果。
〔9〕LevelOrderTraverse(BiTreeT)
调用此函数可以获得二叉树的层序遍历。
〔10〕BTDepth(BiTreeT)
求二叉树的深度的算法。
〔11〕Leaf(BiTreeT)
求二叉树的叶子数的算法。
〔12〕NodeCount(BiTreeT)
求二叉树的结点总数的算法。
〔13〕main()
主函数用while()与switch(select)语句对二叉树的操作的算法进行了设计。
可以实现以上函数的功能,并能退出程序。
2.2算法流程图
先设计出二叉树的一些算法的函数,如非递归遍历、递归遍历、层次遍历等一些算法。
然后在主函数中逐一调用。
其中,在求任意结点在中序遍历前驱后继算法时利用了递归的中序遍历的算法。
算法流程图如图1所示。
图1算法流程图
3、详细设计
3.1界面设计
设计的界面如图2所示。
图2界面
3.2详细代码设计
〔1〕定义二叉树
用链式存储结构存储二叉树。
其中,Lchild和Rchild是分别指向该结点左孩子和右孩子的指针,data是数据元素的内容。
定义二叉树结点值的类型为字符型且结点个数不超过10个。
typedefcharElemType;
//结点个数不超过10个
constintMaxLength=10;
typedefstructBTNode{
ElemTypedata;
structBTNode*lchild,*rchild;
}BTNode,*BiTree;〔2〕查找模块
〔2〕构造二叉链表
创立二叉链表存储的二叉树。
按二叉树带空指针的先序次序输入结点值,结点类型为字符型。
按先序次序输入,其中*表示空结点。
算法是按照先序遍历思想设计的。
构造二叉链表表示的二叉树T,星号表示空树。
voidCreateBiTree(BiTree&T){
charch;
ch=getchar();
if(ch=='*')T=NULL;
else{
if(!
(T=(BTNode*)malloc(sizeof(BTNode))))cout<<"mallocfail!
";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
〔3〕非递归的先序遍历算法
函数功能是用非递归的方法对二叉树进行先序遍历。
通过分析可知最后处理过的结点的右子树应该首先被访问,最先处理过的结点的右子树应该最后被访问,显然使用栈可以解决问题。
voidNRPreOrder(BiTreebt)
{BiTreestack[MaxLength],p;
inttop;
if(bt!
=NULL){
top=0;p=bt;
while(p!
=NULL||top>0)
{while(p!
=NULL)
{
cout<
stack[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{top--;p=stack[top];p=p->rchild;}
}
}
}
〔4〕非递归的中序遍历算法
此函数的功能是用非递归的方法实现二叉树的中序遍历算法。
调用此函数可以获得二叉树的非递归的中序遍历的结果。
用非递归调用也得使用栈。
voidNRInOrder(BiTreebt)
{BiTreestack[MaxLength],p;
inttop;
if(bt!
=NULL){
top=0;p=bt;
while(p!
=NULL||top>0)
{while(p!
=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{top--;p=stack[top];cout<
}
}
}
〔5〕非递归的后序遍历算法
此函数的功能是用非递归的方法实现二叉树的后序遍历算法。
调用此函数可以获得二叉树的非递归的后序遍历的结果。
其中bt是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法,结点入栈时,配一个标志tag一同入栈1:
遍历左子树的现场保护,2:
遍历右子树前的现场保护。
首先将bt和tag(为1)入栈,遍历左子树;返回后,修改栈顶tag为2,遍历右子树;最后访问根结点。
typedefstruct
{
BiTreeptr;
inttag;
}stacknode;
voidNRPostOrder(BiTreebt)
{
stacknodes[MaxLength],x;
BiTreep=bt;
inttop;
if(bt!
=NULL){
top=0;p=bt;
do
{
while(p!
=NULL)
{
s[top].ptr=p;
s[top].tag=1;
top++;
p=p->lchild;
}
while(top>0&&s[top-1].tag==2)
{
x=s[--top];
p=x.ptr;
cout<
}
if(top>0)
{
s[top-1].tag=2;
p=s[top-1].ptr->rchild;
}
}while(top>0);}
}
〔6〕递归的先序遍历
函数功能是用递归的方法对二叉树进行先序遍历,调用此函数可以获得二叉树的递归的先序遍历的结果。
算法思想:
假设二叉树为空,那么结束遍历操作;否那么访问根结点;先序遍历根的左子树;先序遍历根的右子树。
voidPreOrderTraverse(BiTreeT){
if(T){
cout<
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
〔7〕递归的中序遍历
函数功能是用递归的方法对二叉树进行中序遍历。
算法思想:
假设二叉树为空,那么结束遍历操作;否那么中序遍历根的左子树;访问根结点;中序遍历根的右子树。
voidInOrderTraverse(BiTreeT){
if(T){
InOrderTraverse(T->lchild);
cout<
a[i]=T->data;
i++;
InOrderTraverse(T->rchild);
}
}
〔8〕递归的后序遍历
函数功能是用递归的方法对二叉树进行中序遍历。
算法思想:
假设二叉树为空,那么结束遍历操作;否那么后序遍历根的左子树;后序遍历根的右子树;访问根结点。
voidPostOrderTraverse(BiTreeT){
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<
}
}
〔9〕层序遍历
调用此函数可以获得二叉树的层序遍历。
该算法的思想如下:
访问根结点,并将该结点记录下来;假设记录的所有节点都已经处理完毕,那么结束遍历操作;否那么重复以下操作。
取出记录中第一个还没有访问孩子的结点,假设它有左孩子,那么访问做孩子,并记录下来;假设它有右孩子,那么访问右孩子,并记录下来。
voidLevelOrderTraverse(BiTreeT){
BiTreeQ[MaxLength];
intfront=0,rear=0;
BiTreep;
//根结点入队
if(T){
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!
=rear){
//队头元素出队
p=Q[front];
front=(front+1)%MaxLength;
cout<
//左孩子不为空,入队
if(p->lchild){
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
//右孩子不为空,入队
if(p->rchild){
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
〔10〕结点在中序遍历的前驱后继
此程序所用的方法并非利用线索二叉树。
对整个二叉树进行中序遍历,看看哪个结点之后是所求结点的前驱,那么该结点就是所求结点的中序前驱。
同样的也可以得到中序后继。
inti;chara[100];
voidInOrderTraverse(BiTreeT){
if(T){
InOrderTraverse(T->lchild);
cout<
a[i]=T->data;
i++;
InOrderTraverse(T->rchild);
}
}
上面是利用的二叉树的中序遍历方法来获得结点的信息,再调用下面语句便可实现以上功能。
在主函数中应用switch()语句。
cout<<"\n请输入您要在中序中查找前驱后继的结点(字符型):
\n";
cin>>c;
for(j=0;j
{
if(a[j]==c)
cout<<"结点的前驱为:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 二叉