数据结构_二叉树遍历实现

数据结构实验课程名称数据结构实验题目名称二叉树的遍历实现学生学院应用数学学院专业班级信息计算1班学号3114008104学生姓名陈辉腾指导教师刘志煌2016年6月3日二叉树遍历实现14信计1班—陈辉腾—3114008104实验目的：实现二叉树的基本遍历（先序，中序和后序），通过本实验可以加深对二叉树、对递归、对堆栈，对指针的了解，以及对算法的比较和代码规范化的学习。(详细思路写在程序注释里面)首先先序构造一颗树：代码实现及思路如下：构造如下一棵树，代码运行结果如下：构造的树：构造了一颗二叉树，然后就对其进行各种遍历操作。先对其递归遍历实现：abcdef中序和后序和先序是同样的道理：运行结果如下：接着对其非递归递归遍历实现：非递归遍历要用到栈，自己有写栈的各种操作。另外，我发现可以用C++库里面人家写好的，include进来就可以直接调用，以下代码有些是用自己写的栈，有些是用C++库里面的（感觉别人写的很好用，比如调试的时候查看栈内元素就比自己写的简单明了）。思路都写在代码的注释里面面，个人觉得这样好看些，截图放入word文档就省去排版了，更方便理解。先序非递归：先序非递归运行结果：中序非递归1：（中序非递归写了两种算法，都是实现书本上的。）中序非递归1运行结果：中序非递归2：中序非递归2运行结果：后序非递归也写了两种算法，一种是用标识访问次数来确定右子树是否被访问的，访问次数标识变量定义结构体里面。另一种就是经典的双栈法。后序非递归1：后序非递归1运行结果：后序非递归2（双栈）：后序非递归2（双栈）运行结果：总结：二叉树的本质是递归定义的二叉链表，对树的操作往往离不开递归，递归形式上看起来简单明了，调用起来却是层层嵌套，而且递归调用要保存很多信息，这些信息也应该是用栈来保存的，另外，递归调用会占用较多的CPU资源，效率不高。于是，我们考虑使用非递归的形式来对树进行操作，而非递归的算法却不太好理解，可能对于我来说不确定的因素太多了吧，要自己想还真想不出来。一开始，算法也看不太懂，特别是后序非递归比较难，本身对c语言，对指针就不是特别理解，于是只能跟着程序来调试，并参考别人写的，慢慢的才理解。个人觉得后序非递归算法用双栈法比较高大上，因为不仅充分运用数据结构的栈，还能和先序非递归进行对比，简直是经典算法。另外，做实验的时候也遇到了许多困难，感觉对指针怕怕的，还好后来经过同学间的讨论，以及丰富的网上资源把困难摆平了。而看非递归算法也是有一种好像自己所有精力都会耗尽在里面，而自己对算法本质的理解还是不透彻的感觉。总的来说，做完这个实验，也感觉自己在算法方面，编码方面有一定的收获。附录：（代码）头文件：#includestdlib.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR-1#defineOVERFLOW-2#defineSTACK_INIT_SIZE100#defineSTACK_INCREMENT10typedefintStatus;typedefcharElemType;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针intvisitCount;//访问次数(后序遍历会用到)}BiTNode,*BiTree;typedefstruct{BiTNode*base;BiTNode*top;intstacksize;}SqStack;Statusvisit(ElemTypeelem){printf(%c,elem);returnOK;}StatusInitStack(SqStack&S){S.base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusPush(SqStack&S,BiTNode*p){if(S.top-S.base=STACK_INIT_SIZE){S.base=(BiTNode*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(BiTNode));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACK_INCREMENT;}*S.top=*p;S.top=S.top+1;returnOK;}StatusPop(SqStack&S,BiTNode*&p){if(S.base==S.top)returnERROR;S.top=S.top-1;p=S.top;returnOK;}StatusGetTop(SqStackS,BiTNode*p){if(S.base==S.top)returnERROR;*p=*(S.top-1);returnOK;}StatusStackEmpty(SqStackS){if(S.base==S.top)returnTRUE;returnFALSE;}StatusStackLength(SqStackS){returnS.top-S.base;}StatusCreateBiTree(BiTree&T){//T带上&符，做返回值。charch;scanf(%c,&ch);//输入一个字符保存在变量ch里面if(ch=='')//如果输入的是空格，则代表空（子）树T=NULL;else{//否则，分配一个节点大小的空间，并让T指向它。T=(BiTNode*)malloc(sizeof(structBiTNode));if(!T)exit(OVERFLOW);//若空间分配失败，直接退出。T-data=ch;//否则把输入的字符赋到节点结构体的data域CreateBiTree(T-lchild);//递归构造左子树CreateBiTree(T-rchild);//递归构造左子树}returnOK;}源文件：#includestdio.h#includestack#includeBiTree.husingnamespacestd;//先序递归算法StatusPreOrderTraverse(BiTreeT,Status(*visit)(ElemTypeelem)){//按照书本的伪代码转换成可运行的C/C++代码。if(T){//如果不是空树，则进行遍历if(visit(T-data))//先序则先遍历根节点，然后分别遍历左右子树if(PreOrderTraverse(T-lchild,visit))//左if(PreOrderTraverse(T-rchild,visit))//右returnOK;returnERROR;}else{returnOK;}}//中序递归算法StatusInOrderTraverse(BiTreeT,Status(*visit)(ElemTypeelem)){if(T){if(InOrderTraverse(T-lchild,visit))if(visit(T-data))if(InOrderTraverse(T-rchild,visit))returnOK;returnERROR;}else{returnOK;}}//后序递归算法StatusPostOrderTraverse(BiTreeT,Status(*visit)(ElemTypeelem)){if(T){if(PostOrderTraverse(T-lchild,visit))if(PostOrderTraverse(T-rchild,visit))if(visit(T-data))returnOK;returnERROR;}else{returnOK;}}//先序遍历--非递归StatusPreOrder1(BiTreeT,Status(*visit)(ElemTypeelem)){BiTreestack[STACK_INIT_SIZE],p;inttop=-1;if(T){top++;//根节点进栈.stack[top]=T;while(top-1){//栈不空时循环p=stack[top];//退栈并访问该节点top--;if(!visit(p-data))returnERROR;if(p-rchild){top++;//右孩子进栈stack[top]=p-rchild;}if(p-lchild){top++;//左孩子进栈stack[top]=p-lchild;}}}returnOK;}//先序遍历--非递归StatusPreOrder(BiTreeT,Status(*visit)(ElemTypeelem)){//采用C++库里面的栈，#includestack,usingnamespacestd;stackBiTreeS;//把T保存下来（赋给p），因为一次遍历后T就不一定指向根节点了，而下次//其他遍历就不能对同一颗构造的树进行遍历，即为了T的复用。BiTreep=T;if(T){//不是空树就进行遍历S.push(p);//先让根节点进栈while(!S.empty()){//栈不空时进行循环p=S.top();//取得栈顶元素赋给指针变量pS.pop();//退栈，一出栈便要访问之if(!visit(p-data))returnERROR;//访问已出栈的元素，//若有右孩子，则先让右孩子压栈，因为访问左孩子要在右孩子之前，根据栈是先进后//出和以上先出栈先访问（一出栈便访问）的规定，所以右孩子要被压在左孩子下面。if(p-rchild)S.push(p-rchild);if(p-lchild)S.push(p-lchild);//左孩子后进栈}}returnOK;}//中序遍历--非递归StatusInOrder(BiTreeT,Status(*visit)(ElemTypeelem)){//采用自己写的栈的各种操作。根据书本的伪码，转化成可运行的C语言代码对T进行中序遍历SqStackS;InitStack(S);//初始化一个栈SBiTreeb=T;while(b||!StackEmpty(S)){if(b){//若b不空，根指针进栈，左子树进栈Push(S,b);b=b-lchild;}else{Pop(S,b);//根指针退栈，访问根节点，遍历右子树//访问节点b是在节点b的左子树为空或者右子树为空时访问，即if(b)不成立时，在这种情况//下，要不就是左子树为空，要不就是左子树被访问完了，此时应访问根节点并转向右子树。if(!visit(b-data))returnERROR;b=b-rchild;}}returnOK;}//后序遍历--非递归StatusPostOrder(BiTNode*b,Status(*visit)(ElemTypeelem)){BiTNode*stack[STACK_INIT_SIZE];BiTNode*p;intflag,top=-1;if(b!=NULL){do{while(b!=NULL){//将b的所有左子树进栈top++;stack[top]=b;b=b-lchild;}p=NULL;//p用来指向当前节点的前一个已访问的节点flag=1;while(top!=-1&&flag){b=stack[top];//取出当前栈顶元素if(b-rchild==p){//右子树不存在或已被访问，访问根节点if(!visit(b-data))returnERROR;top--;p=b;//p指向已被访问的节点}else{b=b-rchild;//flag=0;}}}while(top!=-1);}returnOK;}//后序遍历--非递归StatusPo