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

#define MaxSize 100

# 顺序存储适应于完全二叉树
typedef struct Node1 {
    int value;
    int isEmpty;
} BiTNode1, SBiTree[MaxSize];

void InitBiTree1(SBiTree t) {
    for (int i = 0; i < MaxSize; i++) {
        t[i].isEmpty = 1;
    }
}

typedef struct Node {
    int data;
    struct Node *lchild, *rchild;
} BiTNode, *BiTree;

BiTNode * Generate(int val) {
    BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
    p->data = val;
    p->lchild = NULL;
    p->rchild = NULL;
    return p;
}

BiTree InitBiTree() {
    BiTNode *root = Generate(1);
    BiTNode *p2 = Generate(2);
    root->lchild = p2;
    BiTNode *p3 = Generate(3);
    root->rchild = p3;
    BiTNode *p4 = Generate(4);
    p2->rchild = p4;
    BiTNode *p6 = Generate(6);
    p3->lchild = p6;
    BiTNode *p7 = Generate(7);
    p3->rchild = p7;
    BiTNode *p11 = Generate(11);
    p4->rchild = p11;
    BiTNode *p12 = Generate(12);
    p6->lchild = p12;
    return root;
}

void PreOrder(BiTree t) {
    if (t != NULL) {
        printf("%i\n", t->data);
        PreOrder(t->lchild);
        PreOrder(t->rchild);
    }
}

void InOrder(BiTree t) {
    if (t != NULL) {
        InOrder(t->lchild);
        printf("%i\n", t->data);
        InOrder(t->rchild);
    }
}

void PostOrder(BiTree t) {
    if (t != NULL) {
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        printf("%i\n", t->data);
    }
}

int TreeDepth(BiTree t) {
    if (t == NULL) {
        return 0;
    } else {
        int l = TreeDepth(t->lchild);
        int r = TreeDepth(t->rchild);
        return l > r ? l+1 : r+1;
    }
}

typedef struct QNode {
    BiTNode *data;
    struct QNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

void InitQueue(LinkQueue *q) {
    q->front = q->rear = NULL;
}

int EnQueue(LinkQueue *q, BiTNode *e) {
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    if (s == NULL) return -1;
    s->data = e;
    s->next = NULL;
    if (q->front == NULL) {
        q->front = q->rear = s;
    } else {
        q->rear->next = s;
        q->rear = s;
    }
    return 1;
}

int DeQueue(LinkQueue *q, BiTree *e) {
    if (q->front == NULL) return -1;
    LinkNode *p = q->front;
    q->front = p->next;
    *e = p->data;
    if (q->rear == p) {
        q->front = NULL;
        q->rear = NULL;
    }
    free(p);
    return 1;
}

int IsEmpty(LinkQueue q) {
    if (q.front == NULL) return 1;
    else return -1;
}

void LevelOrder(BiTree t) {
    LinkQueue q;
    InitQueue(&q);
    BiTree p = NULL;
    EnQueue(&q, t);
    while (IsEmpty(q) == -1) {
        DeQueue(&q, &p);
        printf("%i\n", p->data);
        if (p->lchild != NULL) {
            EnQueue(&q, p->lchild);
        }
        if (p->rchild != NULL) {
            EnQueue(&q, p->rchild);
        }
    }
}

int main() {
    BiTree t = InitBiTree();
    LevelOrder(t);
    return 0;
}