#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
//树结点的数据类型定义
typedef struct BTnode{
	DataType data;
	struct BTnode* lchild,*rchild;
}BTree;
//队列的结点数据类型定义
typedef struct node{
  BTree * tdata; //存放树结点类型的指针
  struct node *next;
}qnode;
//队头指针 和 队尾指针
typedef struct {
  qnode *front,*rear;
}linkQueue;
//初始化队列
void Init(linkQueue *q)
{
	q->front=q->rear=NULL;
}
//元素入队
void InsertQueue(linkQueue * &q,BTree * e)
{
	qnode * node;
	node=(qnode*)malloc(sizeof(qnode));
	node->tdata=e;
	node->next=NULL;
	if(NULL==q->front)
	{
		q->front=q->rear=node;
	}
	else
	{
		q->rear->next=node;
		q->rear=node;
	}
 
}
//元素出队
BTree * outQueue(linkQueue * &q)
{
	BTree * e;
	qnode *temp;
	if(NULL==q->front)
		e=NULL;
	else
	{
		temp=q->front;
		e=temp->tdata;
		q->front=temp->next;
		free(temp);
	}
	return e;
}
//创建二叉树,以先序的方式输入，如果左孩子或右孩子为空，则输入#  
/* 
   例子  A      输入为:ABD##E##CF### 
       /  \ 
     B     C 
    / \    /  
   D   E  F     
*/  
void createBTree(BTree * &t)
{
	char c;
   	c=getchar();
	if(c=='#')
		t=NULL;
	else
	{
		t=(BTree*)malloc(sizeof(BTree));
		t->data=c;
		createBTree(t->lchild);//创建左子树
		createBTree(t->rchild);//创建右子树
	}
}
 
/*
 
二叉树的层次遍历算法: 
1.队列queue初始化；
2. 将根指针入队；
3. 循环直到队列queue为空
      3.1 q=队列queue出队的元素;
      3.2 访问结点q的数据域;
      3.3 若结点q存在左孩子，则将左孩子入队;
      3.4 若结点q存在右孩子，则将右孩子入队;
 
*/
//二叉树的层次遍历
void hierarchyTtraversal(linkQueue *queue,BTree * root)
{
	BTree *q;
	InsertQueue(queue,root);
	while(NULL!=queue->front)
	{
		q=outQueue(queue);
		printf("%c  ",q->data);
		if(q->lchild)
			InsertQueue(queue,q->lchild);
		if(q->rchild)
			InsertQueue(queue,q->rchild);
	}
}
 
int main()
{
	BTree *root;
	linkQueue queue;
	Init(&queue);
	createBTree(root);
	hierarchyTtraversal(&queue,root);
	printf("\n");
	return 0;
}