资源描述：
《算法与数据结构实验报告二叉树实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、算法与数据结构实验报告——二叉树课程名称：算法与数据结构实验项目名称：满二叉树的建立与遍历实验时间：2014年11月29日班级：电科1301姓名：侯炜学号：1402130126实验目的：熟悉使用线性表结构，设计并理解多项式算法。实验环境：VisualC++6.0，win7实验步骤：一．建立基本数据结构及程序架构二．设计多项式各类操作的算法三．调试程序，修改错误四．总结得失实验结果：成功使用中序输入建立二叉树并进行相应的遍历输出。实验心得：①队列结构作用之一：用于储存“临时数据”以便后续输出②满二叉树是仅仅输入一次遍历顺序就得出结果的先决条件具体实验步骤：
2、一．建立基本数据结构及程序架构1.1数据结构确定所需要的对二叉树进行抽象的数据类型：树节点。建立数据结构如下：//----------------数据结构typedefstructtreenode{chardata;structtreenode*ltree;structtreenode*rtree;}Tnode;//---------------1.2主程序架构建立了一个全局变量数组queue[]用作队列，函数指针fp用以调用操作函数，scree[100]数组用以储存输入的字符串。主要函数声明如下：//--------------------------
3、--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[]);//分析二叉树层数voi
4、dvisit(Tnode*k);//回调访问函数intifpopcorn();//判断队列是否为空（未用）voidinintque();///初始化队列intflag(intn,inti);//层数显示标记主函数阶段，循环显示主界面：建立多项式、多项式操作以及显示多项式。【输入格式】：建立二叉树：二叉树数据：按中序遍历顺序输入（只支持满二叉树）输出某一层：输入层数，按回车即可。二．设计算法2.1建立二叉树评价：处理scree存储的中序输入的字符串，实现思想：以中序遍历的方法，递归建立。代码如下：Tnode*finit(Tnode*tf,intflo)//
5、中序建立{if(!flo)returnNULL;if(*scree==' ')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遍历算法评价：利用递归算法遍历。算法思想
6、：递归。实现代码如下：voidordtra(Tnode*tf,fpkf,intflo)//先序遍历{//printf("%c",tf->data);if(!tf
7、
8、!flo)return;kf(tf);//回调函数（其实就是printf()）ordtra(tf->ltree,visit,flo-1);ordtra(tf->rtree,visit,flo-1);}voidfollow(Tnode*tf,fpkf,intflo)//后序遍历{//printf("%c",tf->data);if(!tf
9、
10、!flo)return;follow(tf->ltre
11、e,visit,flo-1);follow(tf->rtree,visit,flo-1);kf(tf);return;}2.3层序遍历评价：实现对每一层（或者指定层）进行遍历输出。算法思想：建立一个队列，循环思想如下：在循环前将当头节点入队，进入循环后，先出队一个，输出，同时判断左右子树是否存在，存在则分别入队，进入下一次循环。这样下去，可以把每一层都输出。同时会有一个i变量，用于判断循环边界以及是否输入某层。（形参n为显示层数参数，如果为0则全部输出，此外输出第n层）。voidtransver(Tnode*tf,intflo,fpkf,intn){in
12、ti=0;if(!tf)returnNULL;inintque();//初始化队
