include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

define MaxNodeNum 100

typedef struct bitnode{
char data;
struct bitnode lchild,rchild;
}bitnode,bitree;
void createbitree(bitree& bt,int &n,char pre[]){
char c=pre[n];
if(c==’#’){
bt=NULL;
return;
}
n+=1;
bt=(bitnode )malloc(sizeof(bitnode));
bt->data=c;
createbitree(bt->lchild,n,pre);
n+=1;
createbitree(bt->rchild,n,pre);
}
void postorder(bitree bt){
if(bt!=NULL){
postorder(bt->lchild);
postorder(bt->rchild);
cout<[HTML_REMOVED]data<<’ ‘;
}
}
void postorder_stack(bitree bt){
//这里我使用非递归算法
bitnode * stack[MaxNodeNum];//初始化栈
int top=0;//指向可以插入的位置
bitnode * p=bt;
bitnode * pre=NULL;
//后序非递归的特殊处在于，两次查看栈顶
//如果右孩子为空，直接拿信息和出栈访问是一起的
//如果右孩子不为空，那么我们要判断是第二次还是第三次
//主要的依据就是上一个访问的点是不是右孩子（后序的前驱就是右孩子）
while(p!=NULL||top>0){//非递归就是要么入栈要么出栈
if(p!=NULL){
stack[top++]=p;
p=p->lchild;
}
else
{
p=stack[top-1];//这里仅仅是查看栈顶元素
if(p->rchild!=NULL&&pre!=p->rchild){
//这里也是合并情况了
//三种情况两种的结果是一样的
//右孩子存在并且上一个点不是右孩子，说明是第二次来
//进入右孩子即可，其余情况都是直接出栈访问
p=p->rchild;
}else
{
p=stack[–top];//这里是出栈了
cout<[HTML_REMOVED]data<<’ ‘;
pre=p;
p=NULL;//这一步也很关键呀，代表下一步是出栈
}
}
}
}
int main(){
bitree p;
char pre[]={‘a’,’b’,’d’,’#’,’#’,’e’,’#’,’g’,’#’,’#’,’c’,’f’,’#’,’#’,’#’};
int m=0;
int& n = m;
createbitree(p,n,pre);
cout<<”正确的后序”<<endl;
postorder(p);
cout<<endl<<”非递归后序”<<endl;
postorder_stack(p);
free(p);

}