//按照完全二叉树的层次顺序一次输入节点信息建立二叉链表的算法

//按照完全二叉树的层次顺序一次输入节点信息建立二叉链表的算法


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

typedef char DataType;

typedef struct node
{
    DataType data;
    struct node* lchild, * rchild;
} BinTNode;

typedef BinTNode* BinTree;



BinTree CreateBinTree(BinTree bt)
{
    //Q[1....n] 是一个BinTNode类型的指针数组，front和rear分别是对头和队尾指针
    BinTree Q[100];
    BinTree s;
    int front, rear;
    char ch;
    ch = getchar();
    bt = NULL;
    front = 1; rear = 0;
    while (ch != '#')
    {
        s = NULL;
        if (ch != "@")
        {
            s = (BinTNode*)malloc(sizeof(BinTNode));
            s->data = ch;
            s->lchild = s->rchild = NULL;

        }

        rear++; //队尾指针自增
        Q[rear] = s;
        
        printf("队尾-------第（%d）位:", rear);
        printf("%c\n",s->data);
        if (rear == 1) {
            bt = s;
        } else {
            if (s != NULL && Q[front] != NULL)
            {
                if (rear % 2 == 0)
                {
                    Q[front]->lchild = s;
                    printf("双亲节点（%d）位的左分支：%c\n", front, s->data);
                }
                else {
                    Q[front]->rchild = s;
                    printf("双亲节点（%d）位的右分支：%c\n", front, s->data);
                }
                if (rear % 2 != 0)
                {
                    front++; //rear为奇数，说明front所指节点的左右儿子都处理完了，因此front加1指向下一个双亲
                }

            }
        }
        getchar();
        ch = getchar();
    }//end while
    return bt;
}


int main()
{
    BinTree bt=NULL;
    CreateBinTree(bt);
    return 0;
}