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

一、设计思想

1. 用递归算法遍历

设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历

前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。

中序遍历： 先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。

后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。

2. 用非递归算法遍历

设计思想：主要是通过栈的存取，判空，从而实现树的遍历

前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。

中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。

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

- 1 -

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

二、算法流程图

开始 Root=Tree t Y Root=null N 输出数据 N Root.getLTree=null Y N Root.getRTree=null Y 结束 图1 递归算法-先序遍历

开始 开始 Root=Tree t Root=Tree t Y Y Root=null Root=null N N N N Root.getLRoot.getLTree=null Tree=null Y Y N 输出数据 Root.getRTree=null N Y Root.getRTree=null 输出数据 Y 结束 结束 图2 递归算法-后序遍历 图3 递归算法-中序遍历

- 2 -

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

开始 开始 Tree t=root Tree t=root N t = null output N t = null 压栈 Y N t.getRtree= null Push t= Y t=current. getLtree() stack.Pop() Y output N t.getLtree= null Push Y N t=current. getRltree() 栈为空 t= stack.pop() N 栈为空 Y Y 结束 结束 图4 非递归算法-先序遍历 图5 非递归算法-中序遍历

- 3 -

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

开始 Tree t=root N t = null Push 标签栈压栈 Y t= stack.pop() t=t.getLtree() 标签栈出栈 赋值给标志位 N 判断栈是否已经入栈过 t=t.getRTree() 标签栈压栈 Y 出栈并赋值t Output Current=null N 树栈为空且当前节点为空 Y 结束 图6 非递归算法-后序遍历

- 4 -

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

三、源代码

#include #include

typedef char ElemType; //定义树结构 typedef struct tree {

ElemType data; struct tree * lchild; struct tree * rchild;

unsigned int isOut; //专为后序遍历设置的，0为不需要被输出，1为需要被输出 }TreeNode, *Tree;

//定义栈结构 typedef struct stack {

Tree * 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 PreOrder(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);

- 5 -

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

printf(\"\\n非递归先序遍历的结果：\"); PreOrder1(T);

printf(\"\\n 递归中序遍历的结果： \"); InOrder(T);

printf(\"\\n非递归中序遍历的结果：\"); InOrder1(T);

printf(\"\\n 递归后序遍历的结果： \"); PostOrder(T);

printf(\"\\n非递归后序遍历的结果：\"); PostOrder1(T); printf(\"\\n\"); }

void InitStack( SqStack &s ) //初始化栈 {

s.base = (Tree *)malloc(100*sizeof(Tree)); if ( !s.base ) {

printf(\"InitStack内存分配出错,程序将推出执行！\\n\"); exit (-1); return 0;

} 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 ) { }

s.top = s.base + s.stacksize; // s.stacksize += 20;

printf(\"Push内存分配出错,程序将退出执行\\n\"); exit (-1);

}

e->isOut = 0; *s.top++ = e; }

void GetTop( SqStack s, Tree &e ) //获得栈顶元素

- 6 -

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

{ }

void Pop( SqStack &s, Tree &e ) {

if ( s.top == s.base ) {

printf(\"栈为空\\n\"); return ;

//出栈

e = *(s.top - 1); //s.top为 tree** 类型

}

e = *(--s.top); }

int StackEmpty( SqStack s ) {

if ( s.top == s.base )

return 1;

return 0; }

void CreateTree(Tree &t) {

char ch; scanf(\"%c\ if ( ch == '*' )

t = NULL;

else { }

void PreOrder(Tree t) //递归先序遍历，遍历顺序：根、左、右 {

t = (Tree)malloc(sizeof(TreeNode)); { }

t->data = ch; CreateTree(t->lchild); CreateTree(t->rchild);

printf(\"分配内存出错！\"); return ;

if ( !t )

//以先序序列建立树

//判断栈是否为空

}

- 7 -

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

//先访问根节点，再先序遍历左子树，再先序遍历右子树

if ( t ) //如果树 t 不为空树，才继续执行先序遍历 { }

void InOrder(Tree t) //递归中序遍历，遍历顺序：左、中、右 {

//先中序遍历左子树，再访问根节点，再中序遍历右节点

if ( t ) //如果树 t 为空树，则停止向下遍历 { }

void PostOrder(Tree t) //递归后序遍历，遍历顺序：左、右、根 { if ( t ) { }

void PreOrder1(Tree t) //非递归先序遍历 {

Tree p = t; SqStack s; InitStack(s);

while ( p || !StackEmpty(s) ) //当树的节点不为空 或 栈不为空执行循环 {

if ( p ) //当数的此节点不为空时，打印此节点值且将此节点入栈 { }

printf(\"%c \ Push(s,p); p = p->lchild;

//p为 tree* 类型变量

PostOrder(t->lchild); PostOrder(t->rchild); printf(\"%c \

InOrder(t->lchild); printf(\"%c \ InOrder(t->rchild);

printf(\"%c \ PreOrder(t->lchild); PreOrder(t->rchild);

}

}

}

- 8 -

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

}

void InOrder1(Tree t) //非递归中序遍历 {

Tree p = t; SqStack s;

InitStack(s); while ( p || !StackEmpty(s) ) { }

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 \ //初始值表示不输出

if ( p ) {

Push(s,p); p = p->lchild;

else //否则父节点出栈，p指向父节点的右子树 { }

Pop(s,p); p = p->rchild;

}

} else { }

Pop(s,p);

printf(\"%c \ p = p->rchild;

}

- 9 -

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

}

} else { }

GetTop(s,p); if ( p->rchild ) { } else { }

Pop(s,p);

printf(\"%c \ p->isOut = 1; if (!StackEmpty(s)) { } else

p = NULL; GetTop(s,p);

if ( p->lchild == NULL ) p->isOut = 1;

//右子树已输出，将父节点isOut置1

p = p->rchild; } else { }

if ( (p->lchild) && (p->lchild->isOut == 1) ) { }

else //否则入栈该节点的树，并且走向它的左子树 {

Push(s,p); p = p->lchild;

//如果存在左子树,并且左子树已经遍历完，则说明该节点已经入栈 p->isOut = 1; p = p->rchild;

if (!StackEmpty(s))

GetTop(s,p); p = NULL;

//得到该节点元素的父节点

else

}

}

- 10 -

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

四、运行结果

图7 遍历二叉树运行结果图

五、遇到的问题及解决

这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：  第一个问题：递归的使用，没有完全理解递归的含义

描述：递归的使用是每次都将上次调用的现场保留，直到本次的方法的完成才会返回上次的调用的现场，由于没有完全的了解，所以在调用的时候回忽略掉上次保存的现场。

解决：通过例子来解决分析，每次将递归调用的现场都记录下来，然后再进行下次递归，从而避免了忽略掉的现场，得到错误的思想。

 第二个问题：非递归如何实现遍历

描述：对于非递归，我们不能像递归一样能保存中间的现场，而如果不能保存上次树则不能调用当前树的下下个左子树或者右子树，所以我们必须得想出一种新的方法去实现现场的保存。

解决：通过一个栈来保存中间的调用线程，由于while循环也有像递归一样的过程，所以只要我们将每次调用的当前树的保存下来，那么下次调用的时候直接将栈里面的树弹出即可访问上一次的保存的现场的树。

 第三个问题：对于非递归后序的实现

描述：由于后续遍历又本身的特殊性，左子树，右子树，中间节点这样的一个顺序，如果分开保存左子树和右子树，那么在遍历右子树后会丢失掉上次现场保留的中间节点，如果要像中序遍历一样的方法保存的话，那么每次弹出后遍历右节点也会丢失上次现场保留的中间节点。

解决：通过一个标签的形式，在每次压栈的时候都给树标记下，由于都是先访问左子树，再访问右子树，也就是说每棵树都是访问两次。那么就可以通过判断树的标志而实现此时是否遍历左节点和右节点完成，从而输出中间节点。

- 11 -

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

六、心得体会

这次的实验相对来说不是很复杂，但是有些本质上的理论知识没有深入理解的话，那么简单的东西也会变得很复杂，所以说，越是简单的东西，包含的知识量越多。

二叉树遍历的实验，让我进一步深刻理解了二叉树创建的原理，而不是将它当做书本上的一些定义和理论的东西，当然，通过这次实验，遍历二叉树的前序遍历、中序遍历、后序遍历的三种方法也有了进一步的巩固。当只有理论的东西有实践的价值的时候，理解起来会更加的透彻，同时我也重新复习了一遍递归的过程。就像这次，由于没有对递归有深刻的记忆，所以导致整个实验做起来很吃力，所以说，温故而知新，这个才是学习的的精髓，当一边学习新的知识，一边却忘记以往的理论原理，那么这样的理论基础也太脆弱了。这样建立起来的大厦也只是豆腐渣工程。总而言之，学习是一个不断获取和不断遗忘的过程，我们要做的是将这个天平始终保持在获取这边，这就是这次实验带给我最大的收获。

- 12 -