判断二叉树是否为完全二叉树
【摘要】 判断二叉树是否为完全二叉树我们刚刚学过了二叉树的层序遍历，下面就有一个问题就很适合利用层序遍历来解决。我们来看一下：就是判断一棵二叉树是否为完全二叉树。那如何判断呢？解这道题的关键就在于我们要熟悉完全二叉树的一个特点：就是完全二叉树的前n-1层一定是满的，最后一层可以不满，但是必须连续。1. 思路讲解那思路是什么呢？就是对给定的二叉树进行层序遍历，判断其所有结点是否连续。详细步骤如下：首先就...
判断二叉树是否为完全二叉树
我们刚刚学过了二叉树的层序遍历，下面就有一个问题就很适合利用层序遍历来解决。
我们来看一下：
就是判断一棵二叉树是否为完全二叉树。
那如何判断呢？
解这道题的关键就在于我们要熟悉完全二叉树的一个特点：
就是完全二叉树的前n-1层一定是满的，最后一层可以不满，但是必须连续。
1. 思路讲解
那思路是什么呢？
就是对给定的二叉树进行层序遍历，判断其所有结点是否连续。
详细步骤如下：
首先就是层序遍历的步骤，我们先让根结点入队列，然后如果队列不为空，就出对头数据，并把对头数据的孩子结点带入队列，到这里要注意，我们上面层序遍历的时候如果结点的左孩子或右孩子为空，我们没有让它入队列（其实就是选择不打印空NULL罢了），但是在这里为了后面的判断，必须把空孩子也入队列。
这样一直循环往复，什么时候结束呢？
当出队列出出到空就结束，然后进行判断
此时队列中如果全为空，则表明是完全二叉树。
若存在不为空的：
则说明其结点不连续，不是完全二叉树。
🆗，这就是整体的一个思路。
2. 代码实现
下面我们写一下代码：
// 判断二叉树是否是完全二叉树
bool BinaryTreeJudge(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
🆗，就完成了，我们测试一下：
这是我们当前项目里创建的二叉树：
它不是完全二叉树，判断正确
我们把它改成完全二叉树，再来测试一下：
在2的右边再链接一个结点：
没问题。
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）