数据结构实验43

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

2、的值，#表示空树3.访问二叉树中元素4.递归先序遍历5.递归中序遍历6.递归后序遍历7.主函数依次调用上述函数五、 测试结果对以下二叉树进行验证 A / B C / / D E F G 六、 分析与探讨1.用按先序遍历输入的方法输入的字符画出二叉树，看图依次按先序、中序、后序的方法写出遍历后的序列与测试结果对比可知正确。2.我在本实验中都是按递归的方法实现遍历，用栈操作也实现了非递归的遍历。七、 附录：源代码 #include<stdio.h>#include<stdlib.h>/ 函数结果状态代码#define TRUE 1#define FALSE 0#define

3、 OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 /因为在math.h中已定义OVERFLOW的值为3,故去掉此行#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 / 存储空间分配增量typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE/二叉树结点typedef struct BiTNode/数据ch

4、ar data;/左右孩子指针struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct SqStackBiTree *base; / 在栈构造之前和销毁之后，base的值为NULLBiTree *top; / 栈顶指针 */int stacksize; / 当前已分配的存储空间，以元素为单位SqStack; / 顺序栈/按先序序列创建二叉树int CreateBiTree(BiTree &T)char data;/按先序次序输入二叉树中结点的值（一个字符），#表示空树scanf("%c",&d

5、ata);if(data = '#')T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode);/生成根结点T->data = data;/构造左子树CreateBiTree(T->lchild);/构造右子树CreateBiTree(T->rchild);return 0;/输出void Visit(BiTree T)if(T->data != '#')printf("%c ",T->data);/先序遍历void PreOrder(BiTree T)if(T != NUL

6、L)/访问根节点Visit(T);/访问左子结点PreOrder(T->lchild);/访问右子结点PreOrder(T->rchild);/中序遍历 void InOrder(BiTree T) if(T != NULL) /访问左子结点 InOrder(T->lchild); /访问根节点 Visit(T); /访问右子结点 InOrder(T->rchild); /后序遍历void PostOrder(BiTree T)if(T != NULL)/访问左子结点PostOrder(T->lchild);/访问右子结点PostOrder(T->rchil

7、d);/访问根节点Visit(T);/栈的基本操作Status InitStack(SqStack &S) / 构造一个空栈SS.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!S.base)exit(-2); /* 存储分配失败 */S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S) /* 若栈S为空栈，则返回TRUE，否则返回FALSE */if(S.top=S.base)return TRUE;elseret

8、urn FALSE;Status GetTop(SqStack S,BiTree &e) /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */if(S.top>S.base)e=*(S.top-1);return OK;elsereturn ERROR;Status Push(SqStack &S,BiTree e) /* 插入元素e为新的栈顶元素 */if(S.top-S.base>=S.stacksize) /* 栈满，追加存储空间 */S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKI

9、NCREMENT)*sizeof(BiTree);if(!S.base)exit(-2); /* 存储分配失败 */S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,BiTree &e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */if(S.top=S.base)return ERROR;e=*-S.top;return OK; /* 先序遍历(非递归) 思路：访问T->data后，将T入栈，

10、遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。*/void PreOrder2(BiTree T)/p是遍历指针BiTree p = T;SqStack S;InitStack(S);/栈不空或者p不空时循环while(p | !StackEmpty(S)if(p != NULL)/存入栈中Push(S,p);/访问根节点printf("%c ",p->data);/遍历左子树p = p->lchild;else/退栈Pop(S,p);/访问右子树p = p->rchild;/while/* 中序遍历(非递归) 思路：T是要遍

11、历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。*/void InOrder2(BiTree T) SqStack S;/p是遍历指针BiTree p = T;InitStack(S);/栈不空或者p不空时循环while(p | !StackEmpty(S)if(p != NULL)/存入栈中Push(S,p);/遍历左子树p = p->lchild;else/退栈，访问根节点Pop(S,p);printf("%c ",p->da

12、ta);/访问右子树p = p->rchild;/while/*/后序遍历(非递归)typedef struct BiTNodePostBiTree biTree;char tag;BiTNodePost,*BiTreePost;void PostOrder2(BiTree T)stack<BiTreePost> stack;/p是遍历指针BiTree p = T;BiTreePost BT;/栈不空或者p不空时循环while(p != NULL | !stack.empty()/遍历左子树while(p != NULL)BT = (BiTreePost)malloc(siz

13、eof(BiTNodePost);BT->biTree = p;/访问过左子树BT->tag = 'L'stack.push(BT);p = p->lchild;/左右子树访问完毕访问根节点while(!stack.empty() && (stack.top()->tag = 'R')BT = stack.top();/退栈stack.pop();printf("%c ",BT->biTree->data);/遍历右子树if(!stack.empty()BT = stack.top();/访

14、问过右子树BT->tag = 'R'p = BT->biTree;p = p->rchild;/while/层次遍历void LevelOrder(BiTree T)BiTree p = T;/队列queue<BiTree> queue;/根节点入队queue.push(p);/队列不空循环while(!queue.empty()/对头元素出队p = queue.front();/访问p指向的结点printf("%c ",p->data);/退出队列queue.pop();/左子树不空，将左子树入队if(p->lch

15、ild != NULL)queue.push(p->lchild);/右子树不空，将右子树入队if(p->rchild != NULL)queue.push(p->rchild);*/int main()BiTree T;CreateBiTree(T);printf("先序遍历：n");PreOrder(T);printf("n");printf("先序遍历(非递归)：n");PreOrder2(T);printf("n");printf("中序遍历：n");InOrder(T);printf("n");printf("中序遍历(非递归)：n");InOrder2(T);printf("n");printf(&q