数据结构实验二叉树.docx
《数据结构实验二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构实验二叉树.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构实验二叉树
嵌入式系统开发实验报告
课程名称数据结构成绩
实验项目二叉树指导教师
学生姓名学号班级专业
实验地点实验日期年月日
一、实习目的
1.熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：
先序递归遍历、中序递归和非递归遍历、后序递归遍历。
了解二叉树的按层遍历、先序非递归遍历及后序递归遍历。
2.用树解决实际问题，如哈夫曼编码等。
3.加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。
二、运行环境
WindowsMicrosoftVisualC++运行界面
三、实例
1.二叉树的建立和遍历。
为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。
建立二叉树有各种不同的方法。
有一种方法利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：
序号数据元素。
结合下图的二叉树数的输入据顺序应该是：
11，22，33，44，65，76，117，128，139。
另一种算法是教材P58～P59介绍的方法，这是一个递归方法，与先序遍历有点相似。
数据的组织时先序的顺序，但是另有特点，当某结点的某孩子为空时以数据0来充当，也要输入。
结合下图的二叉树数的输入据顺序应该是：
1240003507006800900。
若当前数据不为0，则申请一个结点存入当前数据。
递归调用建立函数，建立当前结点的左右子树。
下列程序中的统计二叉树结点的函数，是对二叉树遍历方法的应用，请认真理解然后模仿练习。
/*二叉树的建立与遍历*/
#include
#include
typedefintEtype;
typedefstructBiTNode/*树结点结构体*/
{Etypedata;
structBiTNode*lch,*rch;
}BiTNode;
/*函数原形声明*/
BiTNode*creat_bt1（）;
BiTNode*creat_bt2（）;
voidinorder（BiTNode*p）;
voidnumb（BiTNode*p）;
BiTNode*t;intn,n0,n1,n2;
/*主函数*/
voidmain（）
{charch;intk;
do{printf（"\n\n\n"）;
printf（"\n\n1.建立二叉树方法1"）;
printf（"\n\n2.建立二叉树方法2"）;
printf（"\n\n3.中序递归遍历二叉树"）;
printf（"\n\n4.计算树中结点个数"）;
printf（"\n\n5.结束程序运行"）;
printf（"\n======================================"）;
printf（"\n请输入您的选择（1,2,3,4,5,6）"）;scanf（"%d",&k）;
switch（k）
{case1:
t=creat_bt1（）;break;/*调用性质5建立二叉树算法*/
case2:
t=creat_bt2（）;break;/*调用递归建立二叉树算法*/
case3:
{inorder（t）;/*调用中序遍历*/
printf（"\n\n打回车键，继续。
"）;ch=getchar（）;
}break;
case4:
{n=0;n0=0;n1=0;n2=0;/*全局变量置0*/
numb（t）;
printf（"\n二叉树结点总数n=%d",n）;
printf（"\n二叉树叶子结点数n0=%d",n0）;
printf（"\n度为1的结点数n1=%d",n1）;
printf（"\n度为2的结点数n2=%d",n2）;
printf（"\n\n打回车键，继续。
"）;ch=getchar（）;
}break;
case5:
exit（0）;
}/*switch*/
printf（"\n----------------"）;
}while（k>=1&&k<5）;
printf（"\n再见！
"）;
printf（"\n打回车键，返回。
"）;ch=getchar（）;
}/*main*/
/*利用二叉树性质5，借助一维数组V建立二叉树*/
BiTNode*creat_bt1（）
{BiTNode*t,*p,*v[20];inti,j;Etypee;
/*输入结点的序号i、结点的数据e*/
printf（"\ni,data="）;scanf（"%d,%d",&i,&e）;
while（i!
=0&&e!
=0）/*当i,e都为0时，结束循环*/
{p=（BiTNode*）malloc（sizeof（BiTNode））;
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if（i==1）t=p;/*序号为1的结点是根*/
else{j=i/2;
if（i%2==0）v[j]->lch=p;/*序号为偶数，做左孩子*/
elsev[j]->rch=p;/*序号为奇数，做右孩子*/
}
printf（"\ni,data="）;scanf（"%d,%d",&i,&e）;
}
return（t）;
}/*creat_bt1*/
/*模仿先序递归遍历方法，建立二叉树*/
BiTNode*creat_bt2（）
{BiTNode*t;inte;
printf（"\ndata="）;scanf（"%d",&e）;
if（e==0）t=NULL;/*对于0值，不分配新结点*/
else{t=（BiTNode*）malloc（sizeof（BiTNode））;
t->data=e;
t->lch=creat_bt2（）;/*左孩子获得新指针值*/
t->rch=creat_bt2（）;/*右孩子获得新指针值*/
}
return（t）;
}/*creat_bt2*/
/*中序递归遍历二叉树*/
voidinorder（BiTNode*p）
{if（p）{inorder（p->lch）;
printf（"%3d",p->data）;
inorder（p->rch）;
}
}/*inorder*/
/*利用中序递归遍历二叉树的方法，计算树中结点个数*/
/*读者可以试着运用先序或后序递归遍历二叉树方法重新编写这一段函数*/
voidnumb（BiTNode*p）
{if（p）{numb（p->lch）;
{printf（"%3d",p->data）;
n++;
if（p->lch==NULL&&p->rch==NULL）n0++;
if（（p->lch==NULL&&p->rch!
=NULL）||（p->lch!
=NULL&&p->rch==NULL））n1++;
if（p->lch!
=NULL&&p->rch!
=NULL）n2++;
}/*把访问的功能扩大了*/
numb（p->rch）;
}
}/*inorder*/
程序运行界面如下：
四、实习题
1.建立一棵二叉树，要求用先序非递归方法遍历二叉树。
程序设计如下：
#include
#include
#include
#definemaxsize10
#definestackmaxsize100
/*二叉链表的结构体建立*/
typedefstructnode
{chardata;
structnode*lchild,*rchild;
}bitree;
/*顺序堆栈结构体的建立*/
typedefstruct
{bitreestack[stackmaxsize];
inttop;
}Seqstack;
/*初始化顺序堆栈*/
voidinitstack（Seqstack*s）
{
s->top=0;
}
/*进栈函数*/
intpush（Seqstack*s,bitree*ch）
{if（s->top==stackmaxsize-1）
printf（"\nStackisOverflow!
\n"）;
else{
s->top++;
s->stack[s->top]=*ch;
return1;
}
}/*push*/
/*出栈操作*/
bitree*pop（Seqstack*s）
{
bitreep1,*p=&p1;
*p=s->stack[s->top];
s->top--;
returnp;
}
/*判断栈是否为空*/
intempty（Seqstack*s）
{if（s->top==-1）
return1;
else
return0;
}
bitree*q[maxsize];
/*创建二叉树*/
bitree*creatree（）
{
charch;
intfront,rear;
bitree*t,*s;
t=NULL;
front=1;
rear=0;
ch=getchar（）;
while（ch!
='#'）
{
s=NULL;
if（ch!
='@'）
{s=（bitree*）malloc（sizeof（bitree））;
s->data=ch;
s->lchild=s->rchild=NULL;
}
rear++;
q[rear]=s;
if（rear==1）
t=s;
else
{
if（s!
=NULL&&q[front]!
=NULL）
if（rear%2==0）
q[front]->lchild=s;
elseq[front]->rchild=s;
if（rear%2==1）front++;
}
ch=getchar（）;
}
returnt;
}
/*先序非递归遍历*/
voidpreorder（bitree*t）
{bitree*p=t;
Seqstacks1,*s=&s1;
initstack（s）;
while（（p!
=NULL）||（!
empty（s）））
{
if（p!
=NULL）
{
printf（"%2c",p->data）;
push（s,p）;
p=p->lchild;
}
else
{
p=pop（s）;
p=p->rchild;
}
}
}
/*主函数*/
voidmain（）
{
bitree*tr;
printf（"创建二叉树：
\n请输入节点信息：
"）;
tr=creatree（）;
printf（"非递归先序遍历二叉树的结果为：
\n"）;
preorder（tr）;
printf（"\n"）;
}
程序运行界面输出如下：
2.建立一棵二叉树，要求用“按层遍历”的方法遍历二叉树”的函数。
程序设计如下：
#include
#include
#definemax100
typedefcharElemType;
/*二叉链表的结构体创建*/
typedefstructBiTNode{
ElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BinTree;
/*函数声明*/
voidCreateBinTree（BinTree&T）;/*建立二叉树*/
voidLevleOrder（BinTreeT）;/*层次遍历二叉树*/
voidPrint_BinTree（BinTreeT,inti）;/*按要求输出二叉树*/
/*主函数*/
intmain（）
{
BinTreeT;inti=0;
printf（"\n按先序遍历法，创建二叉树：
\n"）;
CreateBinTree（T）;
printf（"\n层次遍历二叉树并输出遍历结果：
\n"）;
LevleOrder（T）;
printf（"\n按树形打印输出二叉树：
\n"）;
Print_BinTree（T,i）;
return0;
}
/*建立二叉树*/
voidCreateBinTree（BinTree&T）
{
charch;
ch=getchar（）;
if（ch=='#'）T=NULL;
else{
if（!
（T=（BiTNode*）malloc（sizeof（BiTNode））））printf（"%c""结点建立失败!
"）;
T->data=ch;
CreateBinTree（T->lchild）;
CreateBinTree（T->rchild）;
}
}
/*层次遍历二叉树*/
voidLevleOrder（BinTreeT）
{
BinTreeQueue[max],p;
intfront,rear;
front=rear=0;
if（T）
{
Queue[rear++]=T;
while（front!
=rear）{
p=Queue[front++];
printf（"%c",p->data）;
if（p->lchild!
=NULL）Queue[rear++]=p->lchild;
if（p->rchild!
=NULL）Queue[rear++]=p->rchild;}
}
}
/*按要求输出二叉树*/
voidPrint_BinTree（BinTreeT,inti）//i表示结点所在层次,初次调用时i=0
{
if（T->rchild）Print_BinTree（T->rchild,i+1）;//函数递归来建立层次。
for（intj=1;j<=i;j++）printf（""）;//打印i个空格以表示出层次
printf（"%c\n",T->data）;//打印T元素,换行
if（T->lchild）Print_BinTree（T->lchild,i+1）;
}
程序运行界面输出如下：
3.给定一组值，建立一棵二叉树，求二叉数的树深。
程序设计如下：
#include
#include
#include
#defineNULL0
/*二叉树链表的结构体定义*/
typedefstructBiTNode{
chardata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
/*函数声明*/
BiTreeCreate（BiTreeT）;/*二叉树的建立*/
voidPreorder（BiTreeT）;/*前序遍历函数*/
intSumleaf（BiTreeT）;/*二叉树的叶子结点个数的计算*/
voidzhongxu（BiTreeT）;/*中序遍历函数*/
voidhouxu（BiTreeT）;/*后序遍历函数*/
intDepth（BiTreeT）;/*求二叉树的树深*/
/*主函数*/
voidmain（）
{
BiTreeT;
intsum,dep;
printf（"按先序递归遍历方法，如下建立二叉树\n"）;
T=Create（T）;
printf（"1.先序递归遍历二叉树：
\n"）;
Preorder（T）;
printf（"\n"）;
printf（"2.中序递归遍历二叉树：
\n"）;
zhongxu（T）;
printf（"\n"）;
printf（"3.后序递归遍历二叉树：
\n"）;
houxu（T）;
printf（"\n"）;
printf（"4.求二叉树的叶子结点的个数：
\n"）;
sum=Sumleaf（T）;
printf（"%d\n",sum）;
printf（"5.求二叉树的树的深度：
\n"）;
dep=Depth（T）;
printf（"%d",dep）;
printf（"\n"）;
}
/*二叉树的建立*/
BiTreeCreate（BiTreeT）
{
charch;
ch=getchar（）;
if（ch=='@'）
T=NULL;/*对于@值，不分配新结点*/
else{
if（!
（T=（BiTNode*）malloc（sizeof（BiTNode））））
printf（"Error!
"）;
T->data=ch;
T->lchild=Create（T->lchild）;/*左孩子获得新指针值*/
T->rchild=Create（T->rchild）;/*右孩子获得新指针值*/
}
returnT;
}
/*前序遍历函数*/
voidPreorder（BiTreeT）
{
if（T）{
printf（"%c",T->data）;/*遍历根结点*/
Preorder（T->lchild）;/*遍历左子树结点*/
Preorder（T->rchild）;/*遍历右子树结点*/
}
}
/*二叉树的叶子结点个数的计算*/
intSumleaf（BiTreeT）
{
intsum=0,m,n;
if（T）{
if（（!
T->lchild）&&（!
T->rchild））
sum++;/*叶子结点数目加1*/
m=Sumleaf（T->lchild）;/*计算叶子结点数目*/
sum+=m;
n=Sumleaf（T->rchild）;/*计算叶子结点数目*/
sum+=n;
}
returnsum;
}
/*中序遍历函数*/
voidzhongxu（BiTreeT）
{
if（T）{
zhongxu（T->lchild）;/*遍历左子树结点*/
printf（"%c",T->data）;/*遍历根结点*/
zhongxu（T->rchild）;/*遍历右子树结点*/
}
}
/*后序遍历函数*/
voidhouxu（BiTreeT）
{
if（T）{
houxu（T->lchild）;/*遍历左子树结点*/
houxu（T->rchild）;/*遍历右子树结点*/
printf（"%c",T->data）;/*遍历根结点*/
}
}
/*求二叉树的树深*/
intDepth（BiTreeT）
{
intdep=0,depl,depr;
if（!
T）dep=0;
else{
depl=Depth（T->lchild）;
depr=Depth（T->rchild）;
dep=1+（depl>depr?
depl:
depr）;
}
returndep;
}
程序运行界面输出如下：
五、实验结论
树的遍历是指按一定的规律走遍树的各个顶点，且使每一个顶点仅被访问一次，即找一个完整有规律的走法，以得到树中所有结点的一个线性排列。
二叉树的遍历可分为以下四种：
先序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）和层次遍历。
先序遍历是指先访问根节点，然后分别先序遍历左子树、右子树；中序遍历是指先中序遍历左子树，然后访问根结点，最后中序遍历右子树；后序遍历是指先后序遍历左、右子树，然后访问根结点；层次遍历是指按二叉树的层序次序（即从根结点层至叶节点层），同一层中按先左子树再右子树的次序遍历二叉树。
六、实验总结
通过此次实验，我掌握了二叉树在二叉链表存储结构中的常用遍历方法：
先序递归遍历、中序递归和非递归遍历、后序递归遍历。
了解到了二叉树的按层遍历、先序非递归遍历及后序递归遍历。
并且通过学习二叉树的这种非线性存储结构能够解决实际问题，例如哈夫曼问题。
尤其是在编写程序的过程中，我明白了一个行之有效的程序，在于对所学知识的已掌握知识的利用和发挥，并且我加深了对“数据结构+算法=程序”的理解和认识，这样有助于自己提高编写较复杂程序的能力。
升级会员 