链式二叉树：用指针和递归编织树形结构的艺术

ll778811

1420人浏览 · 2025-02-08 23:38:16

ll778811 · 2025-02-08 23:38:16 发布

一.链式二叉树的概念与结构

如图为一棵二叉树，可以看出若以每个结点都为根节点，那么这些结点都有自己的左右子树，叶子节点的左右子树为空，所以链式二叉树也是一棵递归树，同时也可以看到在所有结点中，不存在度超过2的结点，并且每个结点均有左右之分，我们可以根据这两个性质定义二叉树结点的结构。

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

结构体中成员_data为树结点中保存的数据，_left为指向当前结点的左孩子结点的指针，_right为指向当前结点的右孩子结点的指针，这样定义之后每个结点通过指针连接起来，从而形成一棵二叉树。

二.链式二叉树接口的实现

所有接口函数一览：

// 通过前序遍历的数组构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树的高度/深度
int BinaryTreeDepth(BTNode* root);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

由于链式二叉树是一棵递归树，所以链式二叉树的实现会涉及大量的递归。

1.遍历

二叉树的遍历比较复杂，分为两大类：深度优先遍历和广度优先遍历。

深度优先遍历：

前序遍历

先去遍历根结点，再去遍历左子树，最后是右子树 -- 根左右。

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

若遍历到的所在子树的根结点为空，则直接打印NULL并返回。

若遍历到的所在子树的根结点不为空，则先打印根结点，然后再遍历左子树，最后是右子树。

图示：

可以看到若有一棵如图的二叉树，它的遍历详细过程如上图，其中红色的指示线为递归的过程，蓝色的指示线为函数返回回溯的过程。

打印结果为：

中序遍历

先去遍历左子树，再去遍历根结点，最后是右子树 -- 左根右。

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

若遍历到的所在子树的根结点为空，则直接打印NULL并返回。

若遍历到的所在子树的根结点不为空，则先遍历左子树，然后再打印根节点，最后遍历右子树。

图示： 上图则为中序遍历的递归过程，其打印结果为：

后序遍历

先去遍历左子树，再去遍历右子树，最后是根结点 -- 左根右。

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}

若遍历到的所在子树的根结点为空，则直接打印NULL并返回。

若遍历到的所在子树的根结点不为空，则先遍历左子树，然后再遍历右子树，最后遍历根结点。

图示：

上图则为后序遍历的递归过程，其打印结果为：

分析

比较三种遍历的代码，可以看到三者之间只是最后的三条语句位置互换，也对应了根结点的遍历先后位置。

广度优先遍历：

层序遍历

从上到下，从左到右，根据每一层的结点依次遍历。

void BinaryTreeLevelOrder(BTNode* root)

对于层序遍历，我们需要借助之前学过的一种数据结构 -- 队列。

Queue q;
QueueInit(&q);
QueuePush(&q, root);

首先创建队列并初始化，循环判断队列是否为空，在循环前，先将根结点入队列。

while (!QueueEmpty(&q))
{
	//取队头，出队头，打印
	BTNode* top = QueueFront(&q);
	QueuePop(&q);
	printf("%c ", top->_data);
	//孩子结点入队
	if (top->_left)
		QueuePush(&q, top->_left);
	if (top->_right)
		QueuePush(&q, top->_right);
}

进入循环后，每次取队头，打印队头数据，出对头，并将队头的孩子结点入队列，若孩子结点为空，则跳过，直至队列为空，可以看到打印的数据为层序。

	QueueDestroy(&q);

最后再将队列销毁即可。

typedef struct BinaryTreeNode* QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;
}Queue;

要注意的是，由于队列中所储存的数据类型为二叉树结点类型，所以队列中的QDataType的中定义也需要改动。

在添加了之前写的头文件Queue.h，源文件Queue.c后，就可以实现队列的相关操作了。

完整代码：

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头，打印
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", top->_data);
		//孩子结点入队
		if (top->_left)
			QueuePush(&q, top->_left);
		if (top->_right)
			QueuePush(&q, top->_right);
	}
	QueueDestroy(&q);
}

2.手动构建二叉树

在了解了二叉树的遍历后，我们可以通过遍历的结果手动构建一棵链式二叉树，例如这里我们可以通过前序遍历的结果“ABD###CE##F##”构建一棵二叉树，#表示遍历遇到空结点。

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)

函数的参数为遍历的结果存放的数组，数组元素个数n，用来遍历数组的 i 的地址pi。

if (*pi >= n || a[*pi] == '#')
{
	(*pi)++;
	return NULL;
}

首先，若遍历到的结点为#，或者下标大于等于数组元素个数n，则直接返回NULL，并跳过该字符，将 i 指向下一字符。

BTNode* root = BuyNode(a[*pi]);
(*pi)++;

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}

	newnode->_data = x;
	newnode->_left = newnode->_right = NULL;
	return newnode;
}

若遍历到的结点不为#，则对当前的结点申请空间，并创建，单独分装一个申请结点的函数BuyNode，然后让 i 指向下一个结点。

//创建左子树
root->_left = BinaryTreeCreate(a, n, pi);
//创建右子树
root->_right = BinaryTreeCreate(a, n, pi);

再递归创建左子树和右子树，最后返回root即可。

完整代码：

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	//若遍历到#，返回NULL,跳过该字符
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	//不是#，创建当前结点
	BTNode* root = BuyNode(a[*pi]);
	(*pi)++;

	//创建左子树
	root->_left = BinaryTreeCreate(a, n, pi);
	//创建右子树
	root->_right = BinaryTreeCreate(a, n, pi);

	return root;
}

3.二叉树结点个数

int BinaryTreeSize(BTNode* root)

二叉树的总结点个数可以拆分成当前结点，左子树总结点和右子树总结点之和，即二叉树结点个数 = 当前节点 + 左子树结点个数 + 右子树结点个数。

if (root == NULL)
{
	return 0;
}

对于当前结点，若该节点为空，则返回0。

return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);

若当前结点不为空，则继续递归左子树结点个数和右子树结点个数。

完整代码：

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->_left)
			+ BinaryTreeSize(root->_right);
}

图示：

4.二叉树叶子结点个数

int BinaryTreeLeafSize(BTNode* root)

与计算结点个数不同的是，我们对所计算的结点加上了限制条件，必须为叶子结点，即该结点的左右孩子必须为空结点，那么只需在求结点个数的代码上加上限制条件即可。

if (root == NULL)
{
	return 0;
}
if (root->_left == NULL && root->_right == NULL)
{
	return 1;
}

先判断是否为空结点，不是则继续判断，是则直接返回0，若左右孩子为空，则为叶子结点，返回1，若即不是空结点，也不是叶子结点，则继续递归该结点的左子树和右子树。

完整代码：

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

图示：

5.二叉树第k层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)

首先，我们需要找到第k层，若当前k为3，那每次进入一层时让k减一，则到达第k层时，k为1，则k为1时，当前层数即为第k层。

if (root == NULL)
{
	return 0;
}

若当前结点为空，直接返回0。

if (k == 1)
{
	return 1;
}

若当前结点在第k层，并且该结点不为空，则返回1。

return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);

若当前结点不为空，但并不在第k层，则继续往下递归，并让k减一。

完整代码：

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) 
           + BinaryTreeLevelKSize(root->_right, k - 1);
}

6.二叉树的高度/深度

int BinaryTreeDepth(BTNode* root)

一棵二叉树的高度可以表示为根结点与左右子树高度的最大值之和，即可以表示为：

二叉树高度 = 根结点 + max{左子树高度，右子树高度}

int leftdepth = BinaryTreeDepth(root->_left);
int rightdepth = BinaryTreeDepth(root->_right);

所以在这里，用两个变量去记录左右子树的高度。

leftdepth > rightdepth ? leftdepth : rightdepth

并用三目操作符得到左右子树高度的最大值。

if (root == NULL)
{
	return 0;
}

return 1 + (leftdepth > rightdepth ? leftdepth : rightdepth);

对于根结点，若根结点为空，则直接返回0，若根结点不为空，则让根结点加上左右子树高度的最大值并返回。

完整代码：

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftdepth = BinaryTreeDepth(root->_left);
	int rightdepth = BinaryTreeDepth(root->_right);
	return 1 + (leftdepth > rightdepth ? leftdepth : rightdepth);
}

图示：

7.二叉树查找值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)

if (root == NULL)
{
	return NULL;
}

若结点为空，直接返回NULL。

if (root->_data == x)
{
	return root;
}

若结点所储存的数据等于x，直接返回根结点。

BTNode* leftfind = BinaryTreeFind(root->_left, x);
if (leftfind)
{
	return leftfind;
}

若当前结点不为空，并且结点中所储存的数据不为x，则继续递归，在左子树中查找x，若在左子树中找到了x，则不需要再去递归右子树，直接返回。

BTNode* rightfind = BinaryTreeFind(root->_right, x);
if (rightfind)
{
	return rightfind;
}

return NULL;

若在左子树中也没找到x，最后递归右子树，若右子树中还是没找到x，返回NULL。

完整代码：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* leftfind = BinaryTreeFind(root->_left, x);
	if (leftfind)
	{
		return leftfind;
	}
	BTNode* rightfind = BinaryTreeFind(root->_right, x);
	if (rightfind)
	{
		return rightfind;
	}
	return NULL;
}

8.判断二叉树是否是完全二叉树

bool BinaryTreeComplete(BTNode* root)

完全二叉树的特点为：

1.除了最后一层的结点的度不一定为2，其他结点的度均为2

2.结点从左到右依次排列

在这里由于需要对每一层进行判断，我们需要再次借助队列。

Queue q;
QueueInit(&q);
QueuePush(&q, root);

在进入循环前，先将根结点入队列。

while (!QueueEmpty(&q))
{
	//取队头，出队头，判空
	BTNode* top = QueueFront(&q);
	QueuePop(&q);
	if (top == NULL)
	{
		break;
	}
	//不为空，左右孩子入队列
	QueuePush(&q, top->_left);
	QueuePush(&q, top->_right);
}

取队头，出队头，若取出的队头为空，则直接跳出循环，若不为空，该结点的左右孩子入队列，无论是否为空结点。

while (!QueueEmpty(&q))
{
	BTNode* cur = QueueFront(&q);
	QueuePop(&q);
	if (cur != NULL)
	{
		QueueDestroy(&q);
		return false;
	}
}

循环结束后，判断队列中是否有非空结点，若存在，则销毁队列，直接返回false，若全是空结点，循环结束后，销毁队列并返回true。

完整代码：

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头，判空
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		//不为空，左右孩子入队列
		QueuePush(&q, top->_left);
		QueuePush(&q, top->_right);
	}
	//遍历队列，遍历非空结点，则不为完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

9.销毁

void BinaryTreeDestory(BTNode** root)

由于需要销毁根节点，这里需要传输二级指针，实现传址调用。

if (*root == NULL)
{
	return;
}

若结点为空，则直接返回，不需要销毁。

BinaryTreeDestory(&((*root)->_left));
BinaryTreeDestory(&((*root)->_right));

若结点不为空，则需要依照左右根的顺序进行销毁，若在销毁左右子树前销毁根结点，则可能找不到左右子树。

free(*root);
*root = NULL;

当左右子树都销毁完后，最后再释放根结点。

完整代码：

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
	*root = NULL;
}

三.代码总览

头文件：存放函数声明部分

Tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

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

// 通过前序遍历的数组构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树的高度/深度
int BinaryTreeDepth(BTNode* root);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef struct BinaryTreeNode* QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

.c文件：存放函数定义

Tree.c

#include"Tree.h"
#include"Queue.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}

	newnode->_data = x;
	newnode->_left = newnode->_right = NULL;
	return newnode;
}

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	//若遍历到#，返回NULL,跳过该字符
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	//不是#，创建当前结点
	BTNode* root = BuyNode(a[*pi]);
	(*pi)++;

	//创建左子树
	root->_left = BinaryTreeCreate(a, n, pi);
	//创建右子树
	root->_right = BinaryTreeCreate(a, n, pi);

	return root;
}

// 二叉树前序遍历 -- 根左右 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

// 二叉树中序遍历 -- 左根右
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

// 二叉树后序遍历 -- 左右根
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}

// 层序遍历 -- 广度优先遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头，打印
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", top->_data);
		//孩子结点入队
		if (top->_left)
			QueuePush(&q, top->_left);
		if (top->_right)
			QueuePush(&q, top->_right);
	}
	QueueDestroy(&q);
}

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->_left)
			+ BinaryTreeSize(root->_right);
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->_left) 
		+ BinaryTreeLeafSize(root->_right);
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* leftfind = BinaryTreeFind(root->_left, x);
	if (leftfind)
	{
		return leftfind;
	}
	BTNode* rightfind = BinaryTreeFind(root->_right, x);
	if (rightfind)
	{
		return rightfind;
	}
	return NULL;
}

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
	*root = NULL;
}

// 二叉树的高度/深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftdepth = BinaryTreeDepth(root->_left);
	int rightdepth = BinaryTreeDepth(root->_right);
	return 1 + (leftdepth > rightdepth ? leftdepth : rightdepth);
}

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头，判空
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		//不为空，左右孩子入队列
		QueuePush(&q, top->_left);
		QueuePush(&q, top->_right);
	}
	//遍历队列，遍历非空结点，则不为完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

Queue.c

#include"Queue.h"

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
	q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->_data = data;
	newnode->_next = NULL;

	if (q->_front == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = q->_rear->_next;
	}
	++q->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(!QueueEmpty(q));
	if (q->_front == q->_rear)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}
	--q->size;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(!QueueEmpty(q));
	return q->_front->_data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(!QueueEmpty(q));
	return q->_rear->_data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* pcur = q->_front;
	while (pcur)
	{
		QNode* next = pcur->_next;
		free(pcur);
		pcur = next;
	}
	q->_front = q->_rear = NULL;
	q->size = 0;
}

开源鸿蒙跨平台开发者社区

开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。

更多推荐

React Native原理

在移动应用开发领域，React Native凭借“一次编写，多端运行”的特性成为开发者青睐的框架。其核心原理在于通过JavaScript与原生平台的桥梁，实现了高效渲染和性能优化。本文将深入剖析React Native的底层机制，揭示其如何平衡开发效率与原生体验。React Native的核心是基于JavaScriptCore引擎的通信架构。JavaScript代码通过“桥接层”与原生模块交互，将

开源鸿蒙跨平台开发者社区

react native 0.72遇到react-native-screens库出现cxx编译问题的解决方案

《React Native轻量化编译C++错误排查全记录》摘要：本文记录了程序员千里马在维护React Native相簿应用时遭遇的棘手编译问题。项目在轻量化编译时频繁出现react-native-screens的C++编译错误，而完整编译却能通过。作者先后排查了路径限制、缓存污染、网络依赖、版本兼容等问题，尝试了换包、重建工程等多种方案。最终发现是node_modules中老旧的react-na

开源鸿蒙跨平台开发者社区

分布式软总线核心代码分析（二）

本文分析了OpenHarmony分布式软总线5.1版本中"发现服务"的核心实现机制。发现服务通过DiscMgrInit初始化三个通信介质（BLE/CoAP/USB），建立发布服务链表（g_publishInfoList）、发现服务链表（g_discoveryInfoList）和16个能力匹配桶（g_capabilityList）。当设备被发现时，系统会根据设备能力位图与订阅者进