#include<Stdio.h>
#include<Conio.h>
#include<Malloc.h>
#define MaxSize 100
 typedef struct node
 {
  char data;
  struct node *lchild;
  struct node *rchild;
 }BTNode;  BTNode  *b;
  void CreatBTNode(BTNode *b,char *str)
  {
    BTNode  *St[MaxSize],*p=NULL;
    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)
          {
           case1:St[top]->lchild=p;break;
           case2:St[top]->rchild=p;break;
          }
         }
       }
      j++;ch=str[j];
    }
    
  }
 

   void DispBTNode(BTNode *b)
   {
     if(b!=NULL)
    {
      printf("%c",b->data);
      if(b->lchild!=NULL||b->rchild!=NULL)
        {
         printf("(");
         DispBTNode(b->lchild);
         if(b->rchild!=NULL)     printf(",");
         DispBTNode(b->rchild);
         printf(")");
        }
    }
   }
  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");
 }
   void main()
  {

    CreatBTNode(b,"A(B(D(,G)),C(E,F))");
    printf("kuao gao biao shi fa:");
    DispBTNode(b);printf("\n");
    printf("ceng ci bian li:");
    TravLevel(b);
     getch();
  }