数据结构初阶：链式二叉树
前言
本文继续探索新的数据结构——二叉树。通过本文学习，你将掌握二叉树的定义、性质、遍历方式以及使用 C 语言进行链式实现的完整代码。
C算法
数据结构初阶：链式二叉树的实现与遍历
本文介绍数据结构中的链式二叉树。涵盖树的定义、术语、性质，以及二叉树的形态、特殊类型（满二叉树、完全二叉树等）和遍历方式（前序、中序、后序、层序）。重点讲解使用二叉链表实现二叉树的方法，包括节点结构定义、递归遍历接口、查找、销毁及判断完全二叉树等功能的 C 语言代码实现。
本文介绍数据结构中的链式二叉树。涵盖树的定义、术语、性质，以及二叉树的形态、特殊类型（满二叉树、完全二叉树等）和遍历方式（前序、中序、后序、层序）。重点讲解使用二叉链表实现二叉树的方法，包括节点结构定义、递归遍历接口、查找、销毁及判断完全二叉树等功能的 C 语言代码实现。
本文继续探索新的数据结构——二叉树。通过本文学习，你将掌握二叉树的定义、性质、遍历方式以及使用 C 语言进行链式实现的完整代码。
树（Tree）：是一种非线性的数据结构，它是由 n（n≥0）个有限节点组成一个具有层次关系的集合。
树的递归定义：树是由一个根节点和若干棵子树构成的。 一棵树中至少有一个节点，这个节点就是根节点。 当 n > 0 时，其余节点可分为 m（m≥0）个互不相交的有限集合 T1、T2、…、Tm，其中每个集合本身又是一棵树，并且称为根的子树。 例如：在一个表示公司组织架构的树中，公司的最高领导是根节点，其下的各个部门负责人是根节点的子树的根，每个部门又可以有自己的下属员工，形成更下一层的子树。
总结：从上面的定义中，我们可以知道树这种数据结构天然的和递归有关联。
树结构相对线性表比较复杂，要存储表示起来比较麻烦，既要保存值域，也要保存结点和结点之间的关系。 实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。 我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int TDataType;
/**
* @brief 树节点结构体定义（孩子 - 兄弟表示法）
* @details 采用左孩子右兄弟表示法，将多叉树转换为二叉树形式存储
* 每个节点包含数据域和两个指针域
*/
typedef struct TreeNode {
TDataType data; // 节点中的数据域
struct TreeNode* pfirstChild; // 指向第一个孩子结点
struct TreeNode* pNextBrother; // 指向其下一个兄弟结点
} TNode;
二叉树（Binary Tree）：是一种特殊的树形结构，其特点是每个节点最多有两个子节点，分别称为左子节点和右子节点。 二叉树的每个节点最多有两个子节点，并且子节点有左右之分，顺序不能颠倒。 二叉树是一个有限节点的集合，该集合可以为空，或由一个根节点和两棵互不相交的子树组成，这两棵子树分别称为左子树和右子树。
| 特征 | 二叉树 | 普通树 |
|---|---|---|
| 最大分支数 | 每个节点≤2 个子节点 | 任意数量子节点 |
| 子节点顺序 | 严格区分左/右 | 通常无序 |
| 空树定义 | 允许空树（NULL） | 至少包含根节点 |
二叉树的关键特点：
注意：对于任意的二叉树都是由上面的这五种情况复合而成的。
注：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。所以：满二叉树是特殊的完全二叉树。
树的性质：
二叉树的性质：
对于任意非空二叉树：叶节点数 = 度为 2 的节点数 + 1。
| 特性 | 普通树 | 二叉树 |
|---|---|---|
| 节点最大度数 | 无限制 | 最多 2 |
| 子树顺序 | 一般不区分 | 严格区分左右 |
| 空树 | 有些定义不允许 | 明确允许 |
| 存储结构 | 通常使用孩子兄弟表示法 | 常用左右指针法（二叉链） |
| 遍历方式 | 无中序遍历 | 有中序遍历 |
二叉树的遍历：二叉树的遍历是指按照一定的规则和顺序，访问二叉树中的每个节点，且每个节点仅被访问一次。 根据节点访问顺序的不同，二叉树的遍历主要分为以下四类：
| 遍历方式 | 访问顺序 | 典型应用场景 |
|---|---|---|
| 前序遍历 | 根 → 左子树 → 右子树 | 复制树结构、前缀表达式（波兰式） |
| 中序遍历 | 左子树 → 根 → 右子树 | 二叉搜索树的有序输出（升序/降序） |
| 后序遍历 | 左子树 → 右子树 → 根 | 删除树结构、后缀表达式（逆波兰式） |
| 层序遍历 | 按层次从上到下、从左到右 | 计算树的高度、广度优先搜索（BFS） |
示例答案：
和之前我们学习的其他的数据结构一样，二叉树常见实现方式有顺序存储和链式存储。
那我们就先来看看树的顺序存储： 二叉树的顺序存储结构是用一组连续的存储单元依次自上而下、自左至右存储二叉树的节点元素。 其中普通的二叉树是不适合使用顺序存储的，也就是说不适合使用数组来存储二叉树的节点，这是因为对于一般二叉树，需要按照完全二叉树的形式来存储，可能会浪费一些存储空间。 而像完全二叉树就比较适合使用顺序结构存储。
其实我们通常会把'使用动态数组实现的完全二叉树'这种结构称为堆。 注意：这里的堆和内存四区中的堆是两回事，一个是一种数据结构，一个是操作系统中管理内存的一块区域分段。
堆：使用动态数组实现的完全二叉树。
//任务 2：定义堆的结构体（存储类型）
typedef int HPDataType;
typedef struct Heap {
//核心思路：堆是完全二叉树所以使用数组实现比较好
//1.记录数组的容量 ---> 一个 int 变量
//2.记录当前数组中元素的数量 --> 一个 int 变量
//3.使用数组存储堆中的节点 ---> 定义一个动态数组
int capacity;
int size;
HPDataType* a;
} HP;
预告：由于堆这种数据结构有很多可讲的点，这篇博客中我们只是简单的了解一下，下篇博客再详细的介绍它。
接下来我们再看一看树的链式存储： 二叉树的链式存储结构，是借助链表来呈现二叉树形态，以链表的链接关系来体现节点间逻辑关联。 一般而言，链表中的每个节点包含三个域：数据域用于存储节点数据，左指针域指向该节点左孩子所在的链表节点，右指针域则指向右孩子所在的链表节点。 链式结构又分为：二叉链和三叉链，在数据结构初阶阶段，我们先学习使用二叉链来实现二叉树。
1. 使用二叉链实现二叉树：
typedef int BTDataType;
typedef struct BinaryTreeNode {
//1.存储二叉树节点存储的值
//2.存储节点的左孩子指针
//3.存储节点的右孩子指针
BTDataType data;
struct BinaryTreeNode* left; // 注意：这里还是要注意不要忘记使用 struct
struct BinaryTreeNode* right;
} BTNode;
2. 使用三叉链实现二叉树
typedef int BTDataType;
typedef struct BinaryTreeNode {
BTDataType data; // 当前结点值域
struct BinTreeNode* parent; // 指向当前结点的双亲
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
} BTNode;
综上所述：顺序存储（数组）：用数组按层次顺序存储节点，适合完全二叉树。 链式存储（链表）：用节点（含数据域与左右指针域）以链式结构相连存储节点，适配任意二叉树。
------------------------------BinaryTree.h------------------------------
#pragma once
//任务 1：声明需要使用头文件
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Queue.h"
//任务 2：定义二叉树的存储结构体
typedef int BTDataType;
typedef struct BinaryTreeNode {
//1.存储二叉树节点存储的值
//2.存储节点的左孩子指针
//3.存储节点的右孩子指针
BTDataType data;
struct BinaryTreeNode* left; // 注意：这里还是要注意不要忘记使用 struct
struct BinaryTreeNode* right;
} BTNode;
//任务 3：声明二叉树的接口函数
//注意：初阶数据结构阶段的学习我们只会去实现一些简单的接口
//例如：二叉树的创建暂时并不涉及，初学阶段我们直接使用手动创建的二叉树来测试我们完成的简单的接口
/*------------------------------ 递归实现 ------------------------------*/
//0.二叉树的节点的创建 + 初始化
//1.二叉树的前序遍历
//2.二叉树的中序遍历
//3.二叉树的后序遍历
//4.二叉树的求树中节点的个数
//5.二叉树的求树中叶子节点的个数
//6.二叉树的求树的高度
//7.二叉树的求树中第 K 层节点的个数
//8.二叉树的寻找树中某个值
//9.二叉树的销毁
/*------------------------------ 非递归实现 ------------------------------*/
//10.二叉树的层序遍历 （需要使用数据结构：队列）
//11.二叉树的判断是否为完全二叉树 （需要使用数据结构：队列）
BTNode* BTCreatNode(int x);
void PrevOrder(BTNode* root);
void InOrder(BTNode* root);
void PostOrder(BTNode* root);
int BTSize(BTNode* root);
int BTLeafSize(BTNode* root);
int BTHeight(BTNode* root);
int BTLevelKSize(BTNode* root, int k);
BTNode* BTFind(BTNode* root, int x);
void BTDestroy(BTNode* root);
void LevelOrder(BTNode* root);
bool BTComplete(BTNode* root);
--------------------------------Queue.h--------------------------------
#pragma once
//任务 1：声明需要使用的头文件
//任务 2：定义队列的结构体
//任务 3：声明队列的接口函数
//任务 1：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//任务 2：
// Forward declaration to avoid circular dependency
typedef struct BinaryTreeNode BTNode;
typedef struct BinaryTreeNode* QDateType; // 使用 typedef 重新定义队列中的变量的数据类型，方便后续进行修改
//队列节点的结构体
typedef struct QueueNode {
//1.队列节点中存储的数据 ---> 一个 int 变量
//2.队列节点中存储下一个节点的位置 ---> 一个指针
QDateType val;
struct QueueNode* next; // 注意这里 next 的类型可千万不要使用 QNode 哦，因为这时你还没有定义 QNode，也不要使用 QueueNode 进行代替
} QNode;
//队列的结构体（使用带头尾指针的结构）
typedef struct Queue {
//1.记录当前队列中元素的个数 ---> 一个 int 变量
//2.指向头部的指针 ---> （用于：头删/取队头的元素）
//3.指向尾部的指针 ---> （用于：尾插/取队尾的元素）
int size;
QNode* queHead;
QNode* queTail;
} Que;
//任务 3：
//1.队列的初始化
//2.队列的销毁
//3.队列的入队
//4.队列的出队
//5.队列的取队头元素
//6.队列的取队尾元素
//7.队列的判空
//8.队列的求队列中元素的数量
void QueInit(Que* pque);
void QueDestroy(Que* pque);
void QuePush(Que* pque, QDateType x);
void QuePop(Que* pque);
QDateType QueFront(Que* pque);
QDateType QueBack(Que* pque);
bool QueEmpty(Que* pque);
int QueSize(Que* pque);
------------------------------BinaryTree.c------------------------------
#define _CRT_SECURE_NO_WARNINGS 1
#include "BinaryTree.h"
//0.实现：'二叉树的节点的创建 + 初始化'操作
/*****************************************************************
* @brief 动态创建二叉树节点
* @param x 节点要存储的数据值
* @return 成功返回节点指针，失败返回 NULL
* @note 使用 malloc 动态分配内存
* 典型错误处理：
* 1. 内存分配失败时打印错误信息
* 2. 新节点的左右指针初始化为 NULL
*****************************************************************/
BTNode* BTCreatNode(int x) {
/*--------第一阶段：动态申请节点的内存空间--------*/
//1.使用 malloc 进行动态的内存分配
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//2.检查内存是否开辟成功
if (node == NULL) {
perror("malloc fail");
return NULL;
}
/*--------第二阶段：初始化节点的数据--------*/
node->data = x;
node->left = NULL;
node->right = NULL;
/*--------第二阶段：返回开辟的二叉树节点的内存地址--------*/
return node;
}
//1.实现：'二叉树的前序遍历'操作
/*****************************************************************
* @brief 二叉树前序遍历（递归实现）
* @param root 当前遍历的子树根节点
* @note 遍历顺序：根节点->左子树->右子树
* 输出格式：非空节点输出数据，空节点输出"N "
* 示例输出：1 2 3 N N N 4 5 N 6 N N 6 N N
*****************************************************************/
void PrevOrder(BTNode* root) {
//1.递归结束的出口
if (root == NULL) {
printf("N "); // 也可以不写，只是为了方便初学者能更好的理解前序遍历而添加的
return;
}
//2.按照：根节点 ---> 左子树 ---> 右子树 的顺序进行递归遍历
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
//2.实现：'二叉树的中序遍历'操作
/*****************************************************************
* @brief 二叉树中序遍历（递归实现）
* @param root 当前遍历的子树根节点
* @note 遍历顺序：左子树->根节点->右子树
* 输出格式同前序遍历
* 示例输出：N 3 N 2 N 1 N 5 N 6 N 4 N 6 N
*****************************************************************/
void InOrder(BTNode* root) {
//1.递归结束的出口
if (root == NULL) {
printf("N ");
return;
}
//按照：左子树 ---> 根节点 ---> 右子树 的顺序进行递归遍历
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
//3.实现：'二叉树的后序遍历'操作
/*****************************************************************
* @brief 二叉树后序遍历（递归实现）
* @param root 当前遍历的子树根节点
* @note 遍历顺序：左子树->右子树->根节点
* 输出格式同前序遍历
* 示例输出：N N 3 N 2 N N 6 5 N N 6 4 1
*****************************************************************/
void PostOrder(BTNode* root) {
//1.递归结束的出口
if (root == NULL) {
printf("N ");
return;
}
//2.按照：左子树 ---> 右子树 ---> 根节点 的顺序进行递归遍历
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
//4.实现：'二叉树的求树中节点的个数'操作
/*****************************************************************
* @brief 计算二叉树节点总数（递归）
* @param root 当前子树根节点
* @return 以 root 为根的树的节点总数
* @note 计算公式：
* 空树：0
* 非空树：左子树节点数 + 右子树节点数 + 1(当前节点)
*****************************************************************/
int BTSize(BTNode* root) {
//1.处理：空树 + 空节点 的情况（同样是递归结束的条件）
if (root == NULL)
return 0;
else
return BTSize(root->left) + BTSize(root->right) + 1;
//跟简洁的写法：
//return root == NULL ? 0 : BTSize(root->left) + BTSize(root->right) + 1;
}
//5.实现：'二叉树的求树中叶子节点的个数'操作
/*****************************************************************
* @brief 计算二叉树叶子节点数（递归）
* @param root 当前子树根节点
* @return 以 root 为根的树的叶子节点数
* @note 叶子节点定义：无左右子树的节点
* 计算公式：
* 空树：0
* 叶子节点：1
* 非叶子节点：左子树叶子数 + 右子树叶子数
*****************************************************************/
int BTLeafSize(BTNode* root) {
//1.处理：空树 + 一度节点 的情况（同样是递归结束的条件）
if (root == NULL)
return 0;
//2.使用 if 判断如果：当前遍历到的节点是叶子节点（同样是递归结束的条件）
if (root->left == NULL && root->right == NULL)
return 1;
else
return BTLeafSize(root->left) + BTLeafSize(root->right);
}
//6.实现：'二叉树的求树的高度'操作
/*****************************************************************
* @brief 计算二叉树高度/深度（递归）
* @param root 当前子树根节点
* @return 以 root 为根的树的高度
* @note 高度定义：
* 空树高度为 0
* 非空树高度为 max(左子树高，右子树高) + 1
* 优化：避免重复计算左右子树高度
*****************************************************************/
int BTHeight(BTNode* root) {
//1.处理：空树 +
if (root == NULL)
return 0;
//2.计算非空树的高度
//2.1：递归计算左子树和右子树的高度 ---> 进行优化（这里先将结果计算出来，避免进行重复的计算）
int leftHeight = BTHeight(root->left);
int rightHeight = BTHeight(root->right);
//2.2：返回非空树的高度
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
//7.实现：'二叉树的求树中第 K 层节点的个数'操作
/*****************************************************************
* @brief 计算二叉树第 k 层节点数（递归）
* @param root 当前子树根节点
* @param k 目标层数（从 1 开始计数）
* @return 第 k 层节点数
* @note 计算公式：
* 空树或 k<1：0
* k==1：1（当前节点）
* 其他：左子树 k-1 层节点数 + 右子树 k-1 层节点数
*****************************************************************/
int BTLevelKSize(BTNode* root, int k) {
//1. 处理：空树 + 一度节点 情况
if (root == NULL)
return 0;
//2.使用 if 判断：如果当前 K 值为 1
if (k == 1)
return 1;
//3.递归计算左右子树的第 K 层
return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k - 1);
}
//8.实现：'二叉树的寻找树中的某个节点的位置'操作
/*****************************************************************
* @brief 在二叉树中查找值为 x 的节点（递归）
* @param root 当前子树根节点
* @param x 要查找的值
* @return 找到的节点指针，未找到返回 NULL
* @note 查找顺序：
* 1. 检查当前节点
* 2. 递归查找左子树
* 3. 若左子树未找到，递归查找右子树
* 注意：如果树中存在多个 x，返回最先找到的节点
*****************************************************************/
BTNode* BTFind(BTNode* root, int x) {
//1.处理：'空树 + 遍历到空节点'的情况
if (root == NULL)
return NULL;
//2.使用 if 判断：如果遍历到的节点的值是 x
if (root->data == x)
return root;
//3.进行递归查找
//3.1：先在左子树中进行递归查找
BTNode* ret = BTFind(root->left, x);
if (ret)
return ret;
//3.2：再在右子树中进行递归操作
ret = BTFind(root->right, x);
if (ret)
return ret;
//4.返回空指针标志未找到
return NULL;
//可以将'在右子树寻找 + 未找到'的情况进行合并简化
//原因：在右子树中没有找到：（代表整棵树中真的没有你想找的这个值）
//return BTFind(root->right, x);
}
//9.实现：'二叉树的销毁'操作
/**
* @brief 销毁二叉树（后序遍历方式）
* @param root 二叉树根节点指针
* @note 递归释放所有节点内存
* 采用后序遍历顺序：先销毁左子树，再销毁右子树，最后释放当前节点
*/
void BTDestroy(BTNode* root) {
//1.处理：'空树 + 遍历到空节点'的情况
if (root == NULL)
return;
//2.使用后序遍历的方式进行递归的销毁
BTDestroy(root->left);
BTDestroy(root->right);
free(root);
}
//10.实现：'二叉树的层序遍历'操作
/**
* @brief 二叉树层序遍历（广度优先遍历）
* @param root 二叉树根节点指针
* @note 使用队列辅助实现：
* 1. 根节点入队
* 2. 循环取出队首元素并处理
* 3. 将其左右子节点入队
* 时间复杂度：O(n)，空间复杂度：O(n)
*/
void LevelOrder(BTNode* root) {
//1.创建队列 + 初始化队列
Que que;
QueInit(&que);
//2.将二叉树的根节点入队
if (root) {
QuePush(&que, root);
}
//3.遍历队列来实现树的层序遍历
while (!QueEmpty(&que)) {
//3.1：将队头元素：'记录 + 出队 + 输出'
BTNode* front = QueFront(&que);
QuePop(&que);
printf("%d ", front->data);
//3.2：将队头的二叉树的节点的左孩子和右孩子添加到队列中
if (front->left)
QuePush(&que, front->left); // 注意：这里是（front->left 而不是 root->left）
if (front->right)
QuePush(&que, front->right);
}
//4.销毁队列
QueDestroy(&que);
}
//11.实现：'二叉树的判断其是否是一棵完全二叉树'操作
/**
* @brief 判断是否是完全二叉树
* @param root 二叉树根节点指针
* @return true-是完全二叉树，false-不是完全二叉树
* @note 完全二叉树判定条件：
* 1. 层序遍历遇到第一个 NULL 节点后，后续不应再有非 NULL 节点
* 2. 使用队列辅助实现，NULL 节点也入队
* 时间复杂度：O(n)，空间复杂度：O(n)
*/
bool BTComplete(BTNode* root) {
//1.创建队列 + 初始化队列
Que que;
QueInit(&que);
//2.将二叉树的根节点入队
if (root)
QuePush(&que, root);
//3.按照层序遍历：'找到层序遍历的第一个空节点的位置'
while (!QueEmpty(&que)) {
//3.1：将队头元素：'记录 + 出队 + 判断'
BTNode* front = QueFront(&que);
QuePop(&que);
if (front == NULL)
break;
//3.2：将队头的二叉树的节点的左孩子和右孩子添加到队列中
QuePush(&que, front->left); // 注意：这里是无论子节点是否为空都将其入队
QuePush(&que, front->right);
}
//4.按照层序遍历：'检查剩余节点是否有非空节点'
while (!QueEmpty(&que)) {
//3.1：将队头元素：'记录 + 出队 + 判断'
BTNode* front = QueFront(&que);
QuePop(&que);
if (front != NULL) {
QueDestroy(&que);
return false;
}
}
QueDestroy(&que);
return true;
}
------------------------------Queue.c------------------------------
#include "Queue.h"
//1.实现：'队列的初始化'操作
void QueInit(Que* pque) {
assert(pque);
//1.将队列结构体中'元素的数量'置为 0
pque->size = 0;
//2.将队列结构体中'指向队头/队尾的指针'置为空指针
pque->queHead = NULL;
pque->queTail = NULL;
}
//2.实现：'队列的销毁'操作
void QueDestroy(Que* pque) {
assert(pque);
//1.将队列结构体中'元素的数量'置为 0
pque->size = 0;
//2.将队列中的所有的节点都释放掉
//1）创建临时指针代替 queHead 进行遍历队列的节点
QNode* tmp = pque->queHead;
//2）使用 tmp 遍历所有的节点
while (tmp != NULL) {
//3）创建后继指针存储当前遍历到的节点的下一位置
QNode* next = tmp->next;
//4) 释放当前遍历到的节点
free(tmp);
//5) 更新 tmp 指针
tmp = next;
}
//将队列结构体中'指向队列头部/尾部的指针'置为空指针
pque->queHead = NULL;
pque->queTail = NULL;
}
//3.实现：'队列的入队'操作
void QuePush(Que* pque, QDateType x) {
assert(pque);
//思路：使用链表的尾插法实现入队的操作
//1）先创建出来一个队列的节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
//1.1:判断新开辟的空间是否开辟成功哦
if (newNode == NULL) {
perror("malloc fail");
return;
}
//2）为这个节点进行赋值
newNode->val = x;
//3）将这个节点链接到队列链表的后面
//3.1：将新开辟的节点的 next 指针域置空
newNode->next = NULL;
//3.2：将新开辟的节点链接到队列链表的尾部
//3.3.1：如果当前的队列链表中没有节点
if (pque->queTail == NULL) {
pque->queHead = pque->queTail = newNode;
}
//3.3.2：如果当前的队列链表中有节点
else {
pque->queTail->next = newNode;
pque->queTail = newNode;
}
//4）队列中的元素的数量增加
pque->size++;
}
//4.实现：'队列的出队'操作
void QuePop(Que* pque) {
assert(pque);
assert(pque->size > 0);
//注意：当我们：1.删除某个数据结构中的元素时 2.从某个数据结构中取出元素的时
//---> 需要判断当前的数据结构中是否还有元素
//思路：使用链表的头删法实现出队操作
//1）如果当前队列中只有一个元素
if (pque->queHead->next == NULL) {
//1.1：将这一个节点删除掉
free(pque->queHead);
//1.2：将指向队头和队尾的指针都置为空
pque->queHead = NULL;
pque->queTail = NULL;
}
//2）如果队列中的元素有多个
else {
//2.1：创建一个临时的指针来存放 queHead 指针的下一个位置
QNode* next = pque->queHead->next;
//2.2：释放掉 queHead 指针指向的节点
free(pque->queHead);
//2.3：将 queHead 指针移动到下一个节点的位置
pque->queHead = next;
}
//3）队列中的元素的数量减少
pque->size--;
}
//5.实现：'队列的取出队头元素'操作
QDateType QueFront(Que* pque) {
assert(pque);
assert(pque->size > 0);
return pque->queHead->val;
}
//6.实现：'队列的取出队尾元素'操作
QDateType QueBack(Que* pque) {
assert(pque);
assert(pque->size > 0);
return pque->queTail->val;
}
//7.实现：'队列的判空'
bool QueEmpty(Que* pque) {
assert(pque);
return pque->size == 0; // 队列中没有元素返回真；队列中有元素返回假
}
//8.实现：'队列的求出队列中元素的个数'操作
int QueSize(Que* pque) {
assert(pque);
return pque->size;
}
------------------------------Test.c------------------------------
#include "BinaryTree.h"
int main() {
/*****************************************************************
* @brief 创建固定结构的二叉树（示例）
* @return 返回构建好的二叉树根节点指针
* @note 构建的二叉树结构：
* 1
* / \
* 2 4
* / / \
* 3 5 6
* \
* 6
* 注意：实际应用中应该从输入构建树，这里为演示硬编码
*****************************************************************/
/*--------第一阶段：创建二叉树的节点--------*/
BTNode* node1 = BTCreatNode(1);
BTNode* node2 = BTCreatNode(2);
BTNode* node3 = BTCreatNode(3);
BTNode* node4 = BTCreatNode(4);
BTNode* node5 = BTCreatNode(5);
BTNode* node6 = BTCreatNode(6);
BTNode* node7 = BTCreatNode(6);
/*--------第二阶段：构建二叉树的结构--------*/
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node5->right = node7;
/*--------第三阶段：测试二叉树的接口函数--------*/
//1.测试遍历算法
printf("前序遍历：");
PrevOrder(node1); // 预期输出：1 2 3 N N N 4 5 N 6 N N 6 N N
printf("\n");
printf("中序遍历：");
InOrder(node1); // 预期输出：N 3 N 2 N 1 N 5 N 6 N 4 N 6 N
printf("\n");
printf("后序遍历：");
PostOrder(node1); // 预期输出：N N 3 N 2 N N N 6 5 N N 6 4 1
printf("\n");
//2.测试树属性计算
printf("节点总数：%d\n", BTSize(node1)); // 预期：7
printf("叶子节点数：%d\n", BTLeafSize(node1)); // 预期：3（节点 3、6、6）
printf("树高度：%d\n", BTHeight(node1)); // 预期：4
printf("第 3 层节点数：%d\n", BTLevelKSize(node1, 3)); // 预期：3（节点 3、5、6）
printf("第 4 层节点数：%d\n", BTLevelKSize(node1, 4)); // 预期：1（节点 6）
//3.测试查找功能
int target = 6;
BTNode* found = BTFind(node1, target);
if (found)
printf("找到节点%d\n", target);
else
printf("未找到节点%d\n", target);
//4.测试层序遍历
printf("层序遍历：");
LevelOrder(node1); // 预期输出：1 2 4 3 5 6 6
printf("\n");
//5.测试判断是否为完全二叉树
if (BTComplete(node1))
printf("该二叉树是完全二叉树\n");
else
printf("该二叉树不是完全二叉树\n");
//6.测试二叉树销毁
BTDestroy(node1);
printf("二叉树已销毁\n");
return 0;
}
程序编译运行后，控制台将输出遍历结果及树属性统计，验证二叉树功能的正确性。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online