数据结构实验4-3.doc

《数据结构实验4-3.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告实验4二叉树遍历算法的设计与实现实验人：学号:时间：一、实验目的1.掌握二叉树的建立与存储2.掌握二叉树的遍历方法二、实验内容编写程序实现根据用户输入二叉树的先序序列建立一棵二叉树，并实现对此二叉树的先序、中序、和后序遍历。（算法6.4）三、实验步骤：1.接收用户输入的先序序列建立以二叉链表为存储结构的二叉树（算法6.4）。2.对建立好的二叉树实现先序、中序、和后序遍历，将遍历后的序列输出（参考算法6.1，6.3）。其中中序遍历包括递归和非递归算法实现，先序、后序遍历只要求递归算法

2、实现即可。四、算法说明1.二叉树的二叉链表存储表示（结构体）2.按先序次序输入二叉树中结点的值，#表示空树3.访问二叉树中元素4.递归先序遍历5.递归中序遍历6.递归后序遍历7.主函数依次调用上述函数五、测试结果对以下二叉树进行验证A/BC//DEFG数据结构实验报告一、分析与探讨1.用按先序遍历输入的方法输入的字符画出二叉树，看图依次按先序、中序、后序的方法写出遍历后的序列与测试结果对比可知正确。2.我在本实验中都是按递归的方法实现遍历，用栈操作也实现了非递归的遍历。二、附录：源代码#in

3、clude#include//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//因为在math.h中已定义OVERFLOW的值为3,故去掉此行#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefintStatus;//Stat

4、us是函数的类型,其值是函数结果状态代码，如OK等数据结构实验报告typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE//二叉树结点typedefstructBiTNode{//数据chardata;//左右孩子指针structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefstructSqStack{BiTree*base;//在栈构造之前和销毁之后，base的值为NULLBiTree*top;//栈顶指针*/

5、intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//顺序栈//按先序序列创建二叉树intCreateBiTree(BiTree&T){chardata;//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树scanf("%c",&data);if(data=='#'){T=NULL;}else{T=(BiTree)malloc(sizeof(BiTNode));//生成根结点T->data=data;数据结构实验报告//构造左子树CreateBiTree(

6、T->lchild);//构造右子树CreateBiTree(T->rchild);}return0;}//输出voidVisit(BiTreeT){if(T->data!='#'){printf("%c",T->data);}}//先序遍历voidPreOrder(BiTreeT){if(T!=NULL){//访问根节点Visit(T);//访问左子结点PreOrder(T->lchild);//访问右子结点PreOrder(T->rchild);}}//中序遍历voidInOrder(BiTr

7、eeT){if(T!=NULL){//访问左子结点InOrder(T->lchild);//访问根节点数据结构实验报告Visit(T);//访问右子结点InOrder(T->rchild);}}//后序遍历voidPostOrder(BiTreeT){if(T!=NULL){//访问左子结点PostOrder(T->lchild);//访问右子结点PostOrder(T->rchild);//访问根节点Visit(T);}}//栈的基本操作StatusInitStack(SqStack&S){//

8、构造一个空栈SS.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!S.base)exit(-2);/*存储分配失败*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusStackEmpty(SqStackS){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/数据结构实验报告if(S.top==S.base)returnTRUE;elseretur