【二叉树】层次遍历二叉树以及判断一棵树是否是完全二叉树

层次遍历二叉树

分析：层次遍历二叉树也称广度优先遍历，是一层一层的遍历二叉树，可以借助队列，先进先出。

注：与前序遍历的非递归有点像，一个是栈，一个是队列

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;
}