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

#define MAX_SIZE 100

typedef char ElemType;
typedef struct BiTree
{
	ElemType elem;
	BiTree* LChild;
	BiTree* RChild;
}BirTree,*PBiTree;

typedef struct Queue
{
	int rear;
	int front;
	PBiTree data[MAX_SIZE]; /** 指针数组*/
}Queue;

PBiTree CreateBiTree();
void EnQueue(Queue * Q,PBiTree elem);
PBiTree DeQueue(Queue * Q);
void InitQueue(Queue* Q);
void LevelTraversal(PBiTree Tree);

void main()
{
	PBiTree T = CreateBiTree();
	LevelTraversal(T);
}

void LevelTraversal(PBiTree T)
{
	Queue nQueue = {0,};
	InitQueue(&nQueue);

	if (T != NULL)
	{
		EnQueue(&nQueue,T);
	}

	while (nQueue.front != nQueue.rear) /** 当队列不为空时 */
	{
		PBiTree T = DeQueue(&nQueue);
		printf("%c ",T->elem);

		if (T->LChild != NULL)
		{
			EnQueue(&nQueue,T->LChild);
		}

		if (T->RChild != NULL)
		{
			EnQueue(&nQueue,T->RChild);
		}

		free(T);
	}
}


void InitQueue(Queue* Q)
{
	for (int i = 0; i < MAX_SIZE; i++)
	{
		Q->data[i] = 0;
	}

	Q->front = 0;
	Q->rear = 0;
}


void EnQueue(Queue * Q,PBiTree elem)
{
	/** 判断是否队满 */
	if ((Q->rear + 1) % MAX_SIZE != Q->front) 
	{
		Q->data[Q->rear] = elem;
		Q->rear = (Q->rear+1) % MAX_SIZE;
	}
}


PBiTree DeQueue(Queue * Q)
{
	PBiTree tmp;

	if (Q->front != Q->rear)
	{
		tmp = Q->data[Q->front];
		Q->front = (Q->front+1) % MAX_SIZE;

		return tmp;
	}
}


PBiTree CreateBiTree()
{
	PBiTree T;
	ElemType elem = '\0';

	scanf("%c",&elem);

	if (elem == '#')
	{
		T = NULL;
	}
	else
	{
		T = (PBiTree)malloc(sizeof(BiTree));
		T->elem = elem;
		T->LChild = CreateBiTree();
		T->RChild = CreateBiTree();
	}

	return T;
}