void PostOrder(BiTree T,void (*visit)(char))
{
    BiTree p,temp;
    stack S;
    initstack(S);
    p=T;
    if(p==NULL) return;
    else{
        push(S,p);
        do{
            if(p->lchild!=NULL){
                p=p->lchild;
                push(S,p);
            }
            else{
                if(p->rchild!=NULL){
                    p=p->rchild;
                    push(S,p);
                }
                else{
                    visit(p->data);
                    while(1){
                        pop(S,temp);
                        if(emptystack(S)) return;
                        gettop(S,temp);
                        if(temp->rchild!=NULL&&p!=temp->rchild){
                            p=temp->rchild;
                            push(S,p);
                            break;
                        }
                        else{
                            visit(temp->data);
                            p=temp;
                        }
                    }
                }
            }
        }while(!emptystack(S));
    }
}
    

struct stack
{
    BiTree *base;
    BiTree *top;
    int stacksize;
};
//初始化栈
void initstack(stack & p)
{
    p.base=(BiTree *)malloc(sizeof(BiTree)*init_size);
    if(!p.base) exit(1);
    p.top=p.base;
    p.stacksize=init_size;
}

//判断栈空
bool emptystack(stack p)
{
    if(p.base==p.top)
        return(1);
    else
        return(0);
}

//返回栈的长度
int stack_length(stack p)
{
    return(p.top-p.base);
}




//若栈不空,返回栈的栈顶元素,并返回ok;否则返回error
bool gettop(stack p,BiTree & e)
{
    if(p.top!=p.base)
    {
        e=*(p.top-1);
        return(ok);
    }
    else
        return(error);
}







//插入元素e为栈顶元素
bool push(stack &p,BiTree e)
{
    if(stack_length(p)==p.stacksize)
    {
        p.base=(BiTree *)realloc(p.base,sizeof(BiTree)*(init_size+add_size));
        if(!p.base) exit(1);
        p.stacksize+=add_size;
        *(p.top)=e;
        p.top++;
    }
    else
    {
        *(p.top)=e;
        (p.top)++;
    }
    return(ok);
}
        




//若栈不空则删除栈顶元素,用e返回它的值,并返回ok;否则返error
bool pop(stack &p,BiTree & e)
{
    if(!emptystack(p))
    {
        e=*(p.top-1);
        p.top--;
        return(ok);
    }
    else
        return(error);
}

#include "stdio.h"
#include "stdlib.h"
#define ok 1
#define error 0
#define init_size 1000
#define add_size 100


typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//创建一个二叉树(先序),必先调用
bool CreateBiTree(BiTree &T)
{
    char ch;
    scanf("%c",&ch);
    if(ch==' ') T=NULL;
    else{
        T=(BiTNode *)malloc(sizeof(BiTNode));
        if(!T) exit(1);
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return(ok);
}
//输出结点的数据
void print(char e)
{
    printf("%c",e);
}



//先序遍历
void PreOrderTraverse(BiTree T,void (*visit)(char))
{
    if(T==NULL) return;
    else{
        visit(T->data);
        PreOrderTraverse(T->lchild,visit);
        PreOrderTraverse(T->rchild,visit);
    }
}

//中序遍历
void InOrderTraverse(BiTree T,void (*visit)(char))
{
    if(T==NULL) return;
    else{
        InOrderTraverse(T->lchild,visit);
        visit(T->data);
        InOrderTraverse(T->rchild,visit);
    }
}

//后序遍历 
void PostOrderTraverse(BiTree T,void (*visit)(char))
{
    if(T==NULL) return;
    else{
        PostOrderTraverse(T->lchild,visit);
        PostOrderTraverse(T->rchild,visit);
        visit(T->data);
    }
}

void InOrder(BiTree T,void (*visit)(char))
{
    stack S;
    BiTree p;
    initstack(S);
    push(S,T);
    while(!emptystack(S)){
        while(gettop(S,p)&&p) push(S,p->lchild);
        pop(S,p);
        if(!emptystack(S)){
            pop(S,p);
            visit(p->data);
            push(S,p->rchild);
        }
    }
}





void PreOrder(BiTree T,void (*visit)(char))
{
    stack S;
    BiTree p;
    initstack(S);
    push(S,T);
    while(!emptystack(S)){
        while(gettop(S,p)&&p){
            push(S,p->lchild);
            visit(p->data);
        }
        pop(S,p);
        if(!emptystack(S)){
            pop(S,p);
            push(S,p->rchild);
    
        }
    }
}

void create_tree(int *data)
{
 btree *new;
 btree *current;
 btree *father;
 int i;
 for(i=0;i<N;i++)
   {
    new=(btree*)malloc(sizeof(btree));
    new->key=data[i];
    new->lchild=NULL;
    if(root==NULL)
      root=new;
    else
      {
       current=root;
       while(current!=NULL)
         {
          father=current;
          if(current->key>=data[i])
            current=current->lchild;
          else
             current=current->rchild;
         }
       if(father->key>data[i])
         father->lchild=new;
       else
         father->rchild=new;
      }
   }
}