#include "stdio.h"
#include "conio.h"
#define QUEUESIZE 100
#define TRUE 1
#define FALSE !TRUE
#define Statu int
#define BitTreeElementType int
#define BTELEMIOFORMAT "%d"
#define ENDFLAG -1

typedef struct Bittreenode
{
BitTreeElementType data;
struct Bittreenode *lchild;
struct Bittreenode *rchild;
}BTnode,*BitTree;

typedef BitTree QueueElemtype;

typedef struct
{
QueueElemtype data[QUEUESIZE];
int front;
int rear;
}queue;

int CreateQueue(queue *q);
int Entry(queue *q, QueueElemtype c);
Statu Exit(queue *q, QueueElemtype *reb);
Statu CreateBitTree(BitTree *T);
Statu LayerTravelBitTree(BitTree T);

main()
{
BitTree t;
system("cls");
printf("Input data to create bittree and '");
printf(BTELEMIOFORMAT,ENDFLAG);
printf("' will make null tree.\n");
CreateBitTree(&t);
printf("Layer order travel the tree:\n");
LayerTravelBitTree(t);

system("pause");
}

Statu CreateBitTree(BitTree *T)
{
BitTreeElementType inputdata;

*T = (BitTree )malloc(sizeof(BTnode));
printf("Enter Data:");
fflush(stdin);
scanf(BTELEMIOFORMAT,&inputdata);

if ( inputdata == ENDFLAG )
{
*T = NULL;
return FALSE;
}
else
{
(*T)->data = inputdata;
printf("Create left sub tree...<");
CreateBitTree(&((*T)->lchild));
printf("Create right sub tree...<");
CreateBitTree(&((*T)->rchild));
return TRUE;
}

}

Statu LayerTravelBitTree(BitTree T)
{
queue tq;
QueueElemtype res;

CreateQueue(&tq);
Entry(&tq,T);

while ( Exit(&tq,&res) == TRUE)
{
if (res)
{
VisitData(res->data);
Entry(&tq,res->lchild);
Entry(&tq,res->rchild);
}
}
}

int CreateQueue(queue *q)
{
q->front = -1;
q->rear = -1;
}

int Entry(queue *q, QueueElemtype c)
{
q->rear++;
if (q->rear >= QUEUESIZE)
{
printf("Queue overflow!\n");
exit(0);
}
q->data[q->rear] = c;
return 1;
}

Statu Exit(queue *q, QueueElemtype *returnback)
{
if (q->front == q->rear)
{
return FALSE;
}
q->front++;
*returnback = q->data[q->front];

return TRUE;
}

Statu VisitData(BitTreeElementType data)
{
printf(BTELEMIOFORMAT,data);
printf("\n");
return TRUE;
}