#层序遍历建立二叉树#

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode{     //树结构体，记录树节点的左右儿子
    char data;
    TreeNode* leftchild;
    TreeNode* rightchild;
};
struct QueueNode{    //队列结构体，记录队列中的节点
    TreeNode *parent;
    bool isleft;     //记录是否已经访问该父节点的左节点
};
void buildtree(TreeNode* &root,queue<QueueNode*> &pos,char data){ //传入根节点、队列及数据，根和队列需要修改，故使用引用
    if(data!='#'){   //输入如果不是#，证明还有子节点
        TreeNode *pNew = new TreeNode; //申请一个树节点
        pNew->data = data;
        QueueNode *pQueueNode = new QueueNode; //申请一个队列节点
        pQueueNode->parent = pNew; //队列节点的父节点指针指向刚创建的节点
        pQueueNode->isleft=false;
        pos.push(pQueueNode);   //压入队列
        if(root==NULL){ //队列初始为空，就把root指针初始化指向pNew节点
            root=pNew;
        }
        else{ //不为空，则根据isleft变量的数值判断插入左子树还是右子树，左子树指向完成后修改isleft，右子树指向完成后弹出父节点，同时删除临时节点指针pCur
            QueueNode* pCur=pos.front();
            if(pCur->isleft==false){
                pCur->parent->leftchild = pNew;
                pCur->isleft= true;
            }
            else{
                pCur->parent->rightchild = pNew;
                pos.pop();
                delete pCur;
            }
        }
    }
    else{
        if(root!= NULL){
            QueueNode* pCur=pos.front();
            if(pCur->isleft!=false){
                pCur->parent->leftchild = NULL;
                pCur->isleft = false;
            }
            else{
                pCur->parent->rightchild = NULL;
                pos.pop();
                delete pCur;
            }
        }
    }

}
int main(){
    TreeNode *root=NULL;
    char data;
    queue<struct QueueNode *> pos;
    while(1){
        scanf("%c",data);
        if(data=='\n') break;
        buildtree(root,pos,data);
        }
    return 0;
}