数据结构课程设计二叉树.docx
《数据结构课程设计二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计二叉树.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构课程设计二叉树
甘肃政法学院
数据结构课程设计
题目二叉树遍历
计算机科学学院信息管理与信息系统专业
09级信息管理与信息系统班
学号：
_200981020116
姓名：
___唐占红____
指导教师：
___金涛_____
成绩：
_____________
完成时间：
_2010年12月
[摘要]二叉树是树形结构的一个重要的类型，二叉树是n（n>=0）个结点的有限集，它或者是空集（n=0），或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
二叉树的存储结构和算法比较简单，特别适合计算机处理。
即使一般形式的树也可简单的转换为二叉树。
二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。
遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。
在遍历方案中主要序遍历、后序遍历。
现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。
在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。
[关键词]二叉树遍历深度
目录
第一章数据结构课程设计题目及解析3
&1.1数据结构课程设计题目3
&1.2设计题目解析3
第二章程序设计的目的和基本要求3
&2.1程序设计的目的3
&2.2程序设计的基本要求3
第三章程序设计的内容3
&3.1算法设计的思想3
&3.3.程序数据类型4
&3.4程序模块分析5
&3.3主要的算法源代码8
&3.4程序设计的结果14
第四章程序设计的优缺点及遇到问题14
&4.1程序设计的优缺点14
&4.2程序设计遇到的问题14
第五章程序设计的总结15
&5.1心的总结15
第六章参考文献15
第一章数据结构课程设计题目及解析
&1.1数据结构课程设计题目
题目：
二叉树的建立
&1.2设计题目解析
通过这个程序主要掌握三种遍历方案，包括前序遍历、中序遍历、后序遍历，以及怎么求二叉树的高度、总结点数、叶子总个数。
并会将理论与现实结合在一起。
第二章程序设计的目的和基本要求
&2.1程序设计的目的
掌握二叉树的概念和性质、任意二叉树存储结构和任意二叉树的基本操作，并会求二叉树的高度、二叉树总结点个数、二叉树叶子结点，以及熟练掌握三种遍历，包括前序遍历、中序遍历、后序遍历。
&2.2程序设计的基本要求
在设计程序时，一定要简单明了，程序设计的思想要完善，算法要清晰，能给其他读者一目了然的感觉。
实现二叉树的建立；前序、中序和后序遍历；高度、总结点数、叶子结点数。
第三章程序设计的内容
&3.1算法设计的思想
二叉树的建立基本思想是：
依次输入的结点信息，若输入的结点不是虚结点，则建立一个新结点。
若新结点是第一个结点，则令其为根结点；否则将新结点作为孩子链接到它的双亲结点上。
如此重复下去，直至输入“00”时为止。
可设置一个指针类型的数组队列，保存已输入结点的地址。
由于是按层次自左至右输入结点的，所以先输入的结点的孩子必定比后输入结点的孩子先进入队列，因此可利用对头指针指向当前必须与其孩子结点必定建立链接的双亲结点，利用队尾指针指向当前的结点，即是当前必须与其双亲建立链接的双亲结点。
若队尾指针为偶数，则表示当前输入的结点编号是偶数，队尾指针所指向的结点应作为左孩子与其双亲链接；否则队尾指针所指的结点应作为右孩子与其双亲链接。
若双亲结点或孩子结点或孩子结点为虚结点，则无须链接。
若双亲结点与其两个孩子链接完毕，则做出队操作，使队头指针指向下一个等待链接的双亲结点。
遍历二叉树是二叉树的一种重要的运算，所谓遍历是指沿某条搜索路径周游二叉树，对数中每个结点访问一次且仅访问一次。
二叉树的定义是递归的，所以主要由三种遍历方案：
1.前序遍历二叉树
若二叉树非空，则依次进行如下操作：
（1）访问根结点；
（2）前序遍历左子数；
（3）前序遍历右子树。
2.中序遍历二叉树
若二叉树非空，则依次进行如下操作：
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
3.后序遍历二叉树
若二叉树非空，则依次进行如下操作：
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
一个结点的子树个数称为该结点的度。
一颗树的度是该树中结点的最大度数。
度为零的结点称为叶子，二叉树结点的层数是从根开始算起的，树中结点的最大层数称为树的高度或深度。
&3.3.程序数据类型
typedefintdatatype;/*datatype可以为任何类型，这里假设为int*/
#definemax60/*二叉树可能的最大长度，这里假设为60*/
typedefstructnode
{/*结构体*/
chardata;/*数据域*/
structnode*lchild,*rchild;/*左右孩子指针*/
}bitree;
&3.4程序模块分析
（1）二叉树的建立
bitree*creat（）/*二叉树的建立*/
{
inti,j;
bitree*root,*s,*Q[max];
charch;
printf（"请输入要建立的树的下标和数值：
"）;
scanf（"%d%c",&i,&ch）;
while（i!
=0&&ch!
='0'）
{
s=（bitree*）malloc（sizeof（bitree））;
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
Q[i]=s;
if（i==1）root=s;
else
{
j=i/2;
if（i%2==0）Q[j]->lchild=s;
elseQ[j]->rchild=s;
}
scanf（"%d%c",&i,&ch）;
}
returnroot;
}
（2）二叉树的三种遍历
voidpreorder（bitree*t）/*前序遍历*/
{
if（t）
{
printf（"%c",t->data）;
preorder（t->lchild）;
preorder（t->rchild）;
}
}
voidinorder（bitree*t）/*中序遍历*/
{
if（t）
{
inorder（t->lchild）;
printf（"%c",t->data）;
inorder（t->rchild）;
}
}
voidpostorder（bitree*t）/*后序遍历*/
{
if（t）
{
postorder（t->lchild）;
postorder（t->rchild）;
printf（"%c",t->data）;
}
}
（3）求二叉树的高度
inthigh（bitree*t）/*求二叉树的高度*/
{
intl,r;
if（t==NULL）return0;
else
{
l=high（t->lchild）;
r=high（t->rchild）;
return（l>r?
l:
r）+1;
}
}
（4）求二叉树的总结点数
intnodes（bitree*a）/*求总结点数*/
{
intnum1,num2;
if（a==NULL）return0;
else
{
num1=nodes（a->lchild）;
num2=nodes（a->rchild）;
returnnum1+num2+1;
}
}
（5）求叶子结点数
intleafs（bitree*b）/*求叶子结点数*/
{
intn,m;
if（b==NULL）return0;
else
if（b->lchild==NULL&&b->rchild==NULL）return1;
else
{
n=leafs（b->lchild）;
m=leafs（b->rchild）;
returnn+m;
}
（6）主函数main（）,功能是给出测试数据值，建立测试数据值的顺序表，调用creat函数、preorder函数、inorder函数、postorder函数high、函数nodes函数、leafs函数实现问题要求。
&3.3主要的算法源代码
#include"stdio.h"/*头文件*/
#include
typedefintdatatype;
#definemax60
typedefstructnode
{/*结构体*/
chardata;
structnode*lchild,*rchild;
}bitree;
bitree*creat（）/*二叉树的建立*/
{
inti,j;
bitree*root,*s,*Q[max];
charch;
printf（"请输入要建立的树的下标和数值：
"）;
scanf（"%d%c",&i,&ch）;
while（i!
=0&&ch!
='0'）
{
s=（bitree*）malloc（sizeof（bitree））;
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
Q[i]=s;
if（i==1）root=s;
else
{
j=i/2;
if（i%2==0）Q[j]->lchild=s;
elseQ[j]->rchild=s;
}
scanf（"%d%c",&i,&ch）;
}
returnroot;
}
voidpreorder（bitree*t）/*前序遍历*/
{
if（t）
{
printf（"%c",t->data）;
preorder（t->lchild）;
preorder（t->rchild）;
}
}
voidinorder（bitree*t）/*中序遍历*/
{
if（t）
{
inorder（t->lchild）;
printf（"%c",t->data）;
inorder（t->rchild）;
}
}
voidpostorder（bitree*t）/*后序遍历*/
{
if（t）
{
postorder（t->lchild）;
postorder（t->rchild）;
printf（"%c",t->data）;
}
}
inthigh（bitree*t）/*求二叉树的高度*/
{
intl,r;
if（t==NULL）return0;
else
{
l=high（t->lchild）;
r=high（t->rchild）;
return（l>r?
l:
r）+1;
}
}
intnodes（bitree*a）/*求总结点数*/
{
intnum1,num2;
if（a==NULL）return0;
else
{
num1=nodes（a->lchild）;
num2=nodes（a->rchild）;
returnnum1+num2+1;
}
}
intleafs（bitree*b）/*求叶子结点数*/
{
intn,m;
if（b==NULL）return0;
else
if（b->lchild==NULL&&b->rchild==NULL）return1;
else
{
n=leafs（b->lchild）;
m=leafs（b->rchild）;
returnn+m;
}
}
voidmain（）
{
inta,j,h,g;
bitree*b;
b=creat（）;
while
（1）
{
printf（"选择1前序遍历\n选择2中序遍历\n选择3后序遍历\n选择4求高度\n选择5求总结点数\n选择6求叶子结点个数\n选择0退出:
"）;
scanf（"%d",&a）;
switch（a）
{
case1:
printf（"该二叉树的前序遍历是：
"）;
preorder（b）;
printf（"\n"）;
break;
case2:
printf（"该二叉树的中序遍历是：
"）;
inorder（b）;
printf（"\n"）;
break;
case3:
printf（"该二叉树的后序遍历是：
"）;
postorder（b）;
printf（"\n"）;
break;
case4:
printf（"该二叉树的高度j=%d\n",j）;
j=high（b）;
break;
case5:
h=nodes（b）;
printf（"该二叉树的总结点数h=%d\n",h）;
break;
case0:
exit（0）;
}
}
}
&3.4程序设计的结果
第四章程序设计的优缺点及遇到问题
&4.1程序设计的优缺点
这个程序设计的算法清晰，思想明了，能清楚的实现二叉树的建立、三种遍历、高度、总结点数以及叶子结点数的运算。
但是这个程序在设计过程时有些麻烦，而且三种遍历的算法自己不是太清楚，不能很清楚的描述三种遍历。
&4.2程序设计遇到的问题
在设计时主要三种遍历不是很清楚，所以还是很模糊，刚开始不能很准确的把三种遍历的算法写出来，所以在这个问题上还要继续思考。
在写菜单时不是很了解，后来在同学的帮助下把程序的菜单写出来了，自己还要努力学习写菜单。
第五章程序设计的总结
&5.1心的总结
通过这次做数据结构的课程设计，我发现真正掌握一个知识点并不只是要从书上看，还要查一些相关资料，并且理论与现实结合在一起。
这次做的是关于二叉树的课程设计，刚开始以为并不是很难，但真正做的时候才发现这一节的知识点很多，也有一些比较混淆的难点，比如二叉树的遍历就有三种情况，包括前序遍历、中序遍历、后序遍历。
当然这次在做课程设计的时候遇到一些问题，不过得到大家的帮助，问题得到解决，也成功的完成了本次的课程设计。
第六章参考文献
【1】严蔚敏，吴伟明.数据结构[M].2版.清华大学出版社,1992。
【2】唐策善，数据结构——用C语言描述.高等教育出版社。
【3】殷人昆.数据结构.北京：
清华大学出版社，2001。
K
【4】严蔚敏，吴伟民，数据结构习题集（C语言版）.北京清华大学出版社，1999。
升级会员 