要判断是不是完全二叉树，首先要知道什么是完全二叉树？ 完全二叉树：如果一棵具有N个结点的二叉树的结构与满二叉树的前N个节点的结构相同，称为完全二叉树。 所以就分了以下几种情况： 该节点有左右子树，继续判断 该节点只有左子树，判断他的下一个节点还有没有子树，如果有就不是 该节点只有右子树，不是 该节点左右子树都没有，判断他的下一个节点还有没有子树，如果有就不是
所以，以下就是代码：
using namespace std; template <class T> struct BinaryTreeNode//定义二叉树的节点 { BinaryTreeNode(const T& value) :_value(value) ,_pLeft(NULL) ,_pRight(NULL) {} T _value; BinaryTreeNode<T>* _pLeft; BinaryTreeNode<T>* _pRight; }; template<class T> class BinaryTree//定义二叉树 { typedef BinaryTreeNode<T> Node; public: BinaryTree() :_pRoot(NULL) {} private: Node* _pRoot;//根节点 }; bool IsCompleteBinaryTree() { if(_pRoot == NULL) return true; queue<Node*> q; q.push(_pRoot); bool flag = false; while(!q.empty()) { Node* pCur = q.front(); if(flag == true) { if(pCur->_pLeft || pCur->_pRight)//如果该结点的左或右孩子存在 return false; } if(pCur->_pLeft && pCur->_pRight)//左右孩子都存在 { q.push(pCur->_pLeft); q.push(pCur->_pRight); } else if(pCur->_pLeft)//只有左孩子，判断下一个节点是否存在左右孩子 { q.push(pCur->_pLeft); flag = true; } else if(pCur->_pRight)//只有右孩子，不能构成完全二叉树 { return false; } else//左右孩子都不存在，需要判断下一个个节点是否存在左右孩子 flag = true; q.pop(); } return true; }