二叉树遍历报告

《二叉树遍历报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程实习报告题目：二叉树遍历学生姓名：学生学号：专业班级:一、需求分析按某条搜索路径巡访树中每个节点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都有可能有两棵子树。需耍寻找一种规律,以便二叉树上的结点能排列在一个线性队列上，从而便于遍历。所以有三种遍历的方法：先序遍历：先访问根节点；先序遍历左了树；先序遍历右子树。屮序遍历：中序遍历左了树；访问根节点；中序遍历右子树。后序遍历：后序遍历左子树；后序遍历右子树；访问根节点。二、概要设计typedefstructBiTNode{//二叉树结点结构chardata;//结点数据structBiTNode*

2、lchild;//■一左孩了structBiTNode*rchild;//——右孩子}BiTNode,*BiTrcc;BiTreeCreateBiTree(BiTreeT)——构造二叉树StatusInitStack(SqStack*S)构造一个空栈StatusDestroyStack(SqStack*S)-■■一销毁栈……StatusClcarStack(SqStack*S)把栈置为空栈StatusStackEmpty(SqStackS)判断是否为空栈intStackLength(SqStackS)返回栈的长度StatusGetTop(SqStackS,SElemType*e)若栈不

3、空，则川e返回S的栈顶元素，并返回OK；否则返回ERRORStatusPush(SqStack*S,SElcmTypcc)在栈顶插入元索StatusPop(SqStack*S,SElemType*e)-…删除栈顶元素StatusVisit(ElemTypee)对二叉树中的数据元素访问StatusPreOrderTraverse1(BiTreeT,Status(*Visit)(ElemTypee))递归的先序遍历StatusInOrderTraverse1(BiTreeT,Status(*Visit)(ElemTypee))递归中序遍历StatusPostOrderTraverseI(B

4、iTreeT,Status(*Visit)(ElemTypee))递归后序遍丿力StatusPreOrderTraverse2(BiTreeT,Status(*Visit)(ElemTypee))非递归先序遍历StatusInOrderTraverse2(BiTreeT,Status(*Visit)(ElemTypee))-…非递归中序遍历StatusPostOrderTraverse2(BiTreeT,Status(*Visit)(ElemTypee))非递归后序遍历三、详细设计预测输出结果:先序遍历：-+a*b・cd/ef111序遍历:a+b*c-d-e/f四、调试分析在调试过程中

5、有时候经常出现输入了结点可是不出结果的现象，需要我们去看构建二叉树的时候的输入是否有错，如果实在不行就需耍我们更进一步去观察是否有错误。在做非递归的时候要注意函数的调用，首先要将写建栈等函数。有时候遍历会出错，导致遍历的次序会出现错误。如果是这样出现那么出现问题可能的地方就比较多，如递归的遍丿力次序出错等。需耍我们去调试。五、测试结果exeW?卞新数据结构逐结构报告晨后葩报gDebug]先中唐归归ynA、Ta、TA弟爲爲IklrlFEL、I-I•一二一二一二P333历历历list第中后Pressanykeytocontinue六、实验心得在最开始的时候做递归的二叉树比较简便，比较

6、容易理解，很快的就能完成。让我更深的理解了二叉树的三种遍历方法，和递归算法。不管是根据二叉树写出先序遍历，中序遍历，还是写出后序遍历都能正确的写出来。在做非递归的时候就比较麻烦了，需要让我们去看更多的资料，來让我理解非递归的算法。很多抽象数据类型的定义都要去查找资料才能写得出來。让我对函数的调川有了更进一步的巩固。而且通过此次实验讣我加深了对栈的理解不管是出栈，入栈等。所以此次实验收获颇丰。七、附录#include#includc#defineOK1#defineERROR0#defineOVERFLOW-1#defineSTACK_INIT_SI

7、ZE100#dcfincSTACKINCREMENT10typedefintStatus;typedefcharElemType;//二叉树结点元索类型typedefstructBiTNode{//二叉树结点结构chardata;//结点数据structBiTNode*lchild;//—-左孩子structBiTNode*rchild;//右孩了}BiTNode,*BiTree;typedefBiTrccSElcmTypc;typedefst