二叉树遍历之后序遍历（非递归、递归）入门详解

一、引言

二叉树的遍历常见的方法有先序遍历、中序遍历、后序遍历和层次遍历等，本文给出了C语言版本的后序遍历二叉树的非递归算法和递归算法。
后序遍历不如先序遍历简单，是相对最复杂的一种遍历方法。访问结点的次序是：“左—>右—>根”，也就是首先访问左子树，之后访问右子树，最后访问树根。对于左、右子树而言，其访问的次序依然是“左—>右—>根”。也就是说，对于每一棵子树，都是最后访问树根。
从上面描述可以看出遍历过程其实是递归的过程，因此可以使用递归算法来实现，但是同样也可以使用非递归的方法来实现。

二、二叉树的后序遍历详细演示过程

1、假设二叉树（左右子树全）如下图所示：

则后序遍历过程是：左子树b—>右子树c—>树根a
2、假设二叉树（没有右子树）如下图所示：

则后序遍历过程是：左子树b—>树根a
3、假设二叉树（没有左子树）如下图所示：

则后序遍历过程是：右子树c—>树根a
4、对于稍微复杂一点的二叉树，如下图所示：

其后序遍历过程演示如下（“左—>右—>根”）
Step 1. 首先访问结点 d

Step 2. 访问结点 g

Step 3. 访问结点 e

Step 4. 访问结点b

Step 5. 访问结点h

Step 6. 访问结点f

Step 7. 访问结点c

Step 8. 访问树根a

至此后序遍历该二叉树结束，遍历结果为：d g e b h f c a
5、重复访问标志
在此遍历过程中，会发现树根及子树的树根会被访问两次，为了避免这个问题，第一遇到的时候不访问，而第二次遇到的时候再访问，因此引入了一个访问标志。
三、后序遍历二叉树的源代码：
1、结点结构及条件编译

typedef struct node
{
    
	datatype data;
	struct node *Lchild;
	struct node *Rchild;
	int    flag;
}BiTree;
#ifdef CHAR
typedef char datatype;
#else
typedef int datatype;
#endif

2、递归算法

void  PostorderSearch_Recu( BiTree  *T)
{
      
	if  (T!=NULL) 
	{
         
		PostorderSearch_Recu(T->Lchild) ;
		PostorderSearch_Recu(T->Rchild) ; 
		VisitNode(T->data) ;        
	}
} 

3、非递归算法

void PostorderSearch( BiTree *T )
{
    
	BiTree *p, *stack[ MAX_NODE ];
	int top = 0;//栈顶位置下标
	if( T == NULL ) 
	{
    
		return;
	}
	p = T;
	while( 1 )
	{
    
		if( p != NULL )//p非空，则入栈，之后p向左走 
		{
    
			stack[ top++ ] = p;
			p = p->Lchild;
		}
		else//p为空，则出栈 
		{
    
			p = stack[ --top ];
			//右为空，且flag为真，则访问，之后p置空 
			if( p->Rchild == NULL || p->flag == 1 )
			{
    
				VisitNode( p->data );
				p = NULL;
			} 
			else//右非空，则p重新入栈，重复入栈标志flag置为真，之后p向右走
			{
    
				stack[ top++ ] = p;
				p->flag = 1;
				p = p->Rchild;
			}
		} 
		if( top == 0 )//栈为空，则结束遍历
		{
    
			break;
		}
	}
}

4、VisitNode函数如下：

void VisitNode( datatype data )
{
    
#ifdef CHAR
	printf( "%5c", data );
#else
	printf( "%5d", data );
#endif
}

补充：结合前面文章中的创建二叉树的算法，就可以完整的实现二叉树创建与后序遍历二叉树了。此处不再赘叙创建的算法。