DS5树型结构.docx
《DS5树型结构.docx》由会员分享，可在线阅读，更多相关《DS5树型结构.docx（9页珍藏版）》请在冰点文库上搜索。
DS5树型结构
《数据结构与算法分析》
课程实验报告
项目名称：
树结构的操作
学生姓名：
学生学号：
指导教师：
完成日期：
2014．12．5
【实验目的】
1.理解树形结构的逻辑和存储特点。
2.掌握二叉树的遍历递归算法。
【实验内容】
1.用递归算法实现二叉树的建立，并能输出遍历序列结果（先序、中序、后序任意一种即可）
2.完成二叉树的应用：
统计叶子结点数目，输出叶子结点，求二叉树深度，交换每个结点的左右子树，统计树的结点总个数。
（任选其中两个）
【实验方式】
个人实验。
【实验设备与环境】
PC机，WindowsXP操作系统，VC++6.0开发环境。
【数据结构及函数定义】
（1）主函数main（）实现初始化操作，完成对子函数的调用
（2）子函数
BiTree*CreateBiTree（BiTree*T）创建二叉树StatusDepthBiTree（BiTree*T）求深度
Statuscountleaf（BiTree*T）计算叶子结点个数voidpreorder（BiTree*T）先序遍历
voidInorder（BiTree*T）中序遍历voidPostorder（BiTree*T）后序遍历
voidchange_left_right（BiTree*T）交换左右孩子
【测试数据与实验结果】
输入先序序列的数据：
ABC##DE#G##F###
【源程序清单】
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#definenull0
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;
#defineSTACKINCREMENT10
typedefintStatus;
typedefintTElemType;
typedefstructBiTNode
{
chardata;
structBiTNode*lchild;
structBiTNode*rchild;
}BiTree;//-----------------------------------创建二叉树
BiTree*CreateBiTree（BiTree*T）
{
charch;
if（（ch=getchar（））=='#'）T=NULL;
else
{
T=（BiTree*）malloc（sizeof（BiTNode））;
T->data=ch;
T->lchild=CreateBiTree（T->lchild）;
T->rchild=CreateBiTree（T->rchild）;
}
returnT;
}//------------------------------查找结点
/*StatussearchBiTree（BiTree*T,TElemTypex）
{BiTree*bt;
if（T!
=NULL）
{
if（bt->data==x）
printf（"你查找的叶子结点存在于二叉树中）;
returnOK;
searchBiTree（T->lchild,x）;
searchBiTree（T->rchild,x）;
}
else
printf（"%d不在该树种,x）;
returnNULL;
}*///------------------------------求深度
StatusDepthBiTree（BiTree*T）
{
intdepthval,depthLeft,depthRight;
if（!
T）depthval=0;
else
{
depthLeft=DepthBiTree（T->lchild）;
depthRight=DepthBiTree（T->rchild）;
depthval=1+（depthLeft>depthRight?
depthLeft:
depthRight）;
}
returndepthval;
}//----------------------------计算叶子结点个数
Statuscountleaf（BiTree*T）
{
intnum1;
intnum2;
intnum;
if（T==NULL）num=0;
else
if（（T->lchild==NULL）&&（T->rchild==NULL））num=1;
else
{
num1=countleaf（T->lchild）;
num2=countleaf（T->rchild）;
num=num1+num2;
}
returnnum;}//先序遍历二叉树
voidpreorder（BiTree*T）
{
if（T!
=NULL）
{
printf（"%2c",T->data）;
preorder（T->lchild）;
preorder（T->rchild）;
}}//中序遍历二叉树
voidInorder（BiTree*T）
{
structBiTNode*p;
structBiTNode*stack[20];
inttop=0;
p=T;
while（p||top!
=0）{
while（p）
{
stack[top++]=p;
p=p->lchild;}
p=stack[--top];
printf（"%c",p->data）;
p=p->rchild;
}}//后序遍历二叉树
voidPostorder（BiTree*T）
{
if（T!
=NULL）
{
Postorder（T->lchild）;
Postorder（T->rchild）;
printf（"%2c",T->data）;
}
}//------------------------交换左右孩子
voidchange_left_right（BiTree*T）
{
BiTree*temp;
if（T）
{
change_left_right（T->lchild）;
change_left_right（T->rchild）;
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
}}
intmain（）
{
inti,j;
BiTree*bt;
printf（"请用先序序列输入数据:
\n"）;
bt=NULL;
bt=CreateBiTree（bt）;//andhere
printf（"先序遍历的结果：
"）;
preorder（bt）;
printf（"\n\n"）;
printf（"中序遍历的结果：
"）;
Inorder（bt）;
printf（"\n\n"）;
printf（"后序遍历的结果：
"）;
Postorder（bt）;
printf（"\n\n"）;
printf（"叶子结点的总个数：
n="）;
i=countleaf（bt）;
printf（"%d",i）;
printf（"\n\n"）;
printf（"该二叉树的深度:
h="）;
j=DepthBiTree（bt）;
printf（"%d",j）;
printf（"\n\n"）;
printf（"交换左右孩子的结果如下：
"）;
change_left_right（bt）;
printf（"先序遍历的结果：
"）;
preorder（bt）;
printf（"\n\n"）;
printf（"中序遍历的结果：
"）;
Inorder（bt）;
printf（"\n\n"）;
printf（"后序遍历的结果：
"）;
Postorder（bt）;
printf（"\n\n"）;
printf（"叶子结点的总个数:
n="）;
i=countleaf（bt）;
printf（"%d",i）;
printf（"\n\n"）;
printf（"该二叉树的深度:
h="）;
j=DepthBiTree（bt）;
printf（"%d",j）;
printf（"\n\n"）;
return0;
}
升级会员 