课程设计二叉树讲解.docx
《课程设计二叉树讲解.docx》由会员分享,可在线阅读,更多相关《课程设计二叉树讲解.docx(30页珍藏版)》请在冰点文库上搜索。
课程设计二叉树讲解
安徽理工大学
数据结构
课程设计说明书
题目:
二叉树的遍历集成
院系:
计算机科学与工程学院
专业班级:
学号:
学生姓名:
指导教师:
2015年01月9日
安徽理工大学课程设计(论文)任务书
计算机科学与工程学院信息安全教研室
学号
学生姓名
专业(班级)
设计题目
二叉树遍历的集成
设
计
技
术
参
数
系统平台:
windows7
开发工具:
VC6.0++
设
计
要
求
(1)实现二叉树的各种遍历。
包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。
(2)要求能查找任一结点在某种遍历序列中的前驱和后继。
(3)界面友好,易于操作。
可采用菜单或其它人机对话方式进行选择。
工
作
量
课程设计报告要求不少于3000字。
源程序要求不少于300行
工
作
计
划
2015年1月5日分配程序任务,小组内每人做不同模块
2015年1月6日完成先序中序后序三个遍历递归算法
2015年1月7日完成先序中序后序三个遍历非递归算法
2015年1月7日完成线索化二叉树并查找节点的前驱后继
2015年1月8日完成主函数,采用友好的选择菜单页面
2015年1月9日完成设计报告,并打印
参
考
资
料
[1]严蔚敏,吴伟民.数据结构(C语言版).北京:
清华大学出版社,1997.4
指导教师签字
教研室主任签字
2014年12月18日
目 录
1.需求分析
“数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心,而且也成为其他理工类学科必修课程,所谓”数据结构”是相互之间存在一种或多种特定关系的数据元素的集合.数据元素之间的相互关系成为结构,结构一般有线性结构,树形结构,图状结构,本程序所做的就是树形结构的二叉树的遍历算法和线索化查找.
本程序使用VC6.0++编写,具体实现功能有二叉树的遍历,包括先序遍历,中序遍历,后序遍历的递归算法以及非递归算法.另外本程序还有可线索化二叉树的功能,由此可以得到二叉树某个节点的前驱和后继.
题目要求为:
1.实现二叉树的各种遍历。
包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。
2.要求能查找任一结点在某种遍历序列中的前驱和后继。
3.界面友好,易于操作。
可采用菜单或其它人机对话方式进行选择。
由小组一起制作,本人做小组汇总工作,并在基础上加了查找某个节点是否存在二叉树,以及求二叉树总节点数等一些简单功能
2、总体设计
2.1程序目录
(1)typedefstructnode
二叉树的定义,包含数据域data,左孩子lchild,右孩子rchild,若二叉树为空,则头结点指向空指针,并且data数据域为字符型数据.
(2)BiTreeCreatBiTree1(BiTree&T)
创建一颗二叉树,需要按照先序遍历输入相应字符才能构造出二叉树,其中用星号”*”来代表空字符.
(3)voidPreorder1(BiTreeT)
先序遍历递归算法,调用此函数可以获得输入二叉树的先序序列
(4)voidPreorder2(BiTreeT)
先序遍历非递归算法,和上面一样,调用此函数可以获得二叉树先序序列
(5)voidInorder1(BiTreeT)
中序遍历递归算法,调用此函数可以获得输入二叉树的中序序列
(6)voidInorder2(BiTreeT)
中序遍历非递归算法,和上面一样,调用此函数可以获得二叉树中序序列
(7)voidPostorder1(BiTreeT)
后序遍历递归算法,调用此函数可以获得输入二叉树的后序序列
(8)voidPostorder2(BiTree&T)和typedefstructstacknode
后序遍历非递归算法,和其中用到的哨兵结构体.调用此函数可以获得二叉树后序序列
(9)voidLevelorder(BiTreeT,intNodeNum)
层序遍历二叉树,需要手动输入节点数,然后即可进行二叉树的层序遍历,输出遍历结果
(10)voidInThreading(BiTreep)
线索化二叉树中需要用到的线索化前驱和后继
(11)voidInOrderThreading(BiTree&Thrt,BiTreeT)
以中序遍历来线索化二叉树,让空节点分别指向当前节点的前驱后继
(12)BiTreeInprenode(BiTreep)和BiTreeInpostnode(BiTreep)
线索化后用此函数查找二叉树的前驱和后继
(13)BiTreesearch(BiTreeBT,charx)
查找某个二叉树节点,其中x为要查找节点的data域的值
(14)main()
主函数利用while()和switch()语句构造可视化友好界面
2.2算法流程
小组分工设计独立的函数,比如三种遍历,层序遍历,二叉树线索化等,然后再综合起来,用主函数调用即可
3、详细设计
3.1界面设计
(1)打开程序后首先是按照先序序列输入二叉树,其中用“*”号表示空节点。
图1二叉树输入界面
(2)输入完二叉树后进入功能选择页面,选择对应的编号,实行相应的操作
图2二叉树功能选择页面
3.2详细代码设计
(1)创建一个二叉树,用户按照二叉树先序遍历顺序输入相应data域数据,使用getchar()读入并赋给c,利用T节点,以及左右递归,即可建立出一颗二叉树。
BiTreeCreatBiTree1(BiTree&T)
{
charch;
if((ch=getchar())=='*')
T=NULL;//读入星号,返回空指针
else{
T=(BiTNode*)malloc(sizeof(BiTNode));//生成结点
if(!
T)
return0;
T->data=ch;
T->LTag=0;
T->RTag=0;
CreatBiTree1(T->lchild);//构造左子树
CreatBiTree1(T->rchild);//构造右子树
return(T);
}
}
(2)先序递归算法,读取头节点后,输出,接下来使用递归算法,不断地向下延伸读取,输出即可。
voidPreorder1(BiTreeT)
{
if(T){
printf("%c",T->data);//访问结点
Preorder1(T->lchild);//先序遍历左子树
Preorder1(T->rchild);//先序遍历右子树
}
}
(3)先序遍历非递归算法,设置一个stack的栈用来存储读取的二叉树序列,利用栈先进后出的特性,输出栈即为先序遍历.
voidPreorder2(BiTreeT)
{BiTreestack[Max],p;
inttop;
if(T!
=NULL){
top=0;p=T;
while(p!
=NULL||top>0)
{
while(p!
=NULL)
{
printf("%c",p->data);
stack[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{top--;
p=stack[top];
p=p->rchild;
}}}}
(4)中序遍历递归算法和先序遍历思想差不多,只是在遍历完左边后再输出头节点.
voidInorder1(BiTreeT)
{
if(T){
Inorder1(T->lchild);//中序遍历左子树
printf("%c",T->data);//访问结点
Inorder1(T->rchild);//中序遍历右子树
}}
(5)中序遍历非递归算法,同理也是利用栈的特性来存储读取出来的data域的值,修改下出栈方式即可.
voidInorder2(BiTreeT)
{BiTreestack[Max],p;
inttop;
if(T!
=NULL){
top=0;p=T;
while(p!
=NULL||top>0)
{
while(p!
=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{top--;
p=stack[top];
printf("%c",p->data);
p=p->rchild;
}}}}
(6)后序遍历递归算法和先序遍历思想差不多,只是在遍历完最后后再输出头节点.
voidPostorder1(BiTreeT)
{
if(T){
Postorder1(T->lchild);//后序遍历左子树
Postorder1(T->rchild);//后序遍历右子树
printf("%c",T->data);//访问结点
}}
(7)后序遍历非递归算法,首先设置一个typedefstructstacknode的结构体为监查哨兵,输出过的节点都做上标记,防止二次输出.
typedefstruct
{
BiTreeptr;
inttag;
}stacknode;//设置哨兵
voidPostorder2(BiTree&T)
{stacknodes[Max],x;
BiTreep=T;
inttop;
if(T!
=NULL){
top=0;p=T;
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;
printf("%c",p->data);
}
if(top>0)
{
s[top-1].tag=2;
p=s[top-1].ptr->rchild;
}
}while(top>0);}}
(8)层序遍历二叉树,利用指针数组*cq[Max]进行出队入队操作,再遍历左子树,最后再遍历右子树.
voidLevelorder(BiTreeT,intNodeNum)
{
intfront=0,rear=1;
BiTNode*cq[Max],*p;//定义结点的指针数组cq
cq[1]=T;//根入队
while(front!
=rear)
{
front=(front+1)%NodeNum;
p=cq[front];//出队
printf("%c",p->data);//出队,输出结点的值
if(p->lchild!
=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild;//左子树入队
}
if(p->rchild!
=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild;//右子树入队
}}}
(9)线索化二叉树,利用voidInThreading(BiTreep)和voidInOrderThreading(BiTree&Thrt,BiTreeT)可完成二叉树中序线索化.主要思想是使二叉树中的空节点指向其前驱和后继.
voidInThreading(BiTreep)//线索化二叉树前驱后继
{
if(p)
{
InThreading(p->lchild);
if(!
p->lchild)
{
p->LTag=1;
p->lchild=pre;
}
if(!
pre->rchild)
{
pre->RTag=1;
pre->rchild=p;
}
pre=p;
InThreading(p->rchild);
}}
voidInOrderThreading(BiTree&Thrt,BiTreeT)
{
Thrt=(BiTree)malloc(sizeof(BiTNode));
Thrt->LTag=0;
Thrt->RTag=1;
Thrt->rchild=Thrt;
if(!
T)
Thrt->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
InThreading(T);
pre->rchild=Thrt;
pre->RTag=1;
Thrt->rchild=pre;
}
}
(10)查找二叉树的前驱和后继,基于中序线索化二叉树后,根据LTag和RTag的只能即可确定出节点的前驱和后继.
BiTreeInprenode(BiTreep)//查找前驱
{
BiTreepre;
pre=p->lchild;
if(p->LTag!
=1)
while(pre->RTag==0)
pre=pre->rchild;
return(pre);
}
BiTreeInpostnode(BiTreep)//查找后继
{
BiTreepost;
post=p->rchild;
if(p->RTag!
=1)
while(post->LTag==0)
post=post->lchild;
return(post);
}
(11)查找某个二叉树节点.根据data域的值,可以利用递归遍历查找出二叉树的对应节点的data域的值,从而确定所要查询的节点是否在二叉树中.
BiTreesearch(BiTreeBT,charx)//查找结点X,BiTree是二叉树结点类型的指针
{
if(BT->data==x)returnBT;
elseif(BT->lchild)
returnsearch(BT->lchild,x);
elseif(BT->rchild)
returnsearch(BT->rchild,x);
else
returnNULL;
}
3.3调试分析
(1)先序递归遍历
图3二叉树先序递归遍历
(2)先序非递归遍历
图4二叉树先序非递归遍历
(3)中序递归遍历
图5二叉树中序递归遍历
(4)中序非递归遍历
图6二叉树中序非递归遍历
(5)后序递归遍历
图7二叉树后序递归遍历
(6)后序非递归遍历
图8二叉树后序非递归遍历
(7)层序遍历
图8层序遍历二叉树
(8)查找二叉树节点的前驱和后继
图9查找前驱和后继
(9)判断节点是否在二叉树内
图10判断节点是否在二叉树内
4、总结
数据结构是一门博大精深的课程,尤其是通过这次课程设计,我深切是了解到算法为何是程序的灵魂了,算法决定一个程序的好与坏,效率高与效率低.在以前的c语言学习中,编写的程序大多数都是简短的实现单一功能的程序,没有了解到程序与程序之间的联系,和不同算法之间是如何相联系的.
而这次试验却完全不一样.编写程序前需要自己做一个好的规划和设计,不断去了解所需要的编写的功能概念和算法,一开始总是很难,但随着不断地深入,我渐渐喜欢上了这种不断探索的过程,当然程序是不断出错的,而一次又一次的解决错误的过程,却使我体会到成功的喜悦.最终在自己的努力下,程序可以运行起来,实现自己所需要的功能,这是一件自豪的事情.
通过这次试验,我也体会到数据结构的重要性,只有真正理解数据类型的区别和数据类型之间的转换,才能更好地做出程序,比如查找前驱和后继的时候用户输入的是char型的数据,而查找函数需要的是BiTree的结构体数据,因为就需要search函数来转化,找到这个节点,从而查找出前驱和后继,这就是数据利用的一小点,而这一小点,让我在程序设计中避免了好多错误,巧妙地利用数据之间的关系,就可以灵活的调用函数,而避免出错.
这次试验中我有一个疑惑的部分,我输入data数据,使用scanf(“%c”,ch),在运行过程中却没法输入,这个令我很疑惑,我将程序改为cin>>ch;就可以了,我认为%c字符把enter当成字符了,而cin却不把enter当成字符,所以可以输入.像这样的小问题,我不断发现,不断解决,最终提高自己,感受到数据结构的魅力,
参考文献
[1]严蔚敏,吴伟民.数据结构(C语言版).北京:
清华大学出版社,1997.4
代码详述
#include"stdio.h"
#include"string.h"
#include"malloc.h"
#include
usingnamespacestd;
#defineMax20//结点的最大个数
typedefstructnode{
chardata;
structnode*lchild,*rchild;
intLTag,RTag,flag;//用于线索化二叉树
}BiTNode,*BiTree;//自定义二叉树的结点类型
BiTreepre;//用于线索化
intNodeNum;//NodeNum为结点数
//二叉树线索化之前先输入二叉树
BiTreeCreatBiTree1(BiTree&T)
{
charch;
if((ch=getchar())=='*')
T=NULL;//读入星号,返回空指针
else{
T=(BiTNode*)malloc(sizeof(BiTNode));//生成结点
if(!
T)
return0;
T->data=ch;
T->LTag=0;
T->RTag=0;
CreatBiTree1(T->lchild);//构造左子树
CreatBiTree1(T->rchild);//构造右子树
return(T);
}
}
//DLR先序遍历递归算法
voidPreorder1(BiTreeT)
{
if(T){
printf("%c",T->data);//访问结点
Preorder1(T->lchild);//先序遍历左子树
Preorder1(T->rchild);//先序遍历右子树
}
}
//DLR先序遍历非递归算法
voidPreorder2(BiTreeT)
{BiTreestack[Max],p;
inttop;
if(T!
=NULL){
top=0;p=T;
while(p!
=NULL||top>0)
{
while(p!
=NULL)
{
printf("%c",p->data);
stack[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{top--;
p=stack[top];
p=p->rchild;
}
}
}}
//LDR中序遍历递归算法
voidInorder1(BiTreeT)
{
if(T){
Inorder1(T->lchild);//中序遍历左子树
printf("%c",T->data);//访问结点
Inorder1(T->rchild);//中序遍历右子树
}
}
//LDR中序遍历非递归算法
voidInorder2(BiTreeT)
{BiTreestack[Max],p;
inttop;
if(T!
=NULL){
top=0;p=T;
while(p!
=NULL||top>0)
{
while(p!
=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{top--;
p=stack[top];
printf("%c",p->data);
p=p->rchild;
}
}
}}
//LRD后序遍历递归算法
voidPostorder1(BiTreeT)
{
if(T){
Postorder1(T->lchild);//后序遍历左子树
Postorder1(T->rchild);//后序遍历右子树
printf("%c",T->data);//访问结点
}
}
//LRD后序遍历非递归算法
typedefstruct
{
BiTreeptr;
inttag;
}stacknode;//设置哨兵
voidPostorder2(BiTree&T)
{stacknodes[Max],x;
BiTreep=T;
inttop;
if(T!
=NULL){
top=0;p=T;
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;
printf("%c",p->data);
}
if(top>0)
{
s[top-1].tag=2;
p=s[top-1].ptr->rchild;
}
}while(top>0);}
}
//层次遍历二叉树
voidLevelorder(BiTreeT,intNodeNum)
{
intfront=0,rear=1;
BiTNode*cq[Max],*p;//定义结点的指针数组cq
cq[1]=T;//根入队
while(front!
=rear)
{
front=(front+1)%NodeNum;
p=cq[front];//出队
printf("%c",p->data);//出队,输出结点的值
if(p->lchild!
=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchil