二叉树的后序非递归遍历

Question

#include "malloc.h"
#include "stdio.h"
#include "iostream.h"

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 5
#define ERROR 0
#define OK 1

typedef int ElemType;
typedef int Status;
typedef struct BinaryTree
{
ElemType data;
struct BinaryTree *lchild;
struct BinaryTree *rchild;
}*BiTree,BiTNode,*SElemType;

typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

Status GetTop(SqStack S,SElemType &e)
{
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}

Status Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,
(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}

Status Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base)return ERROR;
e=*--S.top;
return OK;
}

Status StackEmpty(SqStack S)
{
if(S.top==S.base) return OK;
else return ERROR;
}

Status CreateBiTree(BiTree &T)
{//先序创建用二叉链表表示的二叉树，0表示空树
int tdata;
cin>>tdata;
if (tdata==0) T=NULL;
else
{
if(!(T=new BiTNode)) return ERROR;
T->data=tdata;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}

int printelem(ElemType e)
{
printf("%d\t",e);
return OK;
}

求符合上述程序的[二叉树]的[后序][非递归]遍历算法

Answer 1

PostOrder2(BiTree root)
{
BiTNode *node=root;
SeqStack *S=(SeqStack *)malloc(sizeof(SeqStack));
InitStack(S);
while (root || !IsEmpty(S))
{
if (root)
{
Push(S, root);
root=root->LChild;
}
else
{
GetTop(S, &root);
if (root->RChild==NULL || root->RChild==node)
{
Visit(root);
Pop(S, &root);
node=root;
root=NULL;
}
else
{
root=root->RChild;
}
}
}
}

======================或者======================
PostOrder(BiTree root)
{
if (root)
{
PostOrder(root->LChild);
PostOrder(root->RChild);
Visit(root);
}
}

Answer 2

用栈模拟啊