110.【C语言】数据结构之判断是否为完全二叉树

目录

1.知识回顾

2.分析

完全二叉树队列示意图

 非完全二叉树队列示意图

区别

3.代码

执行过程

完整代码

运行结果

---

1.知识回顾

完全二叉树和非完全二叉树参见100.【C语言】数据结构之二叉树的基本知识文章

2.分析

使用层序遍历(队列),核心思想参见109.【C语言】数据结构之二叉树层序遍历文章

这里对比完全二叉树和非完全二叉树在层序遍历中的区别

注意:和以往的层序遍历有所不同,空节点也要push(push它的地址NULL)

完全二叉树队列示意图

 非完全二叉树队列示意图

区别

当两个队列的队头为NULL时,观察两个队列之间的区别

完全二叉树:元素全为空

非完全二叉树:有非空元素

可以此来判断是否为完全二叉树

3.代码

执行过程

初始化队列-->非空树,将根节点的地址入队-->层序遍历+出栈+入栈-->对队头的值判断(为NULL则一直出队,遇到非空则销毁队列+返回false)

层序遍历+出栈+入栈

根节点出栈,出栈前需要保留根节点的地址,以便于左右节点入栈(front->left和front->right,不是root->left和root->right)

大概的结构

		BTNode* front = QueueFront(&q);QueuePop(&q);QueuePush(&q,front->left);QueuePush(&q,front->right);

疑问1:不是对根节点的左右节点入栈吗?为什么不写成root->left和root->right呢?
root一直是整个二叉树根节点的地址,导致root->left和root->right的值一直没有变化,导致死循环

如果写成front->left和front->right,每次循环时,front的值会改变(依据队头的值进行调整)

	while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL) break;QueuePush(&q,front->left);QueuePush(&q,front->right);}

最终当队头为NULL时,退出循环

疑问2:第一个while的部分能写成下面这两种吗?

BTNode* front = QueueFront(&q);
while (1)
{front = QueueFront(&q);QueuePop(&q); if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);
}

	while (QueueFront(&q)){BTNode*  front = QueueFront(&q);QueuePop(&q); if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}

两种写法均可以,while循环退出的唯一出口在if (front==NULL),由于NULL也入队,因此不存在队列为空的情况

完整代码

bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL) break;QueuePush(&q,front->left);QueuePush(&q,front->right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;	
}

注意返回前养成好习惯,需要销毁队列

main.c写入

int main()
{BTNode* root = CreateTree();printf("TreeComplete:%d", TreeComplete(root));return 0;
}

备注:创建的二叉树的结构为

运行结果