一、引言
二叉树的遍历常见的方法有先序遍历、中序遍历、后序遍历和层次遍历等，本文给出了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函数如下：文章来源：https://www.toymoban.com/news/detail-443688.html
void VisitNode( datatype data )
{
#ifdef CHAR
printf( "%5c", data );
#else
printf( "%5d", data );
#endif
}
补充：结合前面文章中的创建二叉树的算法，就可以完整的实现二叉树创建与后序遍历二叉树了。此处不再赘叙创建的算法。文章来源地址https://www.toymoban.com/news/detail-443688.html
到了这里，关于二叉树遍历之后序遍历（非递归、递归）入门详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
