判断完全二叉树：

完全二叉树，除最后一层外，每一层上的节点树都达到了最大值；在最后一层上只缺少右边的若干节点！

算法思路：

按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左
右子树都必须为空，否则不是完全二叉树。

代码：

bool IsCompleteBTree(BTree* pRoot){	if (pRoot == NULL)		return false;	queue<BTree *> q;	q.push(pRoot);	bool mustHaveNoChild = false;	bool result = true;	while (!q.empty())	{		BTree* pNode = q.front();		q.pop();		if (mustHaveNoChild)//如果一个节点没有子节点;只要出现了空子树的节点，后面出现的必须为叶子节点（左字树右子树必须为空）		{			if (pNode->m_nLeft != NULL || pNode->m_nRight != NULL)			{				result = false;				break; 			}		}		else		{			if (pNode->m_nLeft != NULL && pNode->m_nRight != NULL)			{				q.push(pNode->m_nLeft);				q.push(pNode->m_nRight);			}			else if (pNode->m_nLeft != NULL && pNode->m_nRight == NULL)			{				mustHaveNoChild = true;				q.push(pNode->m_nLeft);			}			else if(pNode->m_nLeft == NULL && pNode->m_nRight != NULL)			{				result = false;				break;			}			else			{				mustHaveNoChild = true;			}		}	}	return result;}

完整测试代码：

// IsCompleteBTree.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <queue>using namespace std;//节点的数据结构class BTree{public:	int       m_nValue;	BTree*    m_nLeft;	BTree*    m_nRight;public:	BTree(int value)	{		m_nValue = http://www.mamicode.com/value;>


 
C++算法之 判断是否为完全二叉树