树的非递归后序遍历

源代码
VS2005环境下编译通过：
#include
#define MAX 100
typedef struct BitNode{
char data;
int flag;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
typedef struct NodeStack{
BitNode* base;
BitNode* top;
int size;
}NodeStack;
void InitStack(NodeStack&s){
s.base=(BitNode*)malloc(MAX*sizeof(BitNode));
if(!s.base)
exit(1);
else
s.top=s.base;
s.size=MAX;
}
void Push(NodeStack& s,BitNode node){
if(s.top-s.base>=s.size)
{
s.base=(BitNode*)realloc(s.base,(s.size+10)*sizeof(BitNode));
if(!s.base)
exit(1);
s.top=s.base+s.size;
s.size+=10;
}
*s.top++=node;
}

void GetTop(NodeStack& s,BitNode& node){
if(s.top==s.base)
exit(1);
else
node=*--s.top;
}

BitTree CreateTree(){
BitTree root;
char in;
std::cin>>in;
if(in=='#')
return NULL;
else
{
root=(BitTree)malloc(sizeof(BitNode));
root->data=in;
root->lchild=CreateTree();
root->rchild=CreateTree();
}
return root;
}
void PostOrder(BitTree& T){
BitTree root=T;
NodeStack s;
InitStack(s);
while (root!=NULL||s.top!=s.base)
{
while (root!=NULL)
{ *s.top=*root;
(*s.top).flag=1;
s.top++;
root=root->lchild; }
while(s.top!=s.base&&(*(s.top-1)).flag==2)
{// root=s.top-1;
s.top--;
std::cout<data; }
if (s.top!=s.base) {

{
(*(s.top-1)).flag=2;
root=(s.top-1)->rchild;
}
}
}

}
int main(){
BitTree t;
std::cout<<”输入树：”;
t=CreateTree();
std::cout<<”后序出列为：”;
PostOrder(t);
}

五．测试用例
：

5.1
输入树：ABC##DE#G##F###;测试结果如下：
5.2
输入数为：A##；测试结果如下：