算法与数据结构实验报告二叉树实验报告.pdf

.
算法与数据结构实验报告

——二叉树

课程名称：算法与数据结构

实验项目名称：满二叉树的建立与遍历

实验时间：2014年11月29日

班级：电科1301姓名：侯炜学号：1402130126

实验目的：熟悉使用线性表结构，设计并理解多项式算法。

实验环境：VisualC++6.0，win7

实验步骤：

一．建立基本数据结构及程序架构

二．设计多项式各类操作的算法

三．调试程序，修改错误

四．总结得失

实验结果：成功使用中序输入建立二叉树并进行相应的遍历输出。

实验心得：

①队列结构作用之一：用于储存“临时数据”以便后续输出

②满二叉树是仅仅输入一次遍历顺序就得出结果的先决条件

；
.

具体实验步骤：

一．建立基本数据结构及程序架构

1.1数据结构

确定所需要的对二叉树进行抽象的数据类型：树节点。建立数据结构如下：
//----------------数据结构
typedefstructtreenode
{
chardata;
structtreenode*ltree;
structtreenode*rtree;
}Tnode;
//---------------
1.2主程序架构

建立了一个全局变量数组queue[]用作队列，函数指针fp用以调用操作函

数，scree[100]数组用以储存输入的字符串。主要函数声明如下：
//----------------------------

Tnode*finit(Tnode*tf,intflo);//中序建立
voidtransver(Tnode*tf,intflo,fpkf,intn);//层序遍历tf为树节点
flo为层数kf为回调函数n为标识层数：0为全部遍历其他n为输出第n层
voidordtra(Tnode*tf,fpkf,intflo);//先序遍历
voidfollow(Tnode*tf,fpkf,intflo);//后序遍历

Tnode*pus_pop(Tnode*tf,intk);//队列操作函数：k=0时为出队1为入队
intana(charsz[]);//分析二叉树层数
voidvisit(Tnode*k);//回调访问函数

intifpopcorn();//判断队列是否为空（未用）
voidinintque();///初始化队列
intflag(intn,inti);//层数显示标记
主函数阶段，循环显示主界面：建立多项式、多项式操作以及显示多项式。

【输入格式】：

建立二叉树：

二叉树数据：按中序遍历顺序输入（只支持满二叉树）
；
.

输出某一层：

输入层数，按回车即可。

二．设计算法

2.1建立二叉树

评价：处理scree存储的中序输入的字符串，

实现思想：以中序遍历的方法，递归建立。

代码如下：

Tnode*finit(Tnode*tf,intflo)//中序建立
{
if(!flo)returnNULL;

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);//递归
returntf;//返回树节点
}
2.2遍历算法

评价：利用递归算法遍历。

算法思想：递归。

实现代码如下：

voidordtra(Tnode*tf,fpkf,intflo)//先序遍历
{
//

if(!tf||!flo)return;

；
.

kf(tf);//回调函数（其实就是printf()）
ordtra(tf->ltree,visit,flo-1);
ordtra(tf->rtree,visit,flo-1);
}

voidfollow(Tnode*tf,fpkf,intflo)//后序遍历
{
//

if(!tf||!flo)return;
follow(tf->ltree,visit,flo-1);
follow(tf->rtree,visit,flo-1);
kf(tf);
return;
}
2.3层序遍历

评价：实现对每一层（或者指定层）进行遍历输出。

算法思想：建立一个队列，循环思想如下：在循环前将当头节点入队，进入

循环后，先出队一个，输出，同时判断左右子树是否存在，存在则分别入队，进

入下一次循环。这样下去，可以把每一层都输出。

同时会有一个i变量，用于判断循环边界以及是否输入某层。（形参n为显

示