看了很多的二叉树后序遍历资料，没一个统一的，而且全都要么是那种while和if轮流嵌套，看能看明白，但是很快就忘，要么就是博客本身自己就写错了，但是底下评论一堆“测试正确”。
（就比如一些人写的，只用了一个结点栈，没有记录后序遍历时访问过的每个结点的左右子结点是否被访问过，只是记录了上一个访问过的结点的左右子结点是否访问过）
（再就是看的《王道》和其它博客上写的后序遍历的模式，大部分都是那种while套while，甚至里面还套了一层if-else加while，这种代码看着就头疼，而且二叉树本身的递归算法如此简洁，逻辑清晰，为什么到了你这个非递归就变成俄罗斯套娃了？）
最后找到了一篇博客（https://www.iteye.com/blog/hnsdjava-837103），该博主也对这些问题有所感触，然后写了另一种模式的后序遍历。在我看来，这是我见过的逻辑最清晰，代码最简洁的（简洁不是指量少）二叉树后序遍历了。
不过该博主是设置的树结点自带flag，记录自己的左右子结点是否被访问过，而且栈是C++类自带的，所以换成C语言实现起来的时候有些地方需要修改。
下面是根据那个博客的代码用C实现的，没有使用STL的stack。由于本来是打算做线索二叉树的后续遍历，所以多了一些域（其中ltag和rtag等于0时，表示这条边连接的是子结点，等于1时，表示这条边指向直接前驱/直接后驱），不过测试的时候这个后序遍历必须在线索化二叉树之前进行，线索化之后再后序遍历的话，还需要对其进行一些修改，比如对左右子结点的访问的部分。另外，printf部分保留，可以选择自己去除。
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag;
}ThreadNode, *ThreadTree;
void PostOrderBTreeTraverse(ThreadTree tree){
int top = -1;
ThreadTree tree_stack[15];
int flag[15] = {0};
tree_stack[++top] = tree; // push the root node
while(top != -1){
if(flag[top] == 0){ // flag == 0, none of the lchild or rchild of
// stack[top] is visited.
flag[top]++;
ThreadTree lchild = tree_stack[top]->lchild;
if(lchild != null){
tree_stack[++top] = lchild;
}
} else if (flag[top] == 1){ // flag == 1, lchild has been visited
flag[top]++;
ThreadTree rchild = tree_stack[top]->rchild;
if(rchild != null){
tree_stack[++top] = rchild;
}
} else { // flag == 2, rchild has been visited
tree = tree_stack[top];
printf("(ltag: %d, data: %c, rtag: %d)",
tree->ltag, tree->data, tree->rtag);
printf("\t----\t");
printf("lchild: 0x%x, rchild: 0x%x, this: 0x%x",
tree->lchild, tree->rchild, tree);
printf("\n");
/**
\note the flag must be cleared. Otherwise it will affect the process
of next turn.
*/
tree_stack[top] = null;
flag[top] = 0;
top--;
}
}
}
下面是测试的结果，根据输入的结点信息按照先序遍历的方式构建二叉树，另外“#”表示对应结点为null，不构建该结点。
二叉树的结构如图（可以根据下面遍历的结果中，当前结点和其lchild、rchild的指针地址来检验）
原文：https://www.cnblogs.com/atoshdustosh/p/13845909.html