王道書 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;
}