#define QUEUESIZE 100
#define TRUE 1
#define FALSE !TRUE
#define Statu int
#define BitTreeElementType char
#define BTELEMIOFORMAT "%c"
#define ENDFLAG         -1
int i=0,j=0;

typedef struct Bittreenode
{
BitTreeElementType  data;
struct Bittreenode *lchild;
struct Bittreenode *rchild;
}BinTNode,*BinTree;

typedef BinTree QueueElemtype;


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

 
void  LayerTravelBitTree(BinTree 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;
}



//構(gòu)造二叉鏈表
void CreateBinTree(BinTree *T)
{//構(gòu)造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實(shí)參（根指針）本身
char ch;

if ((ch=getchar())=='#')
    *T=FALSE;
else{//讀入非空格
     *T=(BinTNode *)malloc(sizeof(BinTNode));
     (*T)->data=ch;
	 i++;
     CreateBinTree(&(*T)->lchild);
     CreateBinTree(&(*T)->rchild);
    }
}
 //先序遍歷 
 void Inorder(BinTree T)
 {
	 if(T){
		 printf("%c",T->data);
	     Inorder(T->lchild);
         Inorder(T->rchild);
	 }
 }


 //中序遍歷

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

//后序遍歷

 void Hinorder(BinTree T)
 {
	 if(T){
	     Hinorder(T->lchild);
         Hinorder(T->rchild);
		 printf("%c",T->data);
	 }
 }
  
void Yinorder(BinTree T)
{  
	 if(T){
		  if(T->lchild==FALSE)
			 if(T->rchild==FALSE)
			 {j++;
			 goto aaa;
             }
         Yinorder(T->lchild);
         Yinorder(T->rchild);
	 }
aaa: printf("_");
	 
 }
 
 
main()
 {  BinTree *p; 
    CreateBinTree(p);
	printf("先序遍歷 :");
	Inorder(p);
    printf("\n");
	printf("中序遍歷 :");
	Zinorder(p);
	printf("\n");
	printf("后序遍歷 :");
	Hinorder(p);
	printf("\n");
	printf("層次遍歷 :");
	LayerTravelBitTree(p);
	printf("\n");
    printf("總結(jié)點(diǎn)數(shù)   :%d\n",i);
	Yinorder(p);
	printf("\n葉子結(jié)點(diǎn)數(shù):%d\n",j);
 }