#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
  ElemType data;
  struct node *lchild;
  struct node *rchild;
}BTNode;
void CreateBTree(BTNode *&b,char *str)
{
  BTNode * St[MaxSize],*p;
  int top=-1,k,j=0;char ch;
  b=NULL;
  ch=str[j];
  while(ch!='\0')
  {
    switch(ch)
    {
    case'(':top++;St[top]=p;k=1;break;
    case')':top--;break;
    case',':k=2;break;
    default:p=(BTNode *)malloc(sizeof(BTNode));
      p->data=ch;p->lchild=p->rchild=NULL;
      if(b==NULL)
        b=p;
      else
      {
        switch(k)
        {
                case 1:St[top]->lchild=p;break;
        case 2:St[top]->rchild=p;break;
        }
      }
    }
    j++;ch=str[j];
  }
}
void DestroyBTree(BTNode *&b)
{
  if(b!=NULL)
  {
    DestroyBTree(b->lchild);
        DestroyBTree(b->rchild);
    free(b);
  }
}
BTNode *FindNode(BTNode *b,ElemType x)
{
  BTNode *p;
  if(b==NULL)
    return NULL;
  else if(b->data==x)
    return b;
  else
  {
    p=FindNode(b->lchild,x);
    if(p!=NULL)
      return p;
    else
      return FindNode(b->rchild,x);
  }
}
BTNode *LchildNode(BTNode *p)
{
  return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
  return p->rchild;
}
int BTHeight(BTNode *b)
{
  int lchildh,rchildh;
  if(b==NULL)return(0);
  else
  {
    lchildh=BTHeight(b->lchild);
    rchildh=BTHeight(b->rchild);
    return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
  }
}
void DispBTree(BTNode *b)
{
  if(b!=NULL)
  {
    printf("%c",b->data);
    if(b->lchild!=NULL||b->rchild!=NULL)
    {
      printf("(");
      DispBTree(b->lchild);
      if(b->rchild!=NULL)printf(",");
      DispBTree(b->rchild);
      printf(")");
    }
  }
}
#include"btree.cpp"
void PreOrder(BTNode *b)
{
  if(b!=NULL)
  {
    printf("%c",b->data);
    PreOrder(b->lchild);
    PreOrder(b->rchild);
  }
}
void PreOrderl(BTNode *b)
{
  BTNode *St[MaxSize],*p;
  int top = -1;
  if(b!=NULL)
  {
    top++;
    St[top]=b;
    while(top>-1)
    {
      p=St[top];
      top--;
      printf("%c",p->data);
      if(p->rchild!=NULL)
      {
        top++;
        St[top]=p->rchild;
      }
      if(p->lchild!=NULL)
      {
        top++;
        St[top]=p->lchild;
      }
    }
    printf("\n");
  }
}
void InOrder(BTNode *b)
{
  if(b!=NULL)
  {
    InOrder(b->lchild);
    printf("%c",b->data);
    InOrder(b->rchild);
  }
}
void InOrderl(BTNode *b)
{
  BTNode *St[MaxSize],*p;
  int top = -1;
  if(b!=NULL)
  {
    p=b;
    while(top>-1 || p!=NULL)
    {
      while(p!=NULL)
      {
        top++;
        St[top]=p;
        p=p->lchild;
      }
      if(top>-1)
      {
        p=St[top];
        top--;
        printf("%c",p->data);
        p=p->rchild;
      }
    }
    printf("\n");
  }
}
void PostOrder(BTNode *b)
{
  if(b!=NULL)
  {
    PostOrder(b->lchild);
    PostOrder(b->rchild);
    printf("%c",b->data);
  }
}
void PostOrderl(BTNode *b)
{
  BTNode *St[MaxSize],*p;
  int top = -1;
  bool flag;
  if(b!=NULL)
  {
    do
    {    while(b!=NULL)
      { 
        top++;
        St[top]=p;
        b=b->lchild;
      }
        p=NULL;
      flag=true;
      while(top!=-1&&flag)
      {
        b=St[top];
        if(b->rchild==p)
        {
            printf("%c",b->data);
            top--;
            p=b;
        }
        else
        {
          b=b->rchild;
          flag=false;
        }
      }
    }while(top!=-1);
    printf("\n");
  }
}
void TravLevel(BTNode *b)
{
  BTNode *Qu[MaxSize];
  int front,rear;
  front = rear=0;
  if(b!=NULL)printf("%c",b->data);
  rear++;
  Qu[rear]=b;
  while(rear!=front)
  {
    front=(front+1)%MaxSize;
    b=Qu[front];
    if(b->lchild!=NULL)
    {
      printf("%c",b->lchild->data);
      rear=(rear+1)%MaxSize;
      Qu[rear]=b->lchild;
    }
    if(b->rchild!=NULL)
    {
      printf("%c",b->rchild->data);
      rear=(rear+1)%MaxSize;
      Qu[rear]=b->rchild;
    }
  }
  printf("\n");
}
int main()
{
  BTNode *b;
  CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
  printf("二叉树b:");DispBTree(b);printf("\n");
  printf("层次遍历序列:");
  TravLevel(b);
  printf("先序遍历序列:\n");
  printf("   递归算法:");PreOrder(b);printf("\n");
  printf(" 非递归算法:");PreOrder(b);printf("\n");
  printf("中序遍历序列:\n");
  printf("   递归算法:");InOrder(b);printf("\n");
  printf(" 非递归算法:");InOrder(b);printf("\n");
  printf("后序遍历序列:\n");
  printf("   递归算法:");PostOrder(b);printf("\n");
  printf(" 非递归算法:");PostOrder(b);printf("\n");
  DestroyBTree(b);
  return 1;
}