判断是否为完全二叉树

/*-------二叉树的二叉链结点结构定义------*/

#define TElemType char


typedef struct BiTNode{          // 结点结构
    TElemType data;             // 结点数据
    struct BiTNode *lchild, *rchild;    // 左右 孩子指针
} BiTNode, *BiTree;

/*-------队列的数据结构定义------*/

#define MAXSIZE 1000


typedef struct {
    BiTree data[MAXSIZE];
    int front;
    int rear;
}SqQueue;

*----------以下为队列的基本操作函数----------*/

/*初始化一个空队列*/
Status InitQueue(SqQueue *Q){
    if (!Q)return ERROR;             //若空间分配失败，则返回ERROR
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

/*判断SqQueue是否为空*/
Status IsQueueEmpty(SqQueue Q){
    if (Q.rear == Q.front)return TRUE;           //若尾指针指向头指针，则为空队列，返回TRUE
    else{ return FALSE; }                        //否则返回FALSE     
}

/*插入元素e为新的队尾元素*/
Status EnQueue(SqQueue *Q, BiTree e){
    if ((Q->rear + 1)  == MAXSIZE)return ERROR;    // 若队列已满，则返回ERROR
    Q->data[Q->rear] = e;           //e 入队列 
    Q->rear = (Q->rear + 1);                      //队尾指针后移
    return OK;
}

/*若队列不空，则删除队头元素，并用e返回其值*/
Status DeQueue(SqQueue *Q, BiTree *e){

    if (Q->front == Q->rear)return ERROR;    //若队列为空，则返回ERROR
    *e = Q->data[Q->front];                 //若队列不为空，用e接收队头元素
    Q->front = Q->front + 1;        //队头指针后移

    return OK;
}
/*----------队列的基本操作函数结束----------*/

/*-----------基本操作的函数-------------*/
//按照二叉树的定义初始化一个空树
Status InitBiTree(BiTree *bt){

    *bt = (BiTree )malloc(sizeof(BiTNode));
    if (!bt)return OVERFLOW;

    *bt = NULL;

    return OK;
}

//构造二叉链表表示的二叉树T
//按先序次序输入二叉树中结点的值（一个字符）,空格字符表示空树
Status CreateBiTree(BiTree *T){
    TElemType ch;

    printf_s("请输入数据：");
    scanf_s("%c", &ch);
    getchar();                      //getchar()用于处理回车占字符的问题
    if (ch == '#')
        *T = NULL;
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));

        if (!T)return OVERFLOW; // 若内存分配失败，则返回OVERFLOW

        (*T)->data = ch;            // 生成根结点
        CreateBiTree(&((*T)->lchild));  //构建左子树
        CreateBiTree(&((*T)->rchild));  //构建右子树
    }

    return OK;
}

Status IsCompleteBiTree(BiTree T){
    if (!T)return TRUE;             // 若为一个空树，则直接结束

    int flag = 0;               //设立一个flag，若某结点有左右孩子则为0;若某一个空了，则为1

    SqQueue Q;
    BiTree* e;
    e = (BiTree *)malloc(sizeof(BiTree));

    InitQueue(&Q);
    EnQueue(&Q, T);             //将根结点入队列

    while (DeQueue(&Q, e)){     //当队列不空时
        if (!(*e)){             //若当前元素为空，则flag = 1，直接进行下一个循环
            flag = 1;
            continue;
        }else if (flag){        //若当前元素不为空，且flag == 1，则证明该数不为完全二叉树
            return FALSE;
        }else{
            EnQueue(&Q, (*e)->lchild);
            EnQueue(&Q, (*e)->rchild);
        }
    }


    printf_s("\n");
    return TRUE;
}