#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>

#define max 30
#define queuesize 100



typedef char datatype;

typedef struct node{      /*定義二叉樹鏈表結(jié)點結(jié)構(gòu)*/

  datatype data;

struct node *lchild,*rchild;

}BinTNode,*BinTree;

typedef struct
{
  int front,rear;

  BinTree data[queuesize];  /*定義循環(huán)隊列元素類型為二叉鏈表指針*/

  int count;

}cirqueue;       /*定義循環(huán)隊列結(jié)構(gòu)*/


void CreateBinTree(BinTree *T)  /*先序遞歸建立二叉樹*/

    {

     char ch;

     scanf("\n%c",&ch);

     if (ch=='0')  *T=NULL;            /*讀入0時，將相應(yīng)結(jié)點置空*/

     else {*T=(BinTNode*)malloc(sizeof(BinTNode));  /*生成結(jié)點空間*/

            (*T)->data=ch;

            CreateBinTree(&(*T)->lchild);     /*構(gòu)造二叉樹的左子樹*/

            CreateBinTree(&(*T)->rchild);     /*構(gòu)造二叉樹的右子樹*/

           }

}



void PreOrder(BinTree t)        /*遞歸先序遍歷*/
{
  if(t==NULL) return;

  printf("%c",t->data);

  PreOrder(t->lchild);

  PreOrder(t->rchild);
}

void InOrder(BinTree t)        /*遞歸中序遍歷*/
{
  if(t==NULL) return;

  InOrder(t->lchild);

  printf("%c",t->data);

  InOrder(t->rchild);
}

void PostOrder(BinTree t)      /*遞歸后序遍歷*/
{
  if(t=NULL) return;

  PostOrder(t->lchild);

  PostOrder(t->rchild);

  printf("%c",t->data);
}


void LevelOrder(BinTree t)   /*層次遍歷*/
{ cirqueue *q;

  BinTree p;

  q=(cirqueue *)malloc(sizeof(cirqueue)); /*申請循環(huán)隊列空間*/
  if(!q) return;

  q->count=q->rear=q->front=0; /*將循環(huán)隊列初始化為空*/

  q->data[q->rear]=t;       /*把根結(jié)點入隊列*/
  q->count++;
  q->rear=(q->rear+1)%queuesize;  /*判斷隊列是否為真溢出*/

  while(q->count)

    { if(q->data[q->front])  /*如果首元素不為空*/
        { p=q->data[q->front];
          printf("%c",p->data);   /*打印根結(jié)點元素*/

          q->front=(q->front+1)%queuesize;
          q->count--;        /*隊首元素出列*/

          if(q->count==queuesize)   /*判斷是否隊滿*/
            return;
          else
            { q->data[q->rear]=p->lchild;   /*左孩子入列*/
              q->count++;
              q->rear=(q->rear+1)%queuesize;
            }

          if(q->count==queuesize)
            return;
          else
            { q->data[q->rear]=p->rchild;      /*右孩子入列*/
              q->count++;
              q->rear=(q->rear+1)%queuesize;
            }
          }

      else   /*如果隊首為空指針，將空指針出列*/
        { q->front=(q->front+1)%queuesize;
          q->count--;
        }
    }
}

main()
{ BinTree bt;

  CreateBinTree(&bt);

  LevelOrder(bt);

  getch();
}