二叉树的建立和遍历的实验报告

#14(实验类型：验证型)1)问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…建立树2…前序遍历树3…中序遍历树4…后序遍历树5…求二叉树的高度6…求二叉树的叶子节点7…非递归中序遍历树0…结束实验要求：在程序中定义下述函数，并实现要求的函数功能：createbinTree(binTreestructnode*lchild,*rchild;}binTnode;元素类型：intcreatebinTree(binTreevoidpreorder(binTreevoidlnorder(binTreevoidpostorder(binTreevoidlnordern(binTreeintleaf(binTreeintpostTreeDepth(binTree2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。1)问题描述：实现二叉树的非递归中序遍历和求二叉树高度2)实验要求：以二叉链表作为存储结构实现过程：1、实现非递归中序遍历代码：voidcbiTree::lnordern(binTreeinttop=0;p=T;do{while(p!=nuLL){stack[top]=p;;top=top+1;p=p->lchild;};if(top>0){top=top-1;p=stack[top];printf("%3c",p->data);p=p->rchild;}}while(p!=nuLL||top!=0);}2、求二叉树高度：intcbiTree::postTreeDepth(binTreeif(T!=nuLL){l=postTreeDepth(T->lchild);r=postTreeDepth(T->rchild);max=l>r?l:r;return(max+1);}elsereturn(O);}实验步骤：1)新建一个基于consoleApplication的工程，工程名称biTreeTest；2)新建一个类cbiTree二叉树类。3)在类cbiTree的头文件上方定义二叉链表存储数据类型结构体biTnode。4)在类cbiTree中定义函数createbinTree()；preorder()；Inorder()；postorder();postTreeDepth();lnordern()；实现函数createbinTree();preorder();lnorder()；postorder();postTreeDepth();Inordern()；在主函数中定义对象，通过对象调用函数，实现各个函数的操作。运行结果:篇二：数据结构实验报告-二叉树的实现与遍历《数据结构》第六次实验报告学生姓名学生班级学生学号指导老师重庆邮电大学计算机学院一、实验内容1）采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。2）输出树的深度，最大元，最小元。二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1,表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。三、详细设计源代码：#include#definemAx100〃表示栈的最大容量#defineFuLL99〃表示栈满#defineempTY-1〃表示栈空typedefstructTnode//定义结点{定义chardata;//存储结点数据structTnode*left;〃结点左子指针structTnode*right;〃定义右子指针定义}Tnode,*pnode;〃声明Tnode类型的变量和指针typedefstructstack//定义栈{pnodepnode[mAx];〃存放数据intp;//栈顶指针}stack,*pstack;〃定义stack类型的变量和指针voidpush(pstackpstack,pnodepnode)〃入栈{}pnodepop(pstackpstack)//出栈{}pnodeTop(pstackpstack)//看栈顶元素{}intlsempty(pstackpstack)//栈判空{}intlsfull(pstackpstack)//栈满{}voidlnitstack(pstackpstack)//初始化栈if(pstack->p==FuLL)elsereturnO;return1;if(pstack->p==empTY)elsereturnO;;return1;returnpstack->pnode[pstack->p];returnpstack->pnode[pstack->p--];pstack->p++;pstack->pnode[pstack->p]=pnode