【二叉樹】層次周遊二叉樹以及判斷一棵樹是否是完全二叉樹

層次周遊二叉樹

分析：層次周遊二叉樹也稱廣度優先周遊，是一層一層的周遊二叉樹，可以借助隊列，先進先出。

注：與前序周遊的非遞歸有點像，一個是棧，一個是隊列

void LevelOreder(Node *pRoot)
{
    cout << "層次周遊 "<<endl;
    if(pRoot == NULL)
        return ;
    queue<Node *> q;
    q.push(pRoot);
    while(!q.empty())
    {
        Node* pCur = q.front();
        cout << pCur->data << " ";
        q.pop();
        if(pCur->left)
            q.push(pCur->left);
        if(pCur->right)
            q.push(pCur->right);
    }
    cout << endl;
}
           

判斷一棵樹是否是完全二叉樹

分析問題

完全二叉樹的定義：前n-1層都是滿的，第n層如有空缺，則是缺在右邊，即第n層的最右邊的節點，它的左邊是滿的，右邊是空的。

思路：

方法1、

可以借助廣度優先周遊(層次周遊)，将所有的節點入隊，直到遇到一個空的節點，然後判斷剩餘的隊列中是否還有不為空的節點，如果剩餘隊列還有不為空的節點則該二叉樹不是完全二叉樹。

bool IsCompleteTree(Node *pRoot)
{
    if(pRoot == NULL)
        return true;
    queue<Node *> q;
    q.push(pRoot);
    Node *pCur = NULL;
    while((pCur = q.front()) != NULL)
    {
        q.pop();
        q.push(pCur->left);
        q.push(pCur->right);
    }
    //跳出循環，找到一個空的節點，
    q.pop();//目前節點為空 出隊
    //判斷如果隊列中還有不是空節點，說明不是完全二叉樹。
    while(!q.empty())
    {
        if(q.font() != NULL)
            return false;
        q.pop();
    }
    return true;
}
           

方法2、

思路：層次周遊二叉樹， 找到第一個非滿節點，如果之後的節點還有左右孩子的話，說明這個二叉樹不是一個完全二叉樹。

bool IsCompleteTree(Node *pRoot)
{
    if(pRoot == NULL)
        return ;
    queue<Node *> q;
    q.push(pRoot);
    bool flag = false;//标記是否有非滿節點
    while(!q.empty())
    {
        Node *pCur = q.front();
        q.pop();
        if(flag)//已經有非滿節點，後面的節點必須沒有孩子
        {
            if(pCur->left != NULL || pCur->right != NULL)
                return false;
        }
        else// 沒有非滿節點，找非滿節點
        {
            if(pCur->left != NULL && pCur->right != NULL）
            {
                q.push(pCur->left);
                q.push(pCur->right);
            }
            else if(pCur->left != NULL)//左不空 右空
            {
                q.push(pCur->left);
                flag = true;
            }
            else if(pCur->right != NULL)//左空 右不空
            {
                return false;

            }
            else//左右孩子都為空,葉子節點
            {
                flag = true;
            }
        }       
    }
    return true;
}