本篇文章介绍了如何使用非递归的方法实现对二叉树进行后序遍历，在不采用系统栈的情况下优化了空间复杂度。
本段落主要介绍了使用C语言实现非递归后序遍历二叉树的方法，并提供了两种不同的思路及代码示例供读者参考。
一、方法一：栈的实现
在第一种方法中，我们利用两个栈来完成非递归后的顺序访问。第一个栈用来存储节点，第二个栈用于记录访问次序。首先将根节点压入第一个栈内，然后按照根->右子树->左子树的顺序遍历二叉树，并不直接输出结点信息而是将其压入第二层栈中进行临时保存；最后从这个辅助栈里弹出并打印每个元素。
代码示例：
```c
#include
#include
typedef struct TreeNode{
char element;
struct TreeNode *left,*right;
}Tree, *BTree;
// 栈的定义和操作函数省略
void NotRecursionPostOrder(BTree T){
PLinkStack S,CS;
S=Init_Stack();
CS=Init_Stack();
while(T || !empty_Stack(S)){
if(T){
Push_Stack(S,T);
Push_Stack(CS,T);
T=T->right;
}else{
T=Pop_Stack(S)->data;
T=T->left;
}
}
while(CS->top!=NULL){
printf(%c,CS->top->data->element);
CS->top=CS->top->next;
}
DestroyStack(CS);
}
```
二、方法二：标记的使用
第二种实现方式通过在节点上设置标志来追踪其访问状态。我们按照先序遍历的方式进行，每次遇到新结点时将其压入栈中，并将该结点的状态置为未被处理过；当再次访问到此结点的时候，如果发现它的左右子树都已经被访问过了，则可以安全地输出当前节点的信息。
代码示例：
```c
#include
#include
typedef struct TreeNode {
char element;
int flag;
struct TreeNode *left, *right;
}Tree, *BTree;
// 栈的定义和操作函数省略
void NotRecursionPostOrder(BTree T){
PLinkStack S;
S=Init_Stack();
Push_Stack(S,T);
while(!empty_Stack(S)){
BTree p=Pop_Stack(S)->data;
if(p->flag){
printf(%c,p->element);
}else{
Push_Stack(S,p);
p->flag=1;
if(p->right){
Push_Stack(S,p->right);
}
if(p->left){
Push_Stack(S,p->left);
}
}
}
DestroyStack(S);
}
```
通过这两种方法，我们可以实现非递归的后序遍历。在实际应用中可以根据具体需求选择适合的方法来使用。
5星
