判断是否为完全二叉树

题目要求及思路分析

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

算法实现

  1. 二叉树及队列的结构体定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /*-------二叉树的二叉链结点结构定义------*/
    #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. 队列的基本操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    /*----------以下为队列的基本操作函数----------*/

    /*初始化一个空队列*/
    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;
    }
    /*----------队列的基本操作函数结束----------*/
  3. 二叉树的基本操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    /*-----------基本操作的函数-------------*/
    //按照二叉树的定义初始化一个空树
    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. 判断二叉树是否为完全二叉树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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;
    }