用递归、非递归两种方法遍历二叉树

1、用递归、非递归两种方法遍历二叉树一、设计思想二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。递归算法：1 先序遍历： 先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。2. 中序遍历： 中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再

2、将右子作为参数进行判断，打印右子，直至结束。3. 后序遍历： 指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。非递归算法：1. 先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则

3、当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。2.中序遍历：首先建立一个栈，首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，出栈一个元素，作为当前结点，打印该结点，然后将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。3.后续遍历： 首先从根节点

4、开始遍历，看根节点是否为空，如果根节点不为空，将根节点的元素压入栈中，继续遍历，如果根节点有左子，索引移动到左子，并以左子为根节点继续遍历。如果左子不为空，则索引移动到左子并入栈；如果左子为空，索引移动到栈顶元素所在的节点，如果此节点的右子不为空并且右子没有被访问过，则索引移动到右子，否则访问栈顶元素并输出，并且定义此节点为被访问过得节点，栈顶元素出栈，树节点定义为NULL，继续遍历。二、算法流程图递归算法：创建二叉树调用自身调用对应函数输出结果图1 递归算法流程图先序非递归遍历：得到根节点输出当前节点当前节点的元素入栈，当前节点移动到左子上判断当前节点是否存在左子存在存在不存在当前节点是否存

5、在右子当前节点跳到右子上 不存在结束出栈，当前节点为出栈元素栈是否为空为空不为空图2 先序遍历的非递归算法流程图中序非递归遍历：得到根节点栈是否为空出栈，当前节点为出栈元素结束 判断当前节点是否存在右子当前节点的元素入栈，当前节点移动到左子上当前节点跳到右子上判断当前节点是否存在左子输出当前节点存在不存在存在不存在不为空为空图3 中序遍历的非递归算法流程图后序非递归遍历：得到根节点判断当前节点是否存在左子存在当前节点的元素入栈，当前节点移动到左子上不存在 判断当前节点是否存在右子存在当前节点跳到右子上不存在输出当前节点出栈，当前节点为出栈元素为空不为空结束栈是否为空图4 后序遍历的非递归算法流

6、程图三、源代码前序非递归#include<stdio.h>struct element /用结构体构建二叉树元素 struct element * lchild;int data;struct element * rchild;int main()int i=1;struct element * stack30;struct element a,b,c,d,e; /构建二叉树a.data=1; b.data=2; c.data=3; d.data=4; e.data=5;a.lchild=&b; a.rchild=&c; b.lchild=&d; b.rch

7、ild=&e; c.lchild=0; c.rchild=0; d.lchild=0; d.rchild=0; e.lchild=0; e.rchild=0; stacki=&a; while(i!=0) / 用数组逐个处理二叉树的元素 while(stacki!=0) /取左子树直至为空 printf("%dn",(*(stacki).data); /访问元素的数据部分i+;stacki=(*(stacki-1).lchild; i-; /去掉空元素 if(i!=0) stacki=(*(stacki).rchild; /取右子树 getch();中序非递

8、归#include<stdio.h>struct element /用结构体构建二叉树元素 struct element * lchild;int data;struct element * rchild;int main()int i=1;struct element * stack30;struct element a,b,c,d,e; /构建二叉树 a.data=1; b.data=2; c.data=3; d.data=4; e.data=5;a.lchild=&b; a.rchild=&c; b.lchild=&d; b.rchild=&e

9、; c.lchild=0; c.rchild=0; d.lchild=0; d.rchild=0; e.lchild=0; e.rchild=0; stacki=&a; while(i!=0) / 用数组逐个处理二叉树的元素 while(stacki!=0) i+; stacki=(*(stacki-1).lchild; /取左子树直至为空 i-;/去掉空元素 if(i!=0) printf("%dn",(*(stacki).data); /访问元素的数据部分 stacki=(*(stacki).rchild; /取右子树 getch();后序非递归#include

10、<stdio.h>struct element /用结构体构建二叉树元素 struct element * lchild;int data;struct element * rchild;int main()int i=-1,j=-1;int tag 20;struct element * p;struct element stack30;struct element a,b,c,d,e; /构建二叉树 a.data=1; b.data=2; c.data=3; d.data=4; e.data=5;a.lchild=&b; a.rchild=&c; b.lchil

11、d=&d; b.rchild=&e; c.lchild=0; c.rchild=0; d.lchild=0; d.rchild=0; e.lchild=0; e.rchild=0; p=&a; while(p!=0 | j!=-1) /元素非空或没有遍历完全部节点就不结束 while(p) /当p指向的节点存在时，将其压入栈中，把0压入标志栈中 /并将p指向其左子树 stack+i=*p; tag+j=0; p=(*p).lchild; if(j>-1) if(tagj=1) /当有右子树访问标志时，访问当前节点的数据 printf("%dn"

12、,stacki.data); i-; j-; else /没有右子树访问标志时，取得当前节点的的右子树 /并将右子树访问标志置1 p=stacki.rchild; tagj=1; getch();前序递归#include<stdio.h>struct element /用结构体构建二叉树的元素 struct element * lchild;int data;struct element * rchild;int main()struct element a,b,c,d,e;int preRev(struct element e); /声明处理二叉树元素的递归方函数 /构建二叉树

13、a.data=1; b.data=2; c.data=3; d.data=4; e.data=5;a.lchild=&b; a.rchild=&c; b.lchild=&d; b.rchild=&e; c.lchild=0; c.rchild=0; d.lchild=0; d.rchild=0; e.lchild=0; e.rchild=0;preRev(a);/调用递归函数对二叉树元素进行逐个处理 getch();int preRev(struct element e) /定义递归函数 printf("%dn",e.data);if(e.l

14、child) preRev(*e.lchild); if(e.rchild) preRev(*e.rchild);中序递归#include<stdio.h>struct element /用结构体构建二叉树的元素struct element * lchild;int data;struct element * rchild;int main()struct element a,b,c,d,e;int preRev(struct element e); /声明处理二叉树元素的递归方函数 /构建二叉树 a.data=1; b.data=2; c.data=3; d.data=4; e.

15、data=5;a.lchild=&b; a.rchild=&c; b.lchild=&d; b.rchild=&e; c.lchild=0; c.rchild=0; d.lchild=0; d.rchild=0; e.lchild=0; e.rchild=0;preRev(a); /调用递归函数对二叉树元素进行逐个处理 getch();int preRev(struct element e) /定义递归函数 if(e.lchild) preRev(*e.lchild);printf("%dn",e.data); if(e.rchild) pr

16、eRev(*e.rchild);后序递归#include<stdio.h>struct element /用结构体构建二叉树的元素struct element * lchild;int data;struct element * rchild;int main()struct element a,b,c,d,e;int preRev(struct element e); /声明处理二叉树元素的递归方函数 /构建二叉树 a.data=1; b.data=2; c.data=3; d.data=4; e.data=5;a.lchild=&b; a.rchild=&c;

17、b.lchild=&d; b.rchild=&e; c.lchild=0; c.rchild=0; d.lchild=0; d.rchild=0; e.lchild=0; e.rchild=0;preRev(a); /调用递归函数对二叉树元素进行逐个处理 getch();int preRev(struct element e) /定义递归函数 if(e.lchild) preRev(*e.lchild); if(e.rchild) preRev(*e.rchild); printf("%dn",e.data); 4、 运行结果前序递归：图5 前序递归运行结果

18、中序递归：图6 中序递归运行结果后序递归：图7 后序递归运行结果前序非递归：图8 前序非递归运行结果中序非递归：图9 中序非递归运行结果后序非递归：图10 后序非递归运行结果五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 在进行非递归遍历时，编译不报错，但运行出现下面的错误： 到网上查询后，得知出现“Access Violation”错误，有两种可能，第一种：出现这个错误是因为试图访问一块已经被释放的内存,第二种是想使用一个还未创建对象的指针。解决的办法是为指针分配内存，用(Node*)malloc(sizeof(Node)语句，这样就能解决这个问题。l 二叉树的建立 在刚开始进行时，如何建立二叉树难住了我，在网上查阅了一部分资料后，找到了合适的办法，就是用结构体来储存二叉树，结构体内定义了二叉树的值和左右子，用0代表null，这样就可以用先序算法遍历输入了。六、心得体会通过这次作业真的受益匪浅，感触良多：首先，要提高编程能力，必须多动手，多实践，而不是仅仅局限在书本上，