二叉树的层序遍厉

「这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」

//层序遍厉
void BinaryTreeLeveOrder(BTNode* root);
//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
复制代码

BinaryTreeLeveOrder：

🔑 核心思想 🔑

    使用队列的方式：先入第一层，出上一层，再入下一层 ... ...

    需要使用之前实现的队列

BinaryTreeComplete：

🔑 核心思想 🔑

    想必完全二叉树在此处出现一定跟层序有关系

    层序遍厉，把空也入队列

    完全二叉树，非空是连续的，空也是连续的

    非完全二叉树，非空就不是连续的，空也是不连续的

❗ 这里需要三个文件 ❕

    1️⃣ Queue_LeveOrder.h，用于函数的声明

#pragma once

//头
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>

//结构体
typedef struct BinaryTreeNode*  QDataType;
typedef struct QueueNode
{
	struct QueueNode* next; //指向下一个节点
	QDataType data; //存储整型数据
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;//头指针
	QueueNode* ptail;//尾指针
}Queue;

//函数
void QueueInit(Queue* pq); 
void QueuePush(Queue* pq, QDataType x);	
bool QueueEmpty(Queue* pq);
void QueuePop(Queue* pq);
QDataType QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueDestory(Queue* pq);
复制代码

    2️⃣ Queue_LeveOrder.c，用于函数的实现

#include"Queue_LeveOrder.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	//把2个指针置空
	pq->phead = pq->ptail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//malloc空间,如果需要频繁的开辟空间建议再实现一个BuyQueueNode用于malloc
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//第一次插入
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	//非第一次插入
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//空链表返回true，非空链表返回false
	return pq->phead == NULL;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	//链表为空时不能删除
	assert(!QueueEmpty(pq));
	//只有一个节点的情况
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个节点的情况
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead)	;
		pq->phead = next;
	}
}
QDataType QueueSize(Queue* pq)
{
	assert(pq);
	//如果需要频繁的调用QueueSize这个接口，可以在Queue这个结构体中增加一个成员用于记录长度
	int sz = 0;
	QueueNode* cur = pq->phead;
	while (cur)
	{
		sz++;
		cur = cur->next;
	}
	return sz;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//链表为空时不能取头
	assert(!QueueEmpty(pq));
	
	return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//链表为空时不能取尾
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	
	QueueNode* cur = pq->phead;
	//遍历链表
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}
复制代码

    3️⃣ Test.c，用于函数的测试

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

//从此处包含Queue.h文件
#include"Queue_LeveOrder.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;

	return node;
}
//创建二叉树
BTNode* BinaryCreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->_left = node2;
	node1->_right = node3;
	node2->_left = node4;
	node3->_left = node5;
	node3->_right = node6;

	return node1;
}
//层序遍厉
void BinaryTreeLeveOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		//入队列
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		//取队头的数据
		BTNode* front = QueueFront(&q);
		//出队
		QueuePop(&q);
		printf("%d ", front->_data);
		if (front->_left)
		{
			//入左子树
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			//入右子树
			QueuePush(&q, front->_right);
		}
	}
	printf("\n");
	QueueDestory(&q);
}
//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		//入队列
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		//取队头的数据
		BTNode* front = QueueFront(&q);
		//出队
		QueuePop(&q);
		//遇到空就break出去再判断
		if(front == NULL)
		{
			break;
		}
		//入左子树
		QueuePush(&q, front->_left);
		//入右子树
		QueuePush(&q, front->_right);
	}
	//队列中全是空，就是完全二叉树；还有非空，就不是完全二叉树
	while(!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//非空
		if(front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	//全是空
	QueueDestory(&q);
	return true;
}
//后序销毁二叉树
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestroy(root->_left);
	BinaryTreeDestroy(root->_right);
	free(root);
}
int main()
{
	BTNode* root = BinaryCreatBinaryTree();
	BinaryTreeLeveOrder(root);
	printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));
	BinaryTreeDestroy(root);
	root = NULL;
	return 0;
}
复制代码