欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-05 20:09:40
...

层次遍历二叉树

分析:层次遍历二叉树也称广度优先遍历,是一层一层的遍历二叉树,可以借助队列,先进先出。
注:与前序遍历的非递归有点像,一个是栈,一个是队列

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