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

typedef struct node {
    char data;
    struct node *lchild;
    struct node *rchild;
}NODE, *PNODE;

typedef struct qnode {
    PNODE pnode;
    struct qnode *next;
}QNODE, *PQNODE;

typedef struct queue {
    PQNODE front;
    PQNODE rear;
    int size;
}QUEUE, *PQUEUE;

PNODE CreateTree(void);
void initQueue(PQUEUE);
void enQueue(PQUEUE, PNODE);
bool deQueue(PQUEUE, PNODE *);
void levelTraversal(PNODE);

PNODE CreateTree(void)
{
    PNODE pA = (PNODE)malloc(sizeof(NODE));
    PNODE pB = (PNODE)malloc(sizeof(NODE));
    PNODE pC = (PNODE)malloc(sizeof(NODE));
    PNODE pD = (PNODE)malloc(sizeof(NODE));
    PNODE pE = (PNODE)malloc(sizeof(NODE));
    PNODE pF = (PNODE)malloc(sizeof(NODE));
    PNODE pG = (PNODE)malloc(sizeof(NODE));

    pA->data = 'A';
    pB->data = 'B';
    pC->data = 'C';
    pD->data = 'D';
    pE->data = 'E';

    pA->lchild = pB;
    pA->rchild = pC;
    pB->lchild = pB->rchild = NULL;
    pC->lchild = pD;
    pC->rchild = NULL;
    pD->lchild = NULL;
    pD->rchild = pE;
    pE->lchild = pE->rchild = NULL;

    return pA;
}

void initQueue(PQUEUE pQ) {
    pQ->front = pQ->rear = (PQNODE)malloc(sizeof(QNODE));
    if (! pQ->front) {
        printf("init malloc error!\n");
        exit(-1);
    }
    pQ->front->next = NULL;
    pQ->size = 0;
}

void enQueue(PQUEUE pQ, PNODE pnode) {
    //printf("en_queue %c ", pnode->data);
    PQNODE pNew;
    pNew = (PQNODE)malloc(sizeof(QNODE));
    if (!pNew) {
        printf(" en_queue malloc error!\n");
        exit(-1);
    }
    pNew->pnode = pnode;
    pNew->next = NULL;

    pQ->rear->next = pNew;
    pQ->rear = pNew;
    pQ->size++;
    //printf(" success.\n");
}
bool deQueue(PQUEUE pQ, PNODE *ppnode) {
    //printf("de_queue...");
    PQNODE tmp;

    if (pQ->front->next == NULL) {
        printf(" failed, queue empty!\n");
        return false;
    }

    tmp = pQ->front->next;
    *ppnode = tmp->pnode;

    pQ->front->next = tmp->next;
    // 最后一個節(jié)點出隊特殊處理
    if (tmp->next == NULL)
        pQ->rear = pQ->front;
    free(tmp);
    pQ->size--;
    //printf("success, value: %c\n", (*ppnode)->data);
    return true;
}

void levelTraversal(PNODE pnode){
    if (pnode) {
        QUEUE Q;
        PNODE tmp;
        initQueue(&Q);
        enQueue(&Q, pnode);
        int levelSize, level;
        level = 0;
        while (Q.size) {
            sleep(1);
            level++;
            levelSize = Q.size;
            printf("traversal level %d have %d nodes:", level, levelSize);
            for (int i=0; i<levelSize; i++) {
                deQueue(&Q, &tmp);
                printf(" %c,", tmp->data);
                if (tmp->lchild)
                    enQueue(&Q, tmp->lchild);
                if (tmp->rchild)
                    enQueue(&Q, tmp->rchild);
            }
            printf("\n");
        }
    }
}


int main(void)
{
    PNODE T = CreateTree();
    printf("層序遍歷結果:\n");
    levelTraversal(T);

    return 0;
}