题目要求及思路分析

题目：编写算法判别给定二叉树是否为完全二叉树。 —-《数据结构习题集（C 语言版）》
思路：
- 使用层序遍历二叉树
- 若完全二叉树中的某个结点没有左孩子，则其一定没有右孩子
- 若完全二叉树中的某个结点缺左孩子或右孩子，则其一定没有后继结点
  算法实现

二叉树及队列的结构体定义 ```c /———-二叉树的二叉链结点结构定义———/
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;


2. 
队列的基本操作
```c
/*----------以下为队列的基本操作函数----------*/
/*初始化一个空队列*/
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;
}
/*----------队列的基本操作函数结束----------*/

二叉树的基本操作 ```c /—————-基本操作的函数——————-/ //按照二叉树的定义初始化一个空树 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;

}


4. 
判断二叉树是否为完全二叉树
```c
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;
}

瓦雀

一大堆数据

判断是否为完全二叉树

题目要求及思路分析

算法实现

define TElemType char

define MAXSIZE 1000