84.png

    1. /*
    2.     一颗二叉树以二叉链表的形式存储，编写一个算法判断其是否是一个完全二叉树
    3.     分析：
    4.         我们仍然可以借助队列来完成这件事，具体做法为：我们依次将二叉树从上到下，从左到右入栈，包括空节点，如遇空节点，
    5.         若队列非空，则判断其后是否还存在节点，若有，则该树为非完全二叉树。
    6. */
    7. struct biTree {
    8.     char data;
    9.     struct biTree *lchild;
    10.     struct biTree *rchild;
    11. };
    12. struct Squeue {
    13.     biTree data;
    14.     int front, rear;
    15. };
    16. #include <stdio.h>
    17. #include <stdlib.h>
    18. bool isComplete(biTree *T, Squeue *sq, int maxSize) {
    19.     if (!T)return true;
    20.     bool enQueue(Squeue *, biTree *, int maxSize);
    21.     bool deQueue(Squeue *, biTree **, int maxSize);
    22.     bool isEmpty(Squeue *);
    23.     struct biTree *p = T;
    24.     struct biTree *r = (struct biTree*)malloc(sizeof(struct biTree));
    25.     enQueue(sq, p, maxSize);//根节点入队
    26.     while (!isEmpty(sq)) {
    27.         deQueue(sq, &r, maxSize);//取出队首元素
    28.         if (r) {
    29.             enQueue(sq, r->lchild, maxSize);
    30.             enQueue(sq, r->rchild, maxSize);
    31.         }
    32.         else {
    33.             while (!isEmpty(sq)) {//如果已经来到了空节点，判断后续是否还有节点
    34.                 deQueue(sq, &r, maxSize);//取出队首元素
    35.                 if (r) {
    36.                     return false;
    37.                 }
    38.             }
    39.         }
    40.     }
    41.     return true;
    42. }
    43. int main() {
    44.     int count = 0;
    45.     bool isCom;
    46.     struct biTree *T = (struct biTree*)malloc(sizeof(struct biTree));
    47.     struct Squeue *sq;
    49.     biTree *create(biTree *);
    50.     void nodeNum(biTree *, int *);
    52.     Squeue *createQueue(int);
    55.     T = create(T);//创建一颗二叉树
    56.     nodeNum(T, &count);//统计二叉树节点数量
    57.     sq = createQueue(count);//创建容量为二叉树节点个数大小的队列
    59.     isCom = isComplete(T, sq, count);
    60.     isCom ? printf("该二叉树是完全二叉树") : printf("该二叉树不是完全二叉树");
    61.     return 0;
    62. }