#ifndef _BITREE_H
#define _BITREE_H

#include "elemtype.h"
#include "linkqueue.h"
#include "queue.h"

#ifndef BITREE
#define BITREE

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;
#endif


#endif


////////////////////////////////
#ifndef _COMMON_H
#define _COMMON_H

/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1

/*Turbo c math.h中已定义OVERFLOW的值为3 */
/*see http://predef.sourceforge.net/precomp.html#sec2*/
#ifndef  __TURBOC__
#define OVERFLOW -2
#else
#endif

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

#endif


/////////////////////////////////////////



/* c3-2.h 单链队列－－队列的链式存储结构 */
#ifndef _LINKQUEUE_H
#define  _LINKQUEUE_H

typedef char QElemType; /* 队列的元素类型 */
typedef int Status;


typedef struct QNode {
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front, rear; /* 队头、队尾指针 */
} LinkQueue;

typedef LinkQueue Queue;

#endif


/////////////////////////////////////////////////


#include<stdio.h>
#include"linkqueue.h"
#include"common.h"
#include<math.h>


void InitQueue(LinkQueue *Q);
void DestroyQueue(LinkQueue *Q);
void ClearQueue(LinkQueue *Q);
Status QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead_Q(LinkQueue Q, QElemType *e);
void EnQueue(LinkQueue *Q, QElemType e);
Status DeQueue(LinkQueue *Q, QElemType *e);
void QueueTraverse(LinkQueue Q, void(*vi)(QElemType));

///////////////////////////////////////////////////






/* 链队列 的基本操作(9个) */
#include "queue.h"
#include <stdlib.h>
#include <stdio.h>

void InitQueue(LinkQueue *Q)
{
    /* 构造一个空队列Q */
    (*Q).front = (*Q).rear = (QueuePtr)malloc(20*sizeof(QNode));
    if(!(*Q).front)
        exit(OVERFLOW);
    (*Q).front->next = NULL;
}

void DestroyQueue(LinkQueue *Q)
{
    /* 销毁队列Q(无论空否均可) */
    while((*Q).front) {
        (*Q).rear = (*Q).front->next;
        free((*Q).front);
        (*Q).front = (*Q).rear;
    }
}

void ClearQueue(LinkQueue *Q)
{
    /* 将Q清为空队列 */
    QueuePtr p, q;
    (*Q).rear = (*Q).front;
    p = (*Q).front->next;
    (*Q).front->next = NULL;
    while(p) {
        q = p;
        p = p->next;
        free(q);
    }
}

Status QueueEmpty(LinkQueue Q)
{
    /* 若Q为空队列，则返回TRUE，否则返回FALSE */
    if(Q.front->next == NULL)
        return TRUE;
    else
        return FALSE;
}

int QueueLength(LinkQueue Q)
{
    /* 求队列的长度 */
    int i = 0;
    QueuePtr p;
    p = Q.front;
    while(Q.rear != p) {
        i++;
        p = p->next;
    }
    return i;
}

Status GetHead_Q(LinkQueue Q, QElemType *e) /* 避免与bo2-6.c重名 */
{
    /* 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR */
    QueuePtr p;
    if(Q.front == Q.rear)
        return ERROR;
    p = Q.front->next;
    *e = p->data;
    return OK;
}


void EnQueue(LinkQueue *Q, QElemType e)
{
    /* 插入元素e为Q的新的队尾元素 */
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) /* 存储分配失败 */
        exit(OVERFLOW);
    p->data =e;
    p->next = NULL;
    (*Q).rear->next = p;
    (*Q).rear = p;
}


Status DeQueue(LinkQueue *Q, QElemType *e)
{
    /* 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR */
    QueuePtr p;
    if((*Q).front == (*Q).rear)
        return ERROR;
    p = (*Q).front->next;
    *e = p->data;
    (*Q).front->next = p->next;
    if((*Q).rear == p)
        (*Q).rear = (*Q).front;
    free(p);
    return OK;
}


void QueueTraverse(LinkQueue Q, void(*vi)(QElemType))
{
    /* 从队头到队尾依次对队列Q中每个元素调用函数vi() */
    QueuePtr p;
    p = Q.front->next;
    while(p) {
        vi(p->data);
        p = p->next;
    }
    printf("\n");
}



//////////////////////////////////////////////////////////////


#include <stdio.h>
#include <stdlib.h>
#include "bitree.h"
#include "common.h"

void print_char(TElemType c)
{
    putchar(c);
}

void CreateBiTree(BiTree *T)
{
    /* 算法6.4：按先序次序输入二叉树中结点的值(此处字符型)*/
    /* 构造二叉链表表示的二叉树T。 */
    TElemType ch;
    scanf("%c", &ch);
    if(ch == ' ') /* 空 */
        *T = NULL;
    else {
        *T = (BiTree)malloc(sizeof(BiTNode)); /* 生成根结点 */
        if(!*T)
            exit(OVERFLOW);
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild); /* 构造左子树 */
        CreateBiTree(&(*T)->rchild); /* 构造右子树 */
    }
}

void InitBiTree(BiTree *T)
{
    /* 操作结果：构造空二叉树T */
    *T = NULL;
}

void DestroyBiTree(BiTree *T)
{
    /* 初始条件：二叉树T存在。操作结果：销毁二叉树T */
    if(*T) { /* 非空树 */
        if((*T)->lchild) /* 有左孩子 */
            DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
        if((*T)->rchild) /* 有右孩子 */
            DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
        free(*T); /* 释放根结点 */
        *T = NULL; /* 空指针赋0 */
    }
}
/*
void PreOrderTraverse(BiTree T, void(*Visit)(TElemType))
{
    /* 初始条件：二叉树T存在，Visit是对结点操作的应用函数。算法6.1，有改动 *
    /* 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
    if(T) { /* T不空 *
        Visit(T->data); /* 先访问根结点 
        PreOrderTraverse(T->lchild, Visit); /* 再先序遍历左子树 *
        PreOrderTraverse(T->rchild, Visit); /* 最后先序遍历右子树 *
    }
}

void InOrderTraverse(BiTree T, void(*Visit)(TElemType))
{
    /* 初始条件：二叉树T存在，Visit是对结点操作的应用函数 *
    /* 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次 *
    if(T) {
        InOrderTraverse(T->lchild, Visit); /* 先中序遍历左子树 *
        Visit(T->data); /* 再访问根结点 *
        InOrderTraverse(T->rchild, Visit); /* 最后中序遍历右子树 *
    }
}

void PostOrderTraverse(BiTree T, void(*Visit)(TElemType))
{
    /* 初始条件：二叉树T存在，Visit是对结点操作的应用函数 *
    /* 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次 *
    if(T) { /* T不空 *
        PostOrderTraverse(T->lchild, Visit); /* 先后序遍历左子树 *
        PostOrderTraverse(T->rchild, Visit); /* 再后序遍历右子树 *
        Visit(T->data); /* 最后访问根结点 *
    }
}*/

void BFSTree(BiTree T)
{
    LinkQueue Q;
    QElemType e;
    InitQueue(&Q);
    EnQueue(&Q,T->data);
    while(&Q){
        if(T->lchild)
            EnQueue(&Q,T->lchild->data);
        if(T->rchild)
            EnQueue(&Q,T->rchild->data);
        DeQueue(&Q, &e);
        printf("%c",e);        
    }
}

int main(void)
{
    BiTree t;

    InitBiTree(&t);
    
    //注意按p131要求的格式输入，例如"ABC  DE G  F   "
    CreateBiTree(&t);
    BFSTree(t);
/*    PreOrderTraverse(t, print_char);
    putchar('\n');

    InOrderTraverse(t, print_char);
    putchar('\n');

    PostOrderTraverse(t, print_char);
    putchar('\n');*/
    
    DestroyBiTree(&t);
}



///////////////////////////////////////////////////