精品资料
精品资料
树和二叉树
、实验目的掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。
掌握用指针类型描述、访问和处理二叉树的运算。
、实验要求
认真阅读和掌握本实验的程序。
上机运行本程序。
保存和打印出程序的运行结果，并结合程序进行分析。
按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运 行结果。
、实验内容
输入字符序列，建立二叉链表。
按先序、中序和后序遍历二叉树（递归算法）。
按某种形式输出整棵二叉树。
求二叉树的高度。
求二叉树的叶节点个数。
交换二叉树的左右子树。
借助队列实现二叉树的层次遍历。
在主函数中设计一个简单的菜单，分别调试上述算法。
为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。
建立 二叉树有各种不同的方法。一种方法是利用二叉树的性质 5来建立二叉树，
输入数据时要将节点的序号（按满二叉树编号）和数据同时给出： （序号，
数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与 先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的 某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”则申请一 个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。
四、 解题思路
1、 先序遍历：O访问根结点，G先序遍历左子树，C3先序遍历右子树
2、 中序遍历：O中序遍历左子树，C2访问根结点，。中序遍历右子树
3、 后序遍历：O后序遍历左子树，C2后序遍历右子树，C3访问根结点
4、 层次遍历算法：采用一个队列 q，先将二叉树根结点入队列，然后退队列， 输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右 子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达 到按层次遍历二叉树的目的。
五、 程序清单
#in clude<stdio.h>
#in clude<stdlib.h>
#defi ne M 100
typedef char Etype; //定义二叉树结点值的类型为字符
型
//树结点结构typedef struct BiTNode
//树结点结构
Etype data;
struct BiTNode *lch,*rch;
}BiTNode,*BiTree;
BiTree que[M];
int fron t=0,rear=0;
//函数原型声明
BiTNode *creat_bt1();
BiTNode *creat_bt2();
void preorder(BiTNode *p);
void ino rder(BiTNode *p);
void postorder(BiTNode *p);
void enq ueue(BiTree);
BiTree delqueue();
void levorder(BiTree);
int treedepth(BiTree);
void prtbtree(BiTree,i nt);
void excha nge(BiTree);
in t leafco un t(BiTree);
void pain tleaf(BiTree);
BiTNode *t;
int coun t=0;
//主函数
void mai n（） {
char ch;
int k;
do{
prin tf（"\n\n\n"）;
prin tf（"\n=================== 主菜单==================="）;
prin tf（"\n\n 1.建立二叉树方法 1"）;
prin tf（"\n\n 2.建立二叉树方法 2"）;
prin tf（"\n\n 3?先序递归遍历二叉树”）；
prin tf（"\n\n 4?中序递归遍历二叉树”）；
prin tf（"\n\n 5.后序递归遍历二叉树”）；
printf（"\n\n 6.层次遍历二叉树”）；
prin tf（"\n\n 7.计算二叉树的高度”）；
prin tf（"\n\n 8.计算二叉树中叶结点个数 ”）；
prin tf（"\n\n 9.交换二叉树的左右子树 ”）；
printf（"\n\n 10.打印二叉树”）；
printf（"\n\n 0.结束程序运行”）；
prin tf（"\n============================================"）;
printf（"\n 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10）"）;
printf("
printf("二叉树的叶结点为：");pai ntleaf(t);
精品资料
{printf("后序遍历二叉树
{printf("后序遍历二叉树:");
精品资料
sea nf("%d",&k);
switch(k)
{
case 1:t=creat_bt1( );break; //调用性质5建立二叉树算法
case 2:pri ntf("\n 请输入二叉树各结点值:");fflush(stdi n);
t=creat_bt2();break; //调用递归建立二叉树算法
case 3:if(t)
{printf("先序遍历二叉树:");
preorder(t);
prin tf("\n");
}
else printf(” 二叉树为空!\n");
break;
case 4:if(t)
{printf("中序遍历二叉树:");
ino rder(t);
prin tf("\n");
}
else printf("二叉树为空!\n");
break;
case 5:if(t)
postorder(t);
prin tf("\n");
}
else printf(” 二叉树为空!\n");
break;
case 6:if(t)
{printf("层次遍历二叉树：");
levorder(t);
prin tf("\n");
}
else printf("二叉树为空！ \n");
break;
case 7:if(t)
{printf("二叉树的高度为：％d",treedepth(t));
prin tf("\n");
}
else printf("二叉树为空！ \n");
break;
case 8:if(t)
{printf("二叉树的叶子结点数为： %d\n",leafcount(t));
prin tf("\n");
精品资料
精品资料
printf("\n再见！按回车键，返回…
printf("\n再见！按回车键，返回… \n");
精品资料
else printf(” 二叉树为空！ \n");
break;
case 9:if(t)
{printf("交换二叉树的左右子树： \n");
excha nge(t);
prtbtree(t,0);
prin tf("\n");
}
else printf("二叉树为空！ \n");
break;
case 10:if(t)
\n");{printf("逆时针旋转90度输出的二叉树:
\n");
prtbtree(t,0);
prin tf("\n");
}
else printf("二叉树为空！ \n");
break;
case 0:exit(0);
} //switch
}while(k>=1 &&k<=10);
ch=getchar();
} //main
//利用二叉树性质 5，借助一维数组 V建立二叉树
BiTNode *creat_bt1()
{ BiTNode *t,*p,*v[20];i nt i,j;Etype e;
/*输入结点的序号i、结点的数据e*/
printf("\n请输入二叉树各结点的编号和对应的值(如 1，a)：");
sca nf("%d,%c",&i,&e);
while(i!=0&&e!='#') {
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;
//当i
//当i为0, e为#时，结束循环
//序号为偶数，作为左孩子
else v[j]_>rch=p;
//序号为奇数，作为右孩子
}
printf("\n请继续输入二叉树各结点的编号和对应的值： ”);
scan f("%d,%c"，&i, &e);
}
return(t);
}//creat_bt1;
//模仿先序递归遍历方法，建立二叉树
BiTNode *creat_bt2()
{
BiTNode *t;
Etype e;
scan f("%c", &e);
if(e==' #')t=NULL; //对于#值，不分配新结点
else{
t=(BiTNode *)malloc(sizeof(BiTNode));
t->data=e;
t->lch=creat_bt2();
//左孩子获得新指针值
return(t);
t->rch=creat_bt2();
//右孩子获得新指针值
} 〃creat_bt2
//先序递归遍历二叉树 void preorder(BiTNode *p)
{if(P){
prin tf("%3c",p->data);
preorder(p_>lch); preorder(p->rch);
}
} //preorder
〃中序递归遍历二叉树
void ino rder(BiTNode *p)
{if(p){
ino rder(p->lch);
prin tf("%3c",p->data);
ino rder(p->rch);
}
} //ino rder
//后序递归遍历二叉树
void postorder(BiTNode *p)
{ if(p){ postorder(p->lch);
postorder(p->rch);
prin tf("%3c",p->data);
}
} //postorder void enq ueue(BiTree T)
{
if(fron t!=(rear+1)%M)
{rear=(rear+1)%M;
que[rear]=T;}
}
BiTree delqueue()
{
if(fron t==rear)return NULL;
fron t=(fro nt+1)%M;
return(que[fro nt]);
}
//层次遍历二叉树
//层次遍历二叉树
{
BiTree p;
if(T)
{enq ueue(T);
while(fro nt!=rear){
p=delqueue( );
prin tf("%3d",p->data);
if(p->lch!=NULL)e nqueue(p->lch); if(p->rch!=NULL)e nq ueue(p->rch);
}
}
} int treedepth(BiTree bt)
{
int hl,hr,max;
if(bt!=NULL)
{ hl=treedepth(bt->lch); hr=treedepth(bt->rch); max=(hl>hr)?hl:hr; return (max+1);
}
else return (0);
} void prtbtree(BiTree bt,i nt level)
形
{int j;
if(bt)
//计算二叉树的高度〃
//计算二叉树的高度
〃逆时针旋转90度输出二叉树树
for(j=0;j<=6*level;j++)pri ntf(" ”)；
prin tf("%c\n",bt->data);
prtbtree(bt->lch,level+1);
}
}
void excha nge(BiTree bt) // 交换二叉树左右子树
{BiTree p;
if(bt)
{p=bt->lch;bt->lch=bt->rch;bt->rch=p;
excha nge(bt->lch);excha nge(bt->rch);
}
}
in t leafcou nt(BiTree bt) // 计算叶结点数
{
if(bt!=NULL)
{leafc oun t(bt->lch);
leafc oun t(bt->rch);
if((bt->lch==NULL) &&(bt->rch==NULL))
coun t++;
}
return(co unt);
void pai ntleaf(BiTree bt) // 输出叶结点 {if(bt!=NULL)
{if(bt->lch==NULL&&bt->rch==NULL)
prin tf("%3c",bt->data);
pain tleaf(bt->lch);
pain tleaf(bt->rch);
}
}
图11.2所示二叉树的输入数据顺序应该是： abd#g###ce#h##f##
图11.2 二叉树示意图
运行结果:
=================王采单
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 1
请输入二叉树各结点的编号和对应的值(如 1，a)： 1，a
TOC \o "1-5" \h \z 请继续输入二叉树各结点的编号和对应的值： 2， b
请继续输入二叉树各结点的编号和对应的值： 3，c
请继续输入二叉树各结点的编号和对应的值： 4,d
请继续输入二叉树各结点的编号和对应的值： 6，e
请继续输入二叉树各结点的编号和对应的值： 7，f
请继续输入二叉树各结点的编号和对应的值： 9，g
请继续输入二叉树各结点的编号和对应的值： 13，h
请继续输入二叉树各结点的编号和对应的值:
===================主菜单===================");
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 3
先序遍历二叉树：abdgcehf
===================主菜单===================");
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 4
中序遍历二叉树：
dgbaehcf
===================主菜单===================")；
建立二叉树方法 1
建立二叉树方法 2
先序递归遍历二叉树
中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 5
后序遍历二叉树：
gdbhefca
===================主菜单===================")；
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 6
层次遍历二叉树： 97 98 99100101102103104
===================主菜单===================")；
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 7
二叉树的高度为：4
”);王采单
”);
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 8
二叉树的叶子结点数为：3
二叉树的叶结点为： g h f
===================王采单
");
建立二叉树方法 1
建立二叉树方法 2
先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 9
交换二叉树的左右子树：
d
g
b
a
e
h
c
===================王采单
");
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 10
逆时针旋转90度输出的二叉树：
d
g
b
a
e
h
c
”);王采单
”);
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 2
请输入二叉树各结点值： abd#g###ce#h##f##
===================主菜单===================");
建立二叉树方法 1
建立二叉树方法 2
3?先序递归遍历二叉树
4?中序递归遍历二叉树
后序递归遍历二叉树
层次遍历二叉树
计算二叉树的高度
计算二叉树中叶结点个数
交换二叉树的左右子树
打印二叉树
0.结束程序运行
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 0
请按任意键继续 ?
六、 调试心得及收获
建立二叉树有两种方法：一种方法是利用二叉树的性质 5来建立二叉树；另一种 方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。建立后， 通过先序、中序、后序遍历，对二叉树有了进一步的理解与掌握。对二叉树中各 种计算也更了解了！
七、 其他所想到的一个二叉树，有许多部分构成，每一个部分都需要精心编写，才能对其进行操作， 不至于出错
Welcome To
Download !!!
欢迎您的下载，资料仅供参考！
相关热词搜索： 新版 实验 报告 二叉树