【数据结构】二叉树——判断是否为完全二叉树

一、思路

有完全二叉树的解释
我们想要判断二叉树是否为完全二叉树
我们可以用队列来实现
我们先将根节点入队列
再将根节点出队列，判断取出节点是否为空、

若不为空将该节点的左右节点入队列
左右节点为空也入队列

若为空则停止入队列
然后判断队列中是否有 NULL

若有则说明不是完全二叉树
若没有则说明是完全二叉树

二、代码实现

队列的代码

//判断是否为完全二叉树
bool BTComplete(BTNode* php)
{//创建队列Queue p;QueueInit(&p);//将根节点入栈QueuePush(&p, php);while (!QueueEmpty(&p)){//取出队首节点并删除QueueDateType cp = QueueFront(&p);QueuePop(&p);//判断取出节点是否为空if (cp == NULL){break;}//将左右节点入队列QueuePush(&p, cp->left);QueuePush(&p, cp->right);}//判断队列中是否有其他元素while (!QueueEmpty(&p)){//取出队首节点并删除QueueDateType cp = QueueFront(&p);QueuePop(&p);//判断节点中是否有数据if (cp != NULL){QueueDesTroy(&p);return false;}}//队列销毁QueueDesTroy(&p);return true;
}