#include  "stdio.h"
#include  "alloc.h"
#define  OK  1
#define  ERROR  0
#define  OVERFLOW  -2
#define  TRUE  1
#define  FALSE  0
#define Init_Size 100
#define INCR 20
typedef  int  Status;

typedef struct BNode
{ char data;
  struct BNode *lchild;
struct BNode *rchild;
} *BiTree;

typedef BiTree ElemType;

typedef struct
{ElemType *Elem;
 int Top;
 int StackSize;
}SqStack;

Status InitStack(SqStack &S)
{  S.Elem=(ElemType *)malloc(Init_Size*sizeof(ElemType));
 if(!S.Elem) return  OVERFLOW;
   S.Top=0;
   return OK;
}

Status GetTop(SqStack S, ElemType &e)
{if (S.Top==0)  return ERROR;
 e=S.Elem[S.Top-1];
 return OK;
 }

Status Push(SqStack &S, ElemType e)
{  if(S.Top==S.StackSize)
   {  S.Elem=(ElemType*)malloc((S.StackSize+INCR)*sizeof(ElemType));
      if(!S.Elem) return(OVERFLOW);
      S.StackSize+=INCR;
}
S.Elem[S.Top++]=e;
  return OK;
}

Status Pop(SqStack &S,ElemType &e)
 {if (!S.Top)
     {printf("stack is empty when poping\n");return(ERROR);}
  e=S.Elem[--S.Top];
  return OK;
 }

Status StackEmpty(SqStack S)
{if (S.Top) return FALSE;
else return TRUE;}

void CreatBiTree(BiTree &T)
{  char ch;
   scanf("%c",&ch);
   if(ch=='$') T=NULL;
   else
 {  T=(BiTree)malloc(sizeof(struct BNode));
      T->data=ch;
      CreatBiTree(T->lchild);
      CreatBiTree(T->rchild);
   }
}
 
 void Preorder(BiTree T)
 { if (T)
    {printf("%c",T->data);
     Preorder(T->lchild);
     Preorder(T->rchild);
     }
}

  void Inorder(BiTree T)
 { if (T)
    {Inorder(T->lchild);
     printf("%c",T->data);
     Inorder(T->rchild);}
 }

 void Postorder(BiTree T)
 { if (T)
    {Postorder(T->lchild);
     Postorder(T->rchild);
     printf("%c",T->data);}
 }

int DepthTree(BiTree T)
{  int d1,d2;
   if(!T) return 0;
   else 
{  d1=DepthTree(T->lchild);
   d2=DepthTree(T->rchild);
   return d1>=d2?d1+1:d2+1;
 }
}

void Preorder_N(BiTree T)
{   SqStack S;
    BiTree p;
    InitStack(S); 
    Push(S,T);
    while(!StackEmpty(S))
       { while (GetTop(S,p)&&p)
		{ printf("%c",p->data); Push(S,p->lchild);}
	Pop(S, p);
        if(!StackEmpty(S))
        	{ Pop(S,p); Push(S,p->rchild);}
        }
 }

void Inorder_N(BiTree T)
{   SqStack S;
    BiTree p;
    InitStack(S);
    Push(S,T);
    while(!StackEmpty(S))
	{ while (GetTop(S,p)&&p)
		{Push(S,p->lchild);}
	Pop(S,p);
	if(!StackEmpty(S))
	   { Pop(S,p); printf("%c",p->data);Push(S,p->rchild);}
        }
 }


main()
{ BiTree T;
  CreatBiTree(T);
  printf("Preorder binary tree :\n" );
  Preorder(T);
  printf("\nInorder binary tree:\n");
  Inorder_N(T);
  printf("\nPostorder binary tree:\n");
  Postorder(T);
  printf("\nThe depth of this binary tree is:%d\n",DepthTree(T));
}