递归非递归两种算法遍历二叉树

1、一、设计思想1 .用递归算法遍历设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如 果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子 树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上 次的递归调用，重复输出和遍历右子树的操作。中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归 重复遍历左子树的操作， 直到遍历到叶子节点。 如果右子树为空，则回溯到上次递归调用

2、, 重复输出和遍历右子树的操作。后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后 遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上 次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。2 .用非递归算法遍历设计思想：主要是通过栈的存取，判空，从而实现树的遍历前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右 子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空， 则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到 栈为空后退出循环。中序遍历：通过循环实现。将树

3、一直遍历到最左端，并将中间所经过的节点保存在栈 中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节 点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在 树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然 后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为 1的话则代表此时数已经遍历过了，可以开始输出了，为了避 免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因

4、为一直左的操作并没有将右子树压栈）。、算法流程图图1递归算法-先序遍历递归算法-中序遍历图2递归算法-后序遍历图3图4非递归算法-先序遍历图5非递归算法-中序遍历Output图6非递归算法-后序遍历三、源代码#include<stdio.h>#include<stdlib.h>typedef char ElemType;/定义树结构typedef struct treeElemType data;struct tree * Ichild;struct tree * rchild;unsigned int isOut; 专为后序遍历设置的，0为不需要被输出，1为需要被输出

5、TreeNode, *Tree;/定义栈结构typedef struct stackTree * base;Tree * top;int stacksize;SqStack;void InitStack( SqStack &s );void Push( SqStack &s, Tree e );void GetTop( SqStack s, Tree &e );void Pop( SqStack &s, Tree &e );int StackEmpty( SqStack s );void CreateTree(Tree &t);void PreO

6、rder(Tree t);void PreOrder1(Tree t);void InOrder(Tree t);void InOrder1(Tree t);void PostOrder(Tree t);void PostOrder1(Tree t);int main()Tree T;printf("n按先序序列输入结点序列，'*代表空：");CreateTree(T);printf("n递归先序遍历的结果：");PreOrder(T);printf("n非递归先序遍历的结果：");PreOrderl(T);printf(&q

7、uot;n递归中序遍历的结果：");InOrder(T);printf("n非递归中序遍历的结果：");InOrderl(T);printf("n递归后序遍历的结果：")；PostOrder(T);printf("n非递归后序遍历的结果：");PostOrderl(T);printf("n");return 0;void InitStack( SqStack &s ) /初始化栈s.base = (Tree *)malloc(100*sizeof(Tree);if ( !s.base ) prin

8、tf("InitStack 内存分配出错，程序将推出执行！n");exit (-1);s.top = s.base;s.stacksize = 100;void Push (SqStack &s, Tree e ) / 元素入栈 接收一个stack类型变量和一个tree*类型变量if ( s.top - s.base >= s.stacksize )s.base = (Tree *)realloc(s.base,(s.stacksize+20)*sizeof(Tree);if ( !s.base ) printf("Push 内存分配出错，程序将退出

9、执行n");exit (-1); s.top = s.base + s.stacksize;/s.stacksize += 20;e->isOut = 0;*s.top+ = e;/获得栈顶元素 void GetTop( SqStack s, Tree &e )e = *(s.top - 1); /s.top为 tree*类型void Pop( SqStack &s, Tree &e )出栈if ( s.top = s.base )printf("栈为空 n");return ;e = *(-s.top);int StackEmpty

10、( SqStack s )/ 判断栈是否为空if ( s.top = s.base )return 1;return 0;void CreateTree(Tree &t)/以先序序列建立树char ch;scanf("%c",&ch); if ( ch = '*')t = NULL; else t = (Tree)malloc(sizeof(TreeNode);if ( !t )printf(" 分配内存出错！");return ;t->data = ch;CreateTree(t->lchild);Creat

11、eTree(t->rchild);递归先序遍历，遍历顺序：根、左、右void PreOrder(Tree t) / /先访问根节点，再先序遍历左子树，再先序遍历右子树if ( t )/如果树t不为空树，才继续执行先序遍历printf("%c ”,t->data);PreOrder(t->lchild);PreOrder(t->rchild);void InOrder(Tree t) /递归中序遍历，遍历顺序：左、中、右/先中序遍历左子树，再访问根节点，再中序遍历右节点if ( t ) /如果树t为空树，则停止向下遍历InOrder(t->lchild);

12、printf("%c ",t->data);InOrder(t->rchild);void PostOrder(Tree t) /递归后序遍历，遍历顺序：左、右、根if ( t ) PostOrder(t->lchild);PostOrder(t->rchild);printf("%c ",t->data); void PreOrder1(Tree t)非递归先序遍历Tree p = t;/p 为 tree*类型变量SqStack s;InitStack(s);while ( p | !StackEmpty(s) ) /当树

13、的节点不为空 或 栈不为空执行循环if ( p ) /当数的此节点不为空时，打印此节点值且将此节点入栈printf("%c ”,p->data);Push(s,p);p = p->lchild; else /否则父节点出栈，p指向父节点的右子树Pop(s,P)； p = p->rchild;void InOrder1(Tree t) / 非递归中序遍历Tree p = t;SqStack s;InitStack(s);while ( p | !StackEmpty(s) if ( p )Push(s,p);p = p->lchild; elsePoP(s,P)

14、；printf("%c ”,p->data);p = p->rchild; void PostOrder1(Tree t) /非递归后序遍历，遍历顺序：左、右、根t->isOut = 0;/初始值表示不输出Tree p = t;SqStack s;InitStack(s);while ( p | !StackEmpty(s) ) /节点非空 或 栈非空执行循环if ( P )if ( p->isOut )/左右子树都已输出，则该节点也输出Pop(s,p);printf("%c ”,p->data);if (!StackEmpty(s)GetTo

15、p(s,p); /得到该节点元素的父节点elsep = NULL; elseif ( (p->lchild) && (p->lchild->isOut = 1)/如果存在左子树，并且左子树已经遍历完，则说明该节点已经入栈p->isOut = 1;p = p->rchild;else /否则入栈该节点的树，并且走向它的左子树Push(s,p);p = p->lchild;elseGetTop(s,p);if ( p->rchild )p = p->rchild;elsePoP(s,P)；printf("%c ”,p->

16、;data);p->isOut = 1;if (!StackEmpty(s) GetTop(s,p);if ( p->lchild = NULL ) p->isOut = 1; /右子树已输出，将父节点 isOut置1 elsep = NULL;四、运行结果1 , 'lj：,DebugZf21.eKe'按先序序列输入结点序列，代表空，123*45*6*7*89*递归先序遍历的结果：1 2 3 4 5 6 7 8 9非递妇先序遍历的结果：123456780递归中序遍历的结果：325461798非递归中序遍历的结果；3 2 5 4 6 1 7 9 8递归后序遍历的

17、结果 3 5 6 4 2 9 8 7 1非递归后序遍历的结果：356429871Press any key to continue.图7遍历二叉树运行结果图五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列： 第一个问题：递归的使用，没有完全理解递归的含义描述：递归的使用是每次都将上次调用的现场保留，直到本次的方法的完成才会返回 上次的调用的现场，由于没有完全的了解， 所以在调用的时候回忽略掉上次保存的现场。解决：通过例子来解决分析，每次将递归调用的现场都记录下来，然后再进行下次递 归，从而避免了忽略掉的现场，得到错误的思想。第二个问题：非递归如何实现遍历描述：对于非

18、递归，我们不能像递归一样能保存中间的现场，而如果不能保存上次树 则不能调用当前树的下下个左子树或者右子树，所以我们必须得想出一种新的方法去实现 现场的保存。解决：通过一个栈来保存中间的调用线程，由于 while循环也有像递归一样的过程, 所以只要我们将每次调用的当前树的保存下来，那么下次调用的时候直接将栈里面的树弹 出即可访问上一次的保存的现场的树。第三个问题：对于非递归后序的实现描述：由于后续遍历又本身的特殊性，左子树，右子树，中间节点这样的一个顺序， 如果分开保存左子树和右子树，那么在遍历右子树后会丢失掉上次现场保留的中间节点， 如果要像中序遍历一样的方法保存的话，那么每次弹出后遍历右节点也会丢失上次现场保 留的中间节点。解决：通过一个标签的形式，在每次压栈的时候都给树标记下，由于都是先访问左子 树，再访问右子树，也就是说每棵树都是访问两次。那么就可以通过判断树的标志而实现 此时是否遍历左节点和右节点完成，从而输出中间节点。六、心得体会这次的实验相对来说不是很复杂，但是有些本质上的理论知识没有深入理解的话，那 么简单的东西也会变得很复杂，所以说，越是简单的东西，包含的知识量越多。二叉树遍历的实验，让我进一步深刻理解了二叉树创建的