#include<stdio.h>
#include<stdlib.h>
#define NN 50


typedef struct BinaryTreeNode
{
    char Data;
    struct BinaryTreeNode* lChild, * rChild;
}BinaryTreeNode;
typedef BinaryTreeNode* BiTree;

typedef struct BinaryTree {
    BinaryTreeNode* root;
}BinaryTree;

typedef struct {
    BiTree data[NN];
    int front; //头指针
    int rear;//尾指针，队列非空时，指向队尾元素的下一个位置
    int num;//计量
}SqQueue;


void Quenein(BiTree Biquene, SqQueue* Q)
{
    if (Q->num == NN)
        return;
    Q->data[Q->front % NN] = Biquene;
    Q->front++;
    Q->num++;
}

BiTree Queneout(SqQueue * Q)
{
    if (Q->num == 0)
        return 0;
    Q->rear++;
    Q->num--;
    return Q->data[(Q->rear - 1) % NN];
}



BinaryTreeNode* PreCreateBt(BinaryTreeNode * t)
{
    char ch;
    ch = getchar();
    getchar();
    if (ch == '#')
        t = NULL;
    else
    {
       t = malloc(sizeof(BinaryTreeNode));
        t->Data = ch;
        t->lChild = PreCreateBt(t->lChild);
        t->rChild = PreCreateBt(t->rChild);
    }
    return t;
}


int main()
{
    BinaryTree myTree;
    SqQueue Q;
    Q.front = 0; Q.rear = 0; Q.num = 0;
    myTree.root = NULL;
    myTree.root = PreCreateBt(myTree.root);
    printf("LevelOrder:");
    Quenein(myTree.root, &Q);
    BiTree temp = NULL;
    if (myTree.root == 0)
        return 0;
    while (Q.num != 0)
    {
        temp = Queneout(&Q);
        if (temp == NULL)
            break;
        printf(" %c", temp->Data);
        //printf("Fuck you memory limit exceed");
        if (temp->lChild != NULL)
            Quenein(temp->lChild, &Q);
        if (temp->rChild != NULL)
            Quenein(temp->rChild, &Q);
    }
    //printf("sb");
    return 0;
}