//代码经过测试，赋值粘贴即可用
#include<iostream>

#include<stdio.h>

#include<stack>

#include<queue>

#include<malloc.h>

using namespace std;

//二叉树结点

typedef struct BTNode{

    char data;

    struct BTNode *lchild;

    struct BTNode *rchild;

}BTNode;

//模板先序建立二叉树，大话p187，教科书吧版

BTNode *CreateBiTree()//只需要一个函数

{

    char ch;

    BTNode *T;

    scanf("%c",&ch);

    if(ch=='#')

        T=NULL;

    else

    {

        T = (BTNode *)malloc(sizeof(BTNode));

        T->data = ch;

        T->lchild = CreateBiTree();

        T->rchild = CreateBiTree();

    }

    return T;//返回根节点

}

//层次遍历

void LevelOrder(BTNode *T){

  //queue<BTNode> queue;大bug隐藏在这个地方；注意queue这个容器装的是什么东西
    queue<BTNode *> queue;

    queue.push(T);         //算法：根结点入队列

    while(!queue.empty()){ //若队列非空则循环执行下列的3个步骤

        T = queue.front();  //步骤1：对头元素出队，指针从新指向，front()方法是将返回队头元素

        printf("%c ",T->data);//队头元素出队然后将队头元素的左右孩子入队

        queue.pop();//pop是出队

        if(T->lchild != NULL){//步骤2：左子树不空，将左子树入队

            queue.push(T->lchild);//入队的就是一个地址元素

        }

        if(T->rchild != NULL){//步骤3：右子树不空，将右子树入队

            queue.push(T->rchild);

        }

    }

}

int main()

{

    BTNode *T;

    T = CreateBiTree();//建立

     LevelOrder(T);

    return ;

}