数据结构 ——— 判断一棵树是否是完全二叉树

目录

满二叉树和完全二叉树示意图

手搓一个完全二叉树

代码实现 

满二叉树和完全二叉树示意图

注意区分满二叉树和完全二叉树
满二叉树的每一层都是满的，也就是除了叶子节点，其他节点都有左右节点
完全二叉树的最后一层不一定是满的，但是从左到右是连续的

手搓一个完全二叉树

// 数据类型
typedef int BTDataType;

// 二叉树节点的结构
typedef struct BinaryTreeNode
{
	BTDataType data; //每个节点的数据

	struct BinaryTreeNode* left; //指向左子树的指针

	struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;

// 申请新节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

	// 判断是否申请成功
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	// 初始化
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

BTNode* CreatBinaryTree1()
{
	BTNode* n1 = BuyNode(1);
	assert(n1);
	BTNode* n2 = BuyNode(2);
	assert(n2);
	BTNode* n3 = BuyNode(3);
	assert(n3);
	BTNode* n4 = BuyNode(4);
	assert(n4);
	BTNode* n5 = BuyNode(5);
	assert(n5);
	BTNode* n6 = BuyNode(6);
	assert(n6);
	
	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	n3->left = n6;

	return n1;
}

代码实现

实现思路：

通过层序遍历来判断是否是完全二叉树
数据结构 ——— 层序遍历链式二叉树_层序遍历输出二叉树-CSDN博客
同样是需要一个队列来实现，从根节点开始，只要不是空就出队列，出队列前带入左右子树
当遇到空就截至，并且遍历队列中剩下的元素是否都为空
都为空的话那就是完全二叉树，否则就不是

实现前要先构建一个简易队列以及队列的基本函数： 

// 数据类型
typedef BTNode* QDataType;
 
// 链式队列每个节点的结构
typedef struct QueueNode
{
	struct QueueNode* next; //指向下一个节点的指针
 
	QDataType data; //当前节点的数据
}QNode;
 
// 链式队列的结构
typedef struct Queue
{
	QNode* phead; //指向队头节点的指针
 
	QNode* ptail; //指向队尾节点的指针
 
	int size; //队列的总数据个数
}Queue;
 
// 初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
 
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
 
// 数据入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
 
	// 申请新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
 
	// 判断是否申请成功
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
 
	// 初始化新节点
	newnode->data = x;
	newnode->next = NULL;
 
	if (pq->phead == NULL) //当队列中没有数据的情况
	{
		// 双重判断，更加保险
		assert(pq->ptail == NULL);
 
		// 头尾都指向新节点即可
		pq->phead = newnode;
		pq->ptail = newnode;
	}
	else //当队列已有数据的情况
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
 
	pq->size++;
}
 
// 数据出队列
void QueuePop(Queue* pq)
{
	assert(pq);
 
	// 当队列中没有数据的情况
	if (pq->phead == NULL)
	{
		perror(pq->phead);
		return;
	}
 
	if (pq->phead->next == NULL) //当队列中只有一个数据的情况
	{
		free(pq->phead);
		
		pq->phead = NULL;
		pq->ptail = NULL;
	}
	else //当队列中有多个数据的情况
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
 
	pq->size--;
}
 
// 访问队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
 
	// 当队列中没有数据的情况
	if (pq->phead == NULL)
	{
		perror(pq->phead);
		return -1;
	}
 
	return pq->phead->data;
}
 
// 判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
 
	return (pq->phead == NULL) && (pq->ptail == NULL);
}
 
// 释放队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
 
	QNode* cur = pq->phead;
 
	while (cur != NULL)
	{
		QNode* next = cur->next;
 
		free(cur);
 
		cur = next;
	}
 
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

代码实现：

bool BTreeComplete(BTNode* root)
{
	// 定义队列
	Queue q;
	// 初始化队列
	QueueInit(&q);

	// 先将二叉树的根节点的指针入队列
	if (root != NULL)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		// 访问队头数据
		BTNode* front = QueueFront(&q);

		// 判断是否为空
		if (front == NULL)
			break;

		// 队头数据出队列
		QueuePop(&q);

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	// 检查有没有非空节点
	while (!QueueEmpty(&q))
	{
		// 访问队头数据
		BTNode* front = QueueFront(&q);

		if (front != NULL)
		{
			// 返回前先销毁队列
			QueueDestroy(&q);

			return false;
		}

		QueuePop(&q);
	}

	QueueDestroy(&q);
	
	return true;
}

代码验证：