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

算法与数据结构实验报告二叉树课程名称：算法与数据结构实验项目名称：满二叉树的建立与遍历实验时间：2014年11月29日班级：电科1301姓名：侯炜 学号：1402130126实验目的：熟悉使用线性表结构，设计并理解多项式算法。实验环境：Visual C+6.0，win7实验步骤：1 建立基本数据结构及程序架构2 设计多项式各类操作的算法3 调试程序，修改错误4 总结得失实验结果：成功使用中序输入建立二叉树并进行相应的遍历输出。实验心得： 队列结构作用之一：用于储存“临时数据”以便后续输出 满二叉树是仅仅输入一次遍历顺序就得出结果的先决条件具体实验步骤：1 建立基本数据结构及程序架构1.1数据结构确定所需要的对二叉树进行抽象的数据类型：树节点。建立数据结构如下：/-数据结构typedef struct treenodechar data;struct treenode* ltree;struct treenode* rtree;Tnode;/-1.2主程序架构建立了一个全局变量数组queue用作队列，函数指针fp用以调用操作函数，scree100数组用以储存输入的字符串。主要函数声明如下：/-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_po