判断完全二叉树、满二叉树 - C语言（严蔚敏《数据结构》6.49 ）

题目来源：严蔚敏《数据结构》C语言版本习题册 6.49

// 6.49 编写算法判别给定二叉树是否为完全二叉树
int BiTreeIsComplete(BiTree root) {// 判断二叉树是否是完全二叉树
    // 思路：完全二叉树的层次遍历应没有NULL 或者说 在完全二叉树包括空指针的层次遍历中NULL在最后面
    // 操作：对完全二叉树进行层次遍历（包括空指针）。若遍历途中出现空指针，则标记为flag=1。在遍历途中如果是非空结点，而且flag=0，则不是二叉树
    BiTNode *que[MAXSIZE]; int front,rear; //定义一个队列
    BiTree p;
    int flag=0; //标识前面是否出现过空指针
    if (root==NULL) return 1; //临界条件不要丢：空树也是完全二叉树
    front=rear=0;
    que[rear]=root; rear=(rear+1)%MAXSIZE; //根指针入队列
    while (front!=rear) {
        p=que[front]; front=(front+1)%MAXSIZE; //出队列
        if (p==NULL) { //此指针是空指针
            flag=1; //标记出现过空指针
        } else { //此指针是非空结点
            if (flag) return 0; //之前出现过空指针，不是完全二叉树
            // 不判断p的孩子是否为空指针，直接队列
            que[rear]=p->lchild; rear=(rear+1)%MAXSIZE; 
            que[rear]=p->rchild; rear=(rear+1)%MAXSIZE;
        }
    }
    return 1;
}
int BiTreeIsFull(BiTree root) {// 判断二叉树是否是满二叉树
    // 思路：首先它是完全二叉树，并且结点总数sum=2^n-1
    // 操作：在判断完全二叉树的途中记录结点个数，然后判断sum=2^n-1是否满足
    /* 补充知识：判断数num是否是2^k --> !( num&(num-1) )
       [理解] 若num是2的k次方，那么它二进制只有一位是1-->举例0100。那num-1=0011。0100&0011=0000
    */
    BiTNode *que[MAXSIZE]; int front,rear;
    BiTree p;
    int flag=0; //标记之前是否出现了空指针
    int sum=0; //结点总数
    front=rear=0;
    que[rear]=root; rear=(rear+1)%MAXSIZE;
    ++sum;
    while (front!=rear) {
        p=que[front]; front=(front+1)%MAXSIZE;
        if (p==NULL) flag=1; //出现了空指针
        else {
            if (flag) return 0;
            ++sum;
            que[rear]=p->lchild; rear=(rear+1)%MAXISZE;
            que[rear]=p->rchild; rear=(rear+1)%MAXISZE;
        }
    }
    // 检查sum=2^n-1 --> sum+1是2的n次方
    sum = sum+1;
    if ( !( sum&(sum-1) ) ) return 1; //检查数num是否为2的k次方
    else return 0;
}