首先，看一下完全二叉树的定义：
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
思路：可以采用广度优先的遍历方法，从根节点开始将所有的节点按层添加到队列里面，当遇到第一个没有左儿子或者右儿子的节点时，设置标志位，继续遍历，如果后面遇到了有子节点的节点，则不是完全二叉树。
代码：
//二叉树结点定义
typedef struct Node
{
int data;
struct Node* left;
struct Node* right;
}Node;
//实现广度遍历需要队列
Queue queue;
//第n层最右节点标志
bool leftMost = false;
bool ProcessChild(Node* child)
{
if (child)
{
if (!leftMost)
queue.push(child);
else
return false;
}
else
{
leftMost = true;
}
return true;
}
bool IsCompleteBinaryTree(Node* root)
{
//空树也是完全二叉树
if (!root)
return true;
//首先根节点入队列
queue.push(root);
while(!queue.empty())
{
Node* node = queue.pop();
//处理左节点
if (!ProcessChild(node->left))
return false;
//处理右节点
if (!ProcessChild(node->right))
return false;
}
//广度优先遍历完毕，此乃完全二叉树
return true;
}