课程设计二叉树讲解Word文档下载推荐.docx
《课程设计二叉树讲解Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《课程设计二叉树讲解Word文档下载推荐.docx（30页珍藏版）》请在冰点文库上搜索。
包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。
（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&
{
charch;
if（（ch=getchar（））=='
*'
）
T=NULL;
//读入星号，返回空指针
else{
T=（BiTNode*）malloc（sizeof（BiTNode））;
//生成结点
if（!
return0;
T->
data=ch;
LTag=0;
RTag=0;
CreatBiTree1（T->
lchild）;
//构造左子树
rchild）;
//构造右子树
return（T）;
}
}
（2）先序递归算法，读取头节点后，输出，接下来使用递归算法，不断地向下延伸读取，输出即可。
voidPreorder1（BiTreeT）
{
if（T）{
printf（"
%c"
T->
data）;
//访问结点
Preorder1（T->
//先序遍历左子树
//先序遍历右子树
（3）先序遍历非递归算法，设置一个stack的栈用来存储读取的二叉树序列,利用栈先进后出的特性,输出栈即为先序遍历.
voidPreorder2（BiTreeT）
{BiTreestack[Max],p;
inttop;
if（T!
=NULL）{
top=0;
p=T;
while（p!
=NULL||top>
0）
{
while（p!
=NULL）
{
printf（"
p->
stack[top]=p;
top++;
p=p->
lchild;
}
if（top>
{top--;
p=stack[top];
rchild;
}}}}
（4）中序遍历递归算法和先序遍历思想差不多,只是在遍历完左边后再输出头节点.
voidInorder1（BiTreeT）
Inorder1（T->
//中序遍历左子树
//中序遍历右子树
}}
（5）中序遍历非递归算法,同理也是利用栈的特性来存储读取出来的data域的值,修改下出栈方式即可.
voidInorder2（BiTreeT）
{BiTreestack[Max],p;
printf（"
（6）后序遍历递归算法和先序遍历思想差不多,只是在遍历完最后后再输出头节点.
voidPostorder1（BiTreeT）
Postorder1（T->
//后序遍历左子树
//后序遍历右子树
（7）后序遍历非递归算法,首先设置一个typedefstructstacknode的结构体为监查哨兵,输出过的节点都做上标记,防止二次输出.
typedefstruct
BiTreeptr;
inttag;
}stacknode;
//设置哨兵
voidPostorder2（BiTree&
{stacknodes[Max],x;
BiTreep=T;
if（T!
do
s[top].ptr=p;
s[top].tag=1;
while（top>
0&
&
s[top-1].tag==2）
x=s[--top];
p=x.ptr;
s[top-1].tag=2;
p=s[top-1].ptr->
}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];
//出队
//出队，输出结点的值
if（p->
lchild!
rear=（rear+1）%NodeNum;
cq[rear]=p->
//左子树入队
rchild!
//右子树入队
}}}
（9）线索化二叉树,利用voidInThreading（BiTreep）和voidInOrderThreading（BiTree&
Thrt,BiTreeT）可完成二叉树中序线索化.主要思想是使二叉树中的空节点指向其前驱和后继.
voidInThreading（BiTreep）//线索化二叉树前驱后继
if（p）
InThreading（p->
p->
lchild）
p->
LTag=1;
lchild=pre;
}
pre->
rchild）
pre->
RTag=1;
rchild=p;
pre=p;
}}
voidInOrderThreading（BiTree&
Thrt=（BiTree）malloc（sizeof（BiTNode））;
Thrt->
rchild=Thrt;
if（!
Thrt->
lchild=Thrt;
else
lchild=T;
pre=Thrt;
InThreading（T）;
pre->
rchild=pre;
（10）查找二叉树的前驱和后继,基于中序线索化二叉树后,根据LTag和RTag的只能即可确定出节点的前驱和后继.
BiTreeInprenode（BiTreep）//查找前驱
BiTreepre;
pre=p->
if（p->
LTag!
=1）
while（pre->
RTag==0）
pre=pre->
return（pre）;
}
BiTreeInpostnode（BiTreep）//查找后继
BiTreepost;
post=p->
RTag!
while（post->
LTag==0）
post=post->
return（post）;
（11）查找某个二叉树节点.根据data域的值,可以利用递归遍历查找出二叉树的对应节点的data域的值,从而确定所要查询的节点是否在二叉树中.
BiTreesearch（BiTreeBT,charx）//查找结点X，BiTree是二叉树结点类型的指针
if（BT->
data==x）returnBT;
elseif（BT->
returnsearch（BT->
lchild,x）;
rchild,x）;
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当成字符,所以可以输入.像这样的小问题,我不断发现,不断解决,最终提高自己,感受到数据结构的魅力,
参考文献
代码详述
#include"
stdio.h"
string.h"
malloc.h"
#include<
iostream>
usingnamespacestd;
#defineMax20//结点的最大个数
typedefstructnode{
chardata;
structnode*lchild,*rchild;
intLTag,RTag,flag;
//用于线索化二叉树
}BiTNode,*BiTree;
//自定义二叉树的结点类型
BiTreepre;
//用于线索化
intNodeNum;
//NodeNum为结点数
//二叉树线索化之前先输入二叉树
//DLR先序遍历递归算法
//DLR先序遍历非递归算法
//LDR中序遍历递归算法
voidInorder1（BiTreeT）
//LDR中序遍历非递归算法
voidInorder2（BiTreeT）
//LRD后序遍历递归算法
//LRD后序遍历非递归算法
//层次遍历二叉树
lchil
升级会员 