算法与数据结构实验报告二叉树实验报告 本文关键词：实验，报告，数据结构，算法，二叉树
算法与数据结构实验报告二叉树实验报告 本文简介：算法与数据结构实验报告——二叉树课程名称：算法与数据结构实验项目名称：满二叉树的建立与遍历实验时间：2014年11月29日班级：电科1301姓名：侯炜学号：1402130126实验目的：熟悉使用线性表结构，设计并理解多项式算法。实验环境：VisualC++6.0，win7实验步骤：1．建立基本数据结
算法与数据结构实验报告二叉树实验报告 本文内容：
算法与数据结构实验报告
——二叉树
课程名称：算法与数据结构
实验项目名称：满二叉树的建立与遍历
实验时间：2014年11月29日
班级：电科1301姓名：侯炜
学号：1402130126
实验目的：熟悉使用线性表结构，设计并理解多项式算法。
实验环境：Visual
C++6.0，win7
实验步骤：
1．
建立基本数据结构及程序架构
2．
设计多项式各类操作的算法
3．
调试程序，修改错误
4．
总结得失
实验结果：成功使用中序输入建立二叉树并进行相应的遍历输出。
实验心得：
①
队列结构作用之一：用于储存“临时数据”以便后续输出
②
满二叉树是仅仅输入一次遍历顺序就得出结果的先决条件
具体实验步骤：
1．
建立基本数据结构及程序架构
1.1数据结构
确定所需要的对二叉树进行抽象的数据类型：树节点。建立数据结构如下：
//----------------数据结构
typedef
struct
treenode
{
char
data;
struct
treenode*
ltree;
struct
treenode*
rtree;
}Tnode;
//---------------
1.2主程序架构
建立了一个全局变量数组queue[]用作队列，函数指针fp用以调用操作函数，scree[100]数组用以储存输入的字符串。主要函数声明如下：
//----------------------------
Tnode*
finit(Tnode*tf,int
flo);//中序建立
void
transver(Tnode*
tf,int
flo,fp
kf,int
n);//层序遍历
tf为树节点
flo为层数
kf为回调函数
n为标识层数：0为全部遍历
其他n为输出第n层
void
ordtra(Tnode*
tf,fp
kf,int
flo);//先序遍历
void
follow(Tnode*
tf,fp
kf,int
flo);//后序遍历
Tnode*pus_pop(Tnode*tf,int
k);//队列操作函数：k=0时为出队
1为入队
int
ana(char
sz[]);//分析二叉树层数
void
visit(Tnode*k);//回调访问函数
int
ifpopcorn();//判断队列是否为空（未用）
void
inintque();///初始化队列
int
flag(int
n,int
i);//层数显示标记
主函数阶段，循环显示主界面：建立多项式、多项式操作以及显示多项式。
【输入格式】：
建立二叉树：
二叉树数据：按中序遍历顺序输入（只支持满二叉树）
输出某一层：
输入层数，按回车即可。
二．设计算法
2.1
建立二叉树
评价：
处理scree存储的中序输入的字符串，
实现思想：以中序遍历的方法，递归建立。
代码如下：
Tnode*
finit(Tnode*
tf,int
flo)//中序建立
{
if(!flo)return
NULL;
if(*scree==
/0
)return
NULL;
tf=(Tnode*)malloc(sizeof(Tnode));//为当前节点申请空间
tf->ltree=finit(tf->ltree,flo-1);//递归
中序是先左再中后右
tf->data=*printc;//赋值
printc为指向scree字符串（输入的中序序列）
printc++;//指针后移
tf->rtree=finit(tf->rtree,flo-1);//递归
return
tf;//返回树节点
}
2.2遍历算法
评价：利用递归算法遍历。
算法思想：递归。
实现代码如下：
void
ordtra(Tnode*
tf,fp
kf,int
flo)//先序遍历
{
//printf(“%c“,tf->data);
if(!tf||!flo)return;
kf(tf);//回调函数（其实就是printf()）
ordtra(tf->ltree,visit,flo-1);
ordtra(tf->rtree,visit,flo-1);
}
void
follow(Tnode*
tf,fp
kf,int
flo)//后序遍历
{
//printf(“%c“,tf->data);
if(!tf||!flo)return;
follow(tf->ltree,visit,flo-1);
follow(tf->rtree,visit,flo-1);
kf(tf);
return
;
}
2.3
层序遍历
评价：实现对每一层（或者指定层）进行遍历输出。
算法思想：建立一个队列，循环思想如下：在循环前将当头节点入队，进入循环后，先出队一个，输出，同时判断左右子树是否存在，存在则分别入队，进入下一次循环。这样下去，可以把每一层都输出。
同时会有一个i变量，用于判断循环边界以及是否输入某层。（形参n为显示层数参数，如果为0则全部输出，此外输出第n层）。
void
transver(Tnode*
tf,int
flo,fp
kf,int
n)
{
int
i=0;
if(!tf)return
NULL;
inintque();//初始化队列
pus_pop(tf,1);//树头入队
while(iltree)pus_pop(tf->ltree,1);//左子树存在的话就入队
if(tf->rtree)pus_pop(tf->rtree,1);//右子树存在的话就入队
}
printf(“/n“);
}
int
flag(int
n,int
i)
{
if(n==0)return
1;
if((pow(2,n-1)-1)=i)return
1;//在第n层范围内
return
0;
}
2.4
其他函数
2.4.1
队列的入队和出队函数
Tnode*pus_pop(Tnode*tf,int
k)
{
if(k)queue[pt++]=tf;//1入
else
if(pt>ph)return
queue[++ph];
}
2.4.2
访问函数
void
visit(Tnode*k)
{
printf(“%c
“,k->data);
}