数据结构与算法实验报告二叉树.docx
《数据结构与算法实验报告二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构与算法实验报告二叉树.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构与算法实验报告二叉树
阳工程学院
学生实验报告
（课程名称：
数据结构与算法）
实验题目：
二叉树
班级软本111学号2011417104姓名吴月芬
地点F座606指导教师柳祝世东
实验日期:
2012年10月25日
一、实验目的
1．掌握二叉树的结构特征，以及各种存储结构的特点及适用围。
2．掌握用指针类型描述、访问和处理二叉树的运算。
二、实验环境
TurboC或是VisualC++
三、实验容与要求
1．输入字符序列，建立二叉链表。
2．按先序、中序和后序遍历二叉树（递归算法）。
3．按某种形式输出整棵二叉树。
4．求二叉树的高度。
5．求二叉树的叶结点个数。
6．交换二叉树的左右子树。
7．借助队列实现二叉树的层次遍历。
8．在主函数中设计一个简单的菜单，调试上述算法，要求1-3必做，4-7为选做。
为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。
建立二叉树有各种不同的方法。
一种方法是利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：
（序号，数据元素）。
图4.1所示二叉树的输入数据顺序应该是：
（1,a），（2,b），（3,c），（4,d），（6,e），（7,f），（9,g），（13,h）。
另一种算法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。
数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。
这时，图4.1所示二叉树的输入数据顺序应该是：
abd#g###ce#h##f##。
若当前数据不为“#”，则申请一个结点存入当前数据。
递归调用建立函数，建立当前结点的左右子树。
四、实验过程及结果分析
（一）二叉树
1.二叉树的综合程序源代码如下所示：
#include
#include
#defineNULL0
structbitree
{
chardata;
structbitree*lchild,*rchild;
};
structbitree*createbitree_1（structbitree*t）
{
intch;
scanf（"%d",&ch）;
if（ch==0）
{
t=NULL;
}
else
{
t->data=ch;
t->lchild=（structbitree*）malloc（sizeof（structbitree））;
t->lchild=createbitree_1（t->lchild）;
t->rchild=（structbitree*）malloc（sizeof（structbitree））;
t->rchild=createbitree_1（t->rchild）;
}
returnt;
}
structbitree*createbitree_2（structbitree*t）
{
intch;
scanf（"%d",&ch）;
if（ch==0）
{
t=NULL;
}
else
{
t->lchild=（structbitree*）malloc（sizeof（structbitree））;
t->lchild=createbitree_2（t->lchild）;
t->data=ch;
t->rchild=（structbitree*）malloc（sizeof（structbitree））;
t->rchild=createbitree_2（t->rchild）;
}
returnt;
}
voidpreorder_1（structbitree*T）
{
if（T!
=NULL）
{
printf（"%d\t\t",T->data）;
preorder_1（T->lchild）;
preorder_1（T->rchild）;
}
}
voidpreorder_yezi（structbitree*T）
{
if（T!
=NULL）
{
if（T->lchild==NULL&&T->rchild==NULL）//只输出叶子节点
printf（"%d\t\t",T->data）;
preorder_1（T->lchild）;
preorder_1（T->rchild）;
}
}
voidinorder_1（structbitree*H）
{
if（H）
{
inorder_1（H->lchild）;
printf（"%d\t\t",H->data）;
inorder_1（H->rchild）;
}
}
voidpreorder_2（structbitree*p）
{
structbitree*s[100];
inttop=-1;
while（p!
=NULL||top!
=-1）
{
while（p!
=NULL）
{
top++;
s[top]=p;
printf（"%d\t\t",p->data）;
p=p->lchild;
}
if（top!
=-1）
{
p=s[top];
top--;
p=p->rchild;
}
}
}
voidpreorder_yezi_2（structbitree*p）
{
structbitree*s[100];
inttop=-1;
while（p!
=NULL||top!
=-1）
{
while（p!
=NULL）
{
top++;
s[top]=p;
if（p->lchild==NULL&&p->rchild==NULL）//只输出叶子节点
printf（"%d\t\t",p->data）;
p=p->lchild;
}
if（top!
=-1）
{
p=s[top];
top--;
p=p->rchild;
}
}
}
voidinorder_2（structbitree*p）
{
structbitree*s[100];
inttop=-1;
while（p!
=NULL||top!
=-1）
{
while（p!
=NULL）
{
top++;
s[top]=p;
p=p->lchild;
}
if（top!
=-1）
{
p=s[top];
top--;
printf（"%d\t\t",p->data）;
p=p->rchild;
}
}
}
voidmenu_1（）
{
printf（"\n\t******菜单*******\n"）;
printf（"\t1.树的建立\n"）;
printf（"\t2.树的遍历\n"）;
printf（"\t0.退出\n"）;
}
voidmenu_2（intn）
{
if（n==1）
{
printf（"\n\t******菜单*******\n"）;
printf（"\n\t1.树的递归的先序建立\n"）;
printf（"\n\t2.树的递归的中序建立\n"）;
printf（"\n\t3.树的非递归的先序建立\n"）;
printf（"\n\t4.树的非递归的中序建立\n"）;
}
if（n==2）
{
printf（"\n\t******菜单*******\n"）;
printf（"\n\t1.树的递归的先序遍历\n"）;
printf（"\n\t2.树的递归的中序遍历\n"）;
printf（"\n\t3.树的非递归的先序遍历\n"）;
printf（"\n\t4.树的非递归的中序遍历\n"）;
printf（"\n\t5.树的递归的先序遍历叶子节点\n"）;
printf（"\n\t6.树的非递归的先序遍历叶子节点\n"）;
}
}
voidmain（）
{
structbitree*H;
intn,m;
H=（structbitree*）malloc（sizeof（structbitree））;
do
{
menu_1（）;
scanf（"%d",&n）;
if（n>2||n<0）
printf（"\n\t\t您的输入有误！
"）;
elseif（n!
=0）
{menu_2（n）;scanf（"%d",&m）;}
if（n==1）
{
if（m==1）
H=createbitree_1（H）;
if（m==2）
H=createbitree_2（H）;
}
if（n==2）
{
if（m==1）
preorder_1（H）;
if（m==2）
inorder_1（H）;
if（m==3）
preorder_2（H）;
if（m==4）
inorder_2（H）;
if（m==5）
preorder_yezi（H）;
if（m==6）
preorder_yezi_2（H）;
}
}while（n!
=0）;
}
2.运行过程
二叉树递归的先序建立过程如图1.1所示。
图1.1先序建立二叉树
二叉树的递归的先序遍历如图1.2所示。
图1.2递归先序遍历
二叉树的递归的中序遍历如图1.3所示。
图1.3递归的中序遍历
二叉树的非递归的先序遍历如图1.4所示。
图1.4非递归的先序遍历
二叉树的非递归的中序遍历如图1.5所示。
图1.5非递归的中序遍历
二叉树的递归的先序遍历叶子节点如图1.6所示。
图1.6递归的先序遍历叶子节点
二叉树的非递归的先序遍历叶子节点如图1.7所示。
图1.7非递归的先序遍历叶子节点
结束程序操作如图1.8所示。
图1.8结束程序
五、成绩评定
优
良
中
及格
不及格
出勤
容
格式
创新
效果
总评
指导教师：
年月日
升级会员 