如何判定一顆樹是完全二叉樹和滿二叉樹

　　滿二叉樹：一顆深度為k且有2^k-1個節點的二叉樹稱為滿二叉樹；

　　完全二叉樹：對滿二叉樹的結點進行連續編號，約定編號從根結點起，自上而下，自左至右。深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹編號從1至n的結點對應時，稱為完全二叉樹。如圖所示：

1. 判定完全二叉樹。判定一棵樹是不是完全二叉樹的思路是廣度遍歷該二叉樹，當出現NULL值時停止遍歷，如果此時還有沒有遍歷到的結點，那麼就說明該樹非完全二叉樹，因為有空洞。C++代碼如下：

#include "stdafx.h"
#include <list>
using namespace std;

struct Tree{
    Tree()
    {
        data = 0;
        pLeftChild = NULL;
        pRightChild = NULL;
    }

    int data;
    Tree* pLeftChild;
    Tree* pRightChild;
};

Tree* GetFrontPtr(std::list<Tree*> &q)
{
    if (q.empty())
    {
        return NULL;
    }
    else
    {
        Tree* pRet = q.front();
        q.pop_front();
        return pRet;
    }

    return NULL;
}

bool IsCompleteTree(Tree *pRoot)  
{  
    std::list<Tree*> q;
    Tree *ptr;  
    q.push_back(pRoot);  
    while ((ptr = GetFrontPtr(q)) != NULL)  
    {
        q.push_back(ptr->pLeftChild);  
        q.push_back(ptr->pRightChild);  
    }  

    while (!q.empty())  
    {  
        ptr = q.front();
        q.pop_front();
        if (NULL != ptr)  
        {  
            return false;  
        }  
    }  

    return true;  
}  
int _tmain(int argc, _TCHAR* argv[])
{
    Tree t1;
    Tree t2;
    Tree t3;
    Tree t4;
    Tree t5;
    Tree t6;
    Tree t7;
    Tree t8;
    Tree t9;
    Tree t10;
    t1.pLeftChild = &t2;
    t1.pRightChild = &t3;
    t2.pLeftChild = &t4;
    t2.pRightChild = &t5;
    t3.pLeftChild = &t6;

    bool ret = IsCompleteTree(&t1);
    return 0;
}

2. 判定滿二叉樹。判定一棵樹是否是滿二叉樹的思路類似，還是首先將二叉樹按照廣度優先的方法push到隊列裡邊（暫時不pop），然後開始pop，第一次pop，只pop一個元素，第二次pop1*2個元素，第三次pop1*2*2個元素，依次類推，如果該pop1*2^k個元素時，但是還沒有pop完，list就空了，那麼證明該樹為非滿二叉樹。代碼就不貼了。