王道书 P149 T7（二叉树链式存储实现）

/**
 * 用二叉树链式存储实现 王道 P149 T7
 *
 * ①算法思想
 * 基于层次遍历的过程，如果一棵二叉树是完全二叉树，那么一定不存在有节点只有右孩子没有左孩子的情况。
 * 注：一定要基于层次遍历这个过程，因为单单是以“不存在有节点只有右孩子没有左孩子的情况”这一个条件的树是不能保证是完全二叉树的。
 * 
 * ②算法设计
 */


#include <stdio.h>
#include <iostream>
#define MaxSize 100

typedef struct BiTreeNode{
    int data;
    BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;

//P149 T7
bool IsCompleteBiTreeByLevel(BiTree T){
    BiTree Queue[MaxSize];//Queue用来存放树的指针
    BiTree p = T;
    int front = -1, rear = -1;
    Queue[++rear] = p;
    while(front != rear){//队列中还有元素
        p = Queue[++front];
//        Visit(p);
//        if(p -> lchild != NULL)
//            Queue[++rear] = p -> lchild;
//        if(p -> rchild != NULL)
//            Queue[++rear] = p -> rchild;
        //是空节点也要入队！
        if(p != NULL){//不管p的孩子为不为空，只要p不是空就把左右孩子入队
            Queue[++rear] = p -> lchild;
            Queue[++rear] = p -> rchild;
        }else{//当遇到一个NULL时，就要开始下面的判断了，判断这个NULL后面是否全是NULL
            while(front != rear){
                p = Queue[++front];
                if(p != NULL)//只要有一个是不为NULL，就不符合完全二叉树
                    return false;
            }
        }
    }
    return true;
}