二叉树层序建树、遍历

树的结构体
typedef char BiElemType;
typedef struct BiTNode{
    BiElemType data;
    struct BiTNode *lchild; //左结点（左孩子）
    struct BiTNode *rchild; //右结点（右孩子）
}BiTNode,*BiTree;

辅助队列的作用是“避免遍历去插入新结点”，更精准的描述是：队列通过 “预存待分配的父结点”，让插入时无需遍历整棵树找父结点，而是直接从pcur指针取，同时保证层序规则。

队列的“先进先出”特性刚好匹配层序构建二叉树的父结点分配顺序；用队列的O(1)操作替代了无队列时的O(n)遍历，同时保证二叉树层序结构的正确性。

辅助队列结构体
typedef struct tag{
    BiTree p; //存储树的结点的地址
    struct tag *pnext;
}tag_t,*ptag_t;

BiTree pnew; //用来指向新申请的树结点
BiTree tree=NULL; //tree是指向树根的，代表树

// 辅助队列相关的指针
ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur;

char c;
//abcdefg
while (scanf("%c",&c)){
    if(c=='\n'){
        break; //读到换行就结束
    }
    // calloc申请的空间大小是两个参数直接相乘，并对空间进行初始化，赋值为0
    pnew=(BiTree)calloc(1,sizeof(BiTNode));
    pnew->data=c;

    // 给辅助队列结点申请空间
    listpnew=(ptag_t)calloc(1,sizeof(tag_t));
    listpnew->p=pnew;

    // 如果是树的第一个结点
    if(NULL==tree){
        tree=pnew; //tree指向树的根结点

        phead=listpnew; //第一个结点既是队列头，也是队列尾
        ptail=listpnew;
        pcur=listpnew; //pcur要指向要进入树的父亲元素
    } else{
        // 辅助队列，让 树结点的地址 元素先入队
        ptail->pnext=listpnew;
        ptail=ptail->pnext;
        // 把新节点放入树中
        if(pcur->p->lchild==NULL){ //pcur->p左孩子为空，就放入左孩子
            pcur->p->lchild=pnew;
        } else if(pcur->p->rchild==NULL){ //pcur->p右孩子为空，就放入右孩子
            pcur->p->rchild=pnew;
            pcur=pcur->pnext; //当前结点左右孩子都有了，就放入下一个结点
        }
    }
}

前序遍历，也叫先序遍历,也是深度优先遍历
void PreOrder(BiTree t){
    if(t!=NULL){
        printf("%c",t->data);
        PreOrder(t->lchild); //打印左子树
        PreOrder(t->rchild); //打印右子树
    }
}

中序遍历
void INOrder(BiTree t){
    if(t!=NULL){
        INOrder(t->lchild); //打印左子树
        printf("%c",t->data);
        INOrder(t->rchild); //打印右子树
    }
}

后序遍历
void PostOrder(BiTree t){
    if(t!=NULL){
        PostOrder(t->lchild); //打印左子树
        PostOrder(t->rchild); //打印右子树
        printf("%c",t->data);
    }
}