二叉树数据结构课程设计报告.docx
《二叉树数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《二叉树数据结构课程设计报告.docx（15页珍藏版）》请在冰点文库上搜索。
二叉树数据结构课程设计报告
武汉纺织大学
数学与计算机学院
数据结构课程设计报告
二叉树的编码
学生姓名：
学号：
班级：
指导老师：
报告日期：
年月日
1题目与要求
1.1问题提出
其中，x，y是两个整数坐标，采用由上至下和从左到右的方法对这些坐标进行赋值；size表示结点所有子孙结点的个数；depth表示结点的层次。
如下图所示：
要求利用所学的知识编写代码创建二叉树，求x,y,size,depth的值，并完成相应的操作，掌握二叉树的基本知识！
1.2本系统涉及的知识点
涉及的相关知识点：
1.二叉树的先序建立
2.递归算法
3.队列
4.逆中序输出结点
5.二叉树的遍历
6.凹入法
1.3功能要求
实现的主要功能：
⑴根据课本“算法6.4”建立上图所示的二叉树，并且对每个结点的（x，y，size，depth）都赋零值，即（0，0，0，0）。
⑵编写算法求每个结点的（x，y）。
⑶编写算法求每个结点的size。
⑷编写算法求每个结点的depth。
⑸求二叉树中分支结点和叶子结点的数目。
⑹二叉树的繁茂度定义为各层结点数的最大值与树的深度的乘积，求二叉树的繁茂度。
⑺编写算法判别给定二叉树是否为完全二叉树。
⑻按中序凹入法显示二叉树。
⑼对二叉树进行层序遍历。
⑽销毁二叉树中的所有结点，要求在销毁每一个结点前，输出该结点的数据域。
2功能设计
2.1数据结构定义
二叉树的二叉链表存储表示如下：
typedefstructBiNode
{
chardata;
intx,y,size,depth;
structBiNode*lchild,*rchild;
}BiNode,*BiTree;
2.2模块图
3程序代码设计
#include"stdio.h"
#include"stdlib.h"
typedefstructBiNode
{
chardata;
intx,y,size,depth;
structBiNode*lchild,*rchild;
}BiNode,*BiTree;
intmax,max1,max2;
BiTreecreat（BiTreeT）
{
charc;
scanf（"%c",&c）;
if（c=='#'）
T=NULL;
else
{
T=（BiTree）malloc（sizeof（BiNode））;
T->data=c;
T->x=0;
T->y=0;
T->size=0;
T->depth=0;
printf（"\n请输入%c结点的左子结点:
",T->data）;
fflush（stdin）;
T->lchild=creat（T->lchild）;
printf（"\n请输入%c结点的右子结点:
",T->data）;
fflush（stdin）;
T->rchild=creat（T->rchild）;
}
returnT;
}
voiddegree（BiTreeT）//求二叉树的各层结点树的最大值
{
BiTreeTree[30];
intn=1,i=0,flag;
if（T->y==0）
{
Tree[i]=T;
Tree[i]->x=n;
Tree[i]->depth=i+1;
max=Tree[i]->depth;
i++;n++;
while（i>=1）
{
flag=0;
while（Tree[i-1]->lchild!
=NULL）
{
Tree[i]=Tree[i-1]->lchild;
if（Tree[i]->y==0）
{
Tree[i]->x=n;
Tree[i]->depth=i+1;
max=max>Tree[i]->depth?
max:
Tree[i]->depth;
i++;
n++;
}
else
break;
}
if（Tree[i-1]->rchild!
=NULL）
{
Tree[i]=Tree[i-1]->rchild;
if（Tree[i]->y==0）
{
Tree[i]->x=n;
Tree[i]->depth=i+1;
max=max>Tree[i]->depth?
max:
Tree[i]->depth;
n++;
i++;
flag=1;
}
}
if（flag==0）
{
Tree[i-1]->y=n;
n++;
i--;
}
}
}
}
voidxy（BiTreeT）//求结点的（x，y）
{
if（T!
=NULL）
{
printf（"\t\t%c",T->data）;
T->size=（T->y-1-T->x）/2;
printf（"（%d,%d）\n",T->x,T->y）;
xy（T->lchild）;
xy（T->rchild）;
}
}
voidsize（BiTreeT）//求结点的size
{
if（T!
=NULL）
{
printf（"\t\t%c",T->data）;
T->size=（T->y-1-T->x）/2;
printf（"的size为：
%d\n",T->size）;
size（T->lchild）;
size（T->rchild）;
}
}
voidNodedepth（BiTreeT）//计算结点的depth
{
if（T!
=NULL）
{
printf（"\t\t%c",T->data）;
T->size=（T->y-1-T->x）/2;
printf（"的depth为：
%d\n",T->depth）;
Nodedepth（T->lchild）;
Nodedepth（T->rchild）;
}
}
voidPrintTree（BiTree&T,intLayer）//凹入法打印。
按竖向树状打印的二叉树，layer为结点层次
{
inti=0;
if（T）
{
PrintTree（T->rchild,Layer+1）;//处理右孩子
//从此开始处理根
for（;iprintf（""）;
printf（"%c\n",T->data）;//按逆中序输出结点，用层深决定结点的左右位置
//处理根结束
PrintTree（T->lchild,Layer+1）;//处理左孩子
}
}
voidLevelTraverse（BiTree&T）//按层遍历
{
intfront=0,rear=0;
BiTreeQueue[20];
BiTreep;//表示队头指针和队尾指针
printf（"二叉树的层次遍历为：
"）;
if（T）
{
p=T;//根指针入队
Queue[rear]=p;
rear=（rear+1）%20;//队尾指针加一对20取余，可实现循环队列，合理利用空间
while（front!
=rear）//队不空
{
p=Queue[front];//出队，将值赋给p
printf（"%c",p->data）;
front=（front+1）%20;
if（p->lchild）//如果p有左子树，将左子树入队
{
Queue[rear]=p->lchild;
rear=（rear+1）%20;
}
if（p->rchild）//如果p有右子树，将右子树入队
{
Queue[rear]=p->rchild;
rear=（rear+1）%20;
}
}
}
printf（"\n"）;
}
voidJudgeandCount（BiTreeT）//求结点数，并判断是否为完全二叉树
{
BiTreeTree[30],Tree1[30];
inti=0,j=1,n=0,key,k,sum=1,k0,flag=1,k1,sum0=0,k2;
max1=1;
Tree[i]=T;
if（Tree[i]->size==0）
T->size=（T->y-1-T->x）/2;
k=Tree[i]->size+1;
while（j<=max）
{
if（j==max-1）
{
for（k0=1;k0<=j;k0++）
sum*=2;
sum--;
sum0++;
if（sum==sum0）
{
key=k-sum;
k2=i;
if（key%2==0）
{
k0=key/2;
for（k1=0;k1{
if（Tree[k2]->lchild==NULL||Tree[k2]->rchild==NULL）
{
flag=0;
break;
}
k2--;
}
}
else
{
k0=key/2+1;
for（k1=0;k1{
if（Tree[k2]->lchild==NULL||Tree[k2]->rchild==NULL）
{
flag=0;
break;
}
}
if（（flag==1）&&（Tree[k2-k0+1]->lchild==NULL））
flag=0;
}
}
else
flag=0;
}
while（i>=0）
{
if（Tree[i]->lchild!
=NULL）
{
Tree1[n]=Tree[i]->lchild;
n++;
}
if（Tree[i]->rchild!
=NULL）
{
Tree1[n]=Tree[i]->rchild;
n++;
}
if（（Tree[i]->lchild==NULL）&&（Tree[i]->rchild==NULL））
max2++;
i--;
}
i=0;
sum0+=n;
max1=max1>n?
max1:
n;
n--;
while（n>=0）
{
Tree[i]=Tree1[n];
n--;
i++;
}
n=0;
j++;
i--;
}
printf（"\n\t该二叉树繁茂度为%d\n",max*max1）;
if（flag==1）
printf（"\t该二叉树为完全二叉树\n"）;
else
printf（"\t该二叉树为非完全二叉树\n"）;
printf（"\t该二叉树的叶子节点有%d个\n",max2）;
printf（"\t该二叉树的分支节点有%d个\n",k-max2）;
}
voiddestroy（BiTreeT）//销毁二叉树
{
if（T!
=NULL）
{
destroy（T->lchild）;
destroy（T->rchild）;
printf（"\t\t%c",T->data）;
printf（"（%d,%d,%d,%d）\n",T->x,T->y,T->size,T->depth）;
free（T）;
}
}
voidmain（）
{
BiTreeT;
T=NULL;
inti,j=1;
do
{
printf（"*************************************菜单***************************************\n"）;
printf（"\t\t\t1.创建二叉树\n"）;
printf（"\t\t\t2.求每个结点的（x,y）\n"）;
printf（"\t\t\t3.求每个结点的size\n"）;
printf（"\t\t\t4.求每个结点的depth\n"）;
printf（"\t\t\t5.求分支结点和叶子结点、繁茂度、判别完全二叉树\n"）;
printf（"\t\t\t6.按中序凹入法显示二叉树\n"）;
printf（"\t\t\t7.对二叉树进行层序遍历\n"）;
printf（"\t\t\t8.销毁二叉树中的所有结点\n"）;
printf（"\t\t\t9.退出程序\n\n"）;
printf（"********************************************************************************\n"）;
printf（"请输入您的选择（1-9）:
\n"）;
scanf（"%d",&i）;
switch（i）
{
case1:
printf（"请输入结点data域，输入#代表结束\n"）;
getchar（）;
T=creat（T）;
printf（"\t\t\t创建成功!
\n"）;
break;
case2:
degree（T）;putchar（'\n'）;xy（T）;break;
case3:
degree（T）;putchar（'\n'）;size（T）;break;
case4:
degree（T）;putchar（'\n'）;Nodedepth（T）;break;
case5:
if（max==0）degree（T）;JudgeandCount（T）;break;
case6:
putchar（'\n'）;PrintTree（T,1）;break;
case7:
putchar（'\n'）;LevelTraverse（T）;break;
case8:
degree（T）;putchar（'\n'）;destroy（T）;printf（"\t\t\t各结点已销毁!
\n"）;break;
case9:
printf（"\t\t\t谢谢使用!
Thankyou!
\n"）;exit（0）;break;
default:
printf（"Error!
\n"）;
}
}while（i>=1&&i<=9）;
}
4课程设计总结
在此次的课程设计中，由于经验的缺乏以及粗心大意，在程序设计中犯了许多错误，但是经过一番思考并且在同学的帮助下，找到了导致程序错误的原因，经过多次修改和调试，程序终于能正常运行，而且能够完成课程设计任务中的大部分功能，同时在此次的课程设计中我又学到了许多知识，对计算机科学的兴趣又多了一分，但我现在掌握的可能只是计算机科学的皮毛，所以我会继续努力，刻苦钻研，希望在计算机方面有更高的成绩，对计算机科学有更深的研究！
同时也感谢老师给我们这次课程设计的机会，让我们学有所用，并且认识我们自身的不足，让我们能不断完善自己！
升级会员 