判断二叉树是否为完全二叉树-创新互联
判断二叉树是否为完全二叉树。完全二叉树的定义是，前n-1层都是满的，第n层如有空缺，则是缺在右边，即第n层的最右边的节点，它的左边是满的，右边是空的。
河东网站建设公司创新互联建站,河东网站设计制作，有大型网站制作公司丰富经验。已为河东1000+提供企业网站建设服务。企业网站搭建\成都外贸网站建设要多少钱，请找那个售后服务好的
河东做网站的公司定做！
这个问题的描述已经提示了解法，采用广度优先遍历，从根节点开始，入队列，如果队列不为空，循环。遇到第一个没有左儿子或者右儿子的节点，设置标志位，如果之后再遇到有左/右儿子的节点，那么这不是一颗完全二叉树。
这个方法需要遍历整棵树，复杂度为O(N)，N为节点的总数。
#include
#include
using namespace std;
bool leftMost =false;
queue 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;
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
本文名称：判断二叉树是否为完全二叉树-创新互联
链接URL：
http://kswjz.com/article/dsescd.html
扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
