1.使用队列的方式,通过入队元素的规律来判断,(如果是完全二叉树,使用层次遍历的方法,如果父节点存在,不管左右子树是否存在都入队列,如果遍历栈中的元素遇到第一个空的结点,后续结点应该都是空,如果有非空结点则说明不是完全二叉树)
bool BinaryTree<T>::isCompleteBinaryTreeQueue()
{
std::queue<Node*> queue_;
Node* curNode = NULL;
if (_root)
{
queue_.push(_root);
while (!queue_.empty())
{
curNode = queue_.front();
queue_.pop();
if (!curNode) // 遇到空结点直接退出当前循环
break;
queue_.push(curNode->_left);
queue_.push(curNode->_right);
}
while (!queue_.empty())
{
curNode = queue_.front();
queue_.pop();
if (curNode)
return false;
}
}
return true;
}
2.使用标记法,如果遇到一个结点存在一个空结点(如果只存在右孩子则一定不是完全二叉树),如果是完全二叉树,后续结点的孩子节点将不存在。只需要记录第一个有空的孩子结点的结点,遇到下一个结点存在孩子,说明不是完全二叉树 。
bool BinaryTree<T>::isCompleteBinaryTreeFlag()
{
std::queue<Node*> queue_;
if (_root)
{
queue_.push(_root);
Node* curNode = nullptr;
bool flag = false;
while (!queue_.empty())
{
curNode = queue_.front();
queue_.pop();
if (curNode)
{
// 以下if 不是并列关系注意
// 如果这几个if 没有else 那么①的if 一定要在② 后面 否则会出错
if (curNode->_left == NULL && curNode->_right != NULL)
return false;
// 前面的结点已经存在空结点
else
if (flag && (curNode->_left || curNode->_right)) //①
return false;
// 遇到有空子树的父节点做标记
else if (curNode->_left == NULL || curNode->_right == NULL) // ②
{
flag = true;
}
if (curNode->_left)
queue_.push(curNode->_left);
if (curNode->_right)
queue_.push(curNode->_right);
}
}
}
return true;
}