//
// Created by zhuoL on 2021/11/1.
//

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

//树节点
typedef struct TreeNode {
    struct TreeNode *left, *right;
    char data;
} TreeNode, *pTreeNode;
//队列节点
typedef struct QueueNode {
    TreeNode *data;
    struct QueueNode *next;
} QueueNode, *pQueueNode;
//队列
typedef struct Queue {
    pQueueNode front, rear;
} Queue, *pQueue;

///先序遍历输入一棵二叉树(使用一级指针创建)
TreeNode *createBiTree(TreeNode *root) {
    char ch;
    scanf("%c", &ch);
    if (ch == '.') {
        return NULL;
    }
    root = malloc(sizeof(TreeNode));
    root->data = ch;
    root->left = createBiTree(root);
    root->right = createBiTree(root);
    return root;
}

///建立只有头结点的队列
Queue *initQ(Queue *queueNode) {
    queueNode->front = (pQueueNode) malloc(sizeof(QueueNode));
    if (queueNode->front == NULL)//判断内存分配是否成功
    {
        printf("内存分配不成功！");
    } else {
        queueNode->front->next = NULL;//队列的front和rear的next初始化为空
        queueNode->rear = queueNode->front;
        return queueNode;
    }
}

///把二叉树的数据取出放入队列
void enqueue(Queue *queueNode, TreeNode *data) {
    QueueNode *newNode = malloc(sizeof(QueueNode));
    newNode->data = data;//二叉树的数据存入队列
    newNode->next = NULL;
    queueNode->rear->next = newNode;//尾插法建立连接
    queueNode->rear = newNode;//rear更新
}

///出队：删除队列第一个元素
TreeNode *dequeue(Queue *queueNode) {
    QueueNode *pTemp = (pQueueNode) malloc(sizeof(QueueNode));
    pTemp = queueNode->front->next;
    //只剩下1个节点（不含队列空的头结点）
    if (pTemp->next == NULL) {
        queueNode->rear = queueNode->front;
    } else {
        queueNode->front->next = pTemp->next;//front+1（从指向第1个非空节点改为指向第2个节点）
    }
    TreeNode *x;
    x = pTemp->data;//x为队列第一个元素的data
    free(pTemp);
    return x;
}

/层序输出
/**
 * 1.初始化并创建一个队列
 * 2.让二叉树的根节点入队
 * 3.当队列不为空时元素出队并将出队节点的左右孩子入队(当他们不为NULL时)
 * 4.重复步骤二三直至队列为空
 * @param root 
 */
void LevelOrderBiTree(TreeNode *root) {
    ///初始化并创建一个队列
    Queue *queueNode = malloc(sizeof(Queue));
    queueNode = initQ(queueNode);
    ///取出二叉树的根节点，子节点存入队列
    enqueue(queueNode, root);
    ///当队列不为空
    while (queueNode->rear != queueNode->front) {
        TreeNode *x = dequeue(queueNode);//x用于输出队列弹出元素的数据
        printf("%-2c", x->data);
        if (x->left != NULL) {
            enqueue(queueNode, x->left);//递归左节点
        }
        if (x->right != NULL) {
            enqueue(queueNode, x->right);//递归右节点
        }
    }
}

int main() {
    TreeNode *root = createBiTree(root);
    LevelOrderBiTree(root);
    return 0;
}