A-A+

判断二叉树是否为完全二叉树

2016年08月10日 Linux 教程 暂无评论 阅读 304 次

判断二叉树是否为完全二叉树。完全二叉树的定义是,前n-1层都是满的,第n层如有空缺,则是缺在右边,即第n层的最右边的节点,它的左边是满的,右边是空的。

这个问题的描述已经提示了解法,采用广度优先遍历,从根节点开始,入队列,如果队列不为空,循环。遇到第一个没有左儿子或者右儿子的节点,设置标志位,如果之后再遇到有左/右儿子的节点,那么这不是一颗完全二叉树。

这个方法需要遍历整棵树,复杂度为O(N),N为节点的总数。

#include<iostream>
#include<queue>
using namespace std;
bool leftMost =false;
queue<Node*> q;
bool ProcessChild(Node* node)
{
    if(node)
    {
        if(!leftMost)
        {
            q.push_back(node);
        }
        else
            return false;
    }
    else
        leftMost=true;
    return true;
}
bool IsCompleteBinaryTree(Node* root)//层序遍历 
{
    if(root==NULL)
        return true;
    q.push_back(root);
    while(!q.empty())
    {
        Node* node=q.pop();
        if (!ProcessChild(node->left)) 
            return false; 
   
        //处理右节点 
        if (!ProcessChild(node->right)) 
            return false; 
    }
    return true;
 
}

标签:

给我留言

Copyright © SEARU.ORG 保留所有权利.   Theme  Ality 网站地图 360网站安全检测平台

用户登录

分享到: