数据结构实验2报告.doc
《数据结构实验2报告.doc》由会员分享，可在线阅读，更多相关《数据结构实验2报告.doc（8页珍藏版）》请在冰点文库上搜索。
任课教师：
孙树森
《数据结构与算法》
（2012-2013学年第2学期）
实
验
报
告
学号：
2011329700214
姓名：
周咪咪
班级：
11数字媒体技术
（2）班
实验2树的二叉链表表示及其遍历
实验目的：
掌握二叉树的链式存储结构及其遍历
实验重点：
二叉树的链式存储实现方法
实验内容：
用二叉链表存储结构表示下图所示二叉树的，并用递归方法输出三种遍历结果。
实验思路：
（1）
实验提示:
1,二叉树的链式存储结构表示
typedefstructBiTNode{
TElemTypedata;
structBitNode*lchild,*rchild;
}BiTNode,*BiTree;
2,二叉树的链式存储算法实现
CreateBiTree（&T,definition）;
InsertChild（T,p,LR,c）;
3,二叉树的递归法遍历
PreOrderTraverse（T,Visit（））;
InOrderTraverse（T,Visit（））;
PostOrderTraverse（T,Visit（））;
示例源程序
#include
#defineERROR0;
#defineOK1;
typedefintElemType;
typedefstructBinaryTree
{
ElemTypedata;
structBinaryTree*l;
structBinaryTree*r;
}*BiTree,BiNode;
BiNode*new（）
{
return（（BiNode*）malloc（sizeof（BiNode）））;
}
intCreateSubTree（BiTree*T,ElemType*all,inti）
{
if（（all[i]==0）||i>16）
{
*T=NULL;
returnOK;
}
*T=new（）;
if（*T==NULL）returnERROR;
（*T）->data=all[i];
CreateSubTree（&（（*T）->l）,all,2*i）;
CreateSubTree（&（（*T）->r）,all,2*i+1）;
}
intCreateBiTree（BiTree*T）
{
ElemTypeall[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree（T,all,1）;
}
voidprintelem（ElemTyped）//输出d的值
{
printf（"%d\n",d）;
}
intPreOrderTraverse（BiTreeT,int（*Visit）（ElemTyped））
{
if（T）{
if（Visit（T->data））
if（PreOrderTraverse（T->l,Visit））
if（PreOrderTraverse（T->r,Visit））returnOK;
returnERROR;
}
else
returnOK;
}
intmain（）
{
BiTreeroot;
CreateBiTree（&root）;
PreOrderTraverse（root,printelem）;
}
程序代码：
#include
#include
usingnamespacestd;
#defineERROR0;
#defineOK1;
typedefintElemType;
typedefstructBinaryTree//二叉树结点结构
{
ElemTypedata;
structBinaryTree*l;
structBinaryTree*r;
}*BiTree,BiNode;
intCreateSubTree（BiTree*T,ElemType*all,inti）//创建二叉树
{
if（（all[i]==0）||i>16）
{
*T=NULL;
returnOK;
}
*T=（BiNode*）malloc（sizeof（BiNode））;//动态分配结点空间
if（*T==NULL）returnERROR;
（*T）->data=all[i];
CreateSubTree（&（（*T）->l）,all,2*i）;
CreateSubTree（&（（*T）->r）,all,2*i+1）;
}
intCreateBiTree（BiTree*T）//初始化二叉树
{
ElemTypeall[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree（T,all,1）;
}
intprintelem（ElemTyped）//输出d的值
{
printf（"%d\n",d）;
return0;
}
intPreOrderTraverse（BiTreeT,int（*Visit）（ElemTyped））//先序遍历
{
if（T）{
if（Visit（T->data））
if（PreOrderTraverse（T->l,Visit））
if（PreOrderTraverse（T->r,Visit））returnOK;
returnERROR;
}
else
returnOK;
}
intInOrderTraverse（BiTreeT,int（*Visit）（ElemTyped））//中序遍历
{
if（T）{
if（PreOrderTraverse（T->l,Visit））
if（Visit（T->data））
if（PreOrderTraverse（T->r,Visit））returnOK;
returnERROR;
}
else
returnOK;
}
intPostOrderTraverse（BiTreeT,int（*Visit）（ElemTyped））//后序遍历
{
if（T）{
if（PreOrderTraverse（T->l,Visit））
if（PreOrderTraverse（T->r,Visit））
if（Visit（T->data））returnOK;
returnERROR;
}
else
returnOK;
}
intmain（）
{
intn;
BiTreeroot;
CreateBiTree（&root）;
printf（"先序遍历结果：
"）;
PreOrderTraverse（root,printelem）;
printf（"中序遍历结果：
"）;
InOrderTraverse（root,printelem）;
printf（"后序遍历结果：
"）;
PostOrderTraverse（root,printelem）;
scanf（"%d",&n）;
return1;
}
#include
#include
usingnamespacestd;
#defineERROR0;
#defineOK1;
typedefstructBiNode{
intdata;
structBiNode*lchild,*rchild;
}BiNode,*BiTree;
intn=0;
inti;
intCreateBiTree（BiTree*T）
{
inta[100];
intm=0;
printf（"请输入总结点数量:
"）;
cin>>m;
for（i=0;i printf（"请输入结点的值，表示空结点，表示结束\n"）;
i=0;
while（i=999）
{
cin>>n;
a[i]=n;
i++;
}
for（i=0;i<100;i++）{
if（a[i]==0）{
T=NULL;
return0;
}
else{
if（!
（*T=（BiNode*）malloc（sizeof（BiNode））））return0;
（*T）->data=a[i];
CreateBiTree（&（（*T）->lchild））;
CreateBiTree（&（（*T）->rchild））;
}
}
return1;
}
intPreOrderTraverse（BiTreeT）
{
if（T==NULL）return0;
printf（"%d",T->data）;
PreOrderTraverse（T->lchild）;
PreOrderTraverse（T->rchild）;
return1;
}
intmain（）
{
BiTreeroot;
CreateBiTree（&root）;
PreOrderTraverse（root）;
intn;
scanf（"%d",&n）;
}
一、程序源码：
1、方法1：
2、方法2：
二、运行结果与测试分析：
1、方法1：
2、方法2：
七、实验心得与体会：
升级会员 