数据结构初阶：链式二叉树的实现与遍历

二叉树

什么是二叉树？

二叉树（Binary Tree）：是一种特殊的树形结构，其特点是每个节点最多有两个子节点，分别称为左子节点和右子节点。 二叉树的每个节点最多有两个子节点，并且子节点有左右之分，顺序不能颠倒。 二叉树是一个有限节点的集合，该集合可以为空，或由一个根节点和两棵互不相交的子树组成，这两棵子树分别称为左子树和右子树。

二叉树与普通树的本质区别是什么？

二叉树的关键特点：

1. 每个节点至多有两个子节点：即节点的度最大为 2。
2. 子节点有明确的左右之分：左子树和右子树是不同的，即使只有一个子节点也必须区分左右。
3. 递归结构：二叉树的左右子树本身也都是二叉树。

二叉树的五大基本形态是什么？

1. 空树：没有任何节点。
2. 只有根节点：根节点的左右子树均为空。
3. 根节点只有左子树：右子树为空。
4. 根节点只有右子树：左子树为空。
5. 根节点同时有左右子树：左右子树均非空。

注意：对于任意的二叉树都是由上面的这五种情况复合而成的。

特殊的二叉树有哪些？

• 满二叉树（Full Binary Tree）：所有层的节点数都达到最大值，则这个二叉树就是满二叉树。
• 完全二叉树（Complete Binary Tree）：除了最后一层外，每一层的节点数都达到最大值，且最后一层的节点从左到右连续排列。
• 二叉搜索树（Binary Search Tree, BST）：左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
• 平衡二叉树（Balanced Binary Tree）：每个节点的左右子树高度差不超过 1（如：AVL 树、红黑树、B 树）。

注：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。所以：满二叉树是特殊的完全二叉树。

树和二叉树的性质有哪些？

树的性质：

• 连通性：树是一个连通的无向图，任意两个节点之间都有且仅有一条路径相连。
• 无环性：树中不存在回路或环，从根节点到任何其他节点都有唯一的路径。
• 层次关系：树具有明显的层次结构。
• 子树性质：树中的每个节点都可以看作是一棵子树的根。
• 节点与边的关系：对于一棵有 n 个节点的树，其边的数量为 n - 1。
• 节点和度的关系：总结点数 = 所有节点度数之和 + 1。

二叉树的性质：

• 二叉树遍历的性质：已知前序 + 中序，或后序 + 中序可以唯一确定一棵二叉树，但前序 + 后序不能唯一确定二叉树（除非是满二叉树）。
• 层节点数与层数的关系：在满二叉树中，第 k 层的节点数为 2^(k-1)。扩展到二叉树：一棵非空二叉树的第 k 层上最多有 2^(k-1) 个结点。
• 总节点数与高度的关系：
  • 在满二叉树中，高度为 h 的满二叉树的总节点数为 2^h - 1。
  • 扩展到二叉树：一棵高度为 h 的二叉树最多有 2^h - 1 个结点。
  • 在满二叉树中，具有 n 个结点的满二叉树的高度为 log2(n + 1)。
• 完全二叉树顺序特性：
  • 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：
    • 双亲结点（父结点）：若 i = 0，该结点为根结点，无双亲结点；若 i > 0，结点 i 的双亲结点序号为 (i-1)/2（向下取整）。
    • 左孩子结点：若 2i + 1 >= n，则该结点无左孩子；若 2i + 1 < n，则左孩子序号为 2i + 1。
    • 右孩子结点：若 2i + 2 >= n，则该结点无右孩子；若 2i + 2 < n，则右孩子序号为 2i + 2。
• 总节点数与高度的关系：具有 n 个节点的完全二叉树的高度为 floor(log2(n)) + 1。

对于任意非空二叉树：叶节点数 = 度为 2 的节点数 + 1。

树和二叉树的区别是什么？

二叉树怎么进行遍历？

二叉树的遍历：二叉树的遍历是指按照一定的规则和顺序，访问二叉树中的每个节点，且每个节点仅被访问一次。 根据节点访问顺序的不同，二叉树的遍历主要分为以下四类：

示例答案：

• 前序：1 2 3 N N N 4 5 N 6 N N 6 N N
• 中序：N 3 N 2 N 1 N 5 N 6 N 4 N 6 N
• 后序：N N 3 N 2 N N 6 5 N N 6 4 1

二叉树的实现方式有哪些？我们要选择哪种方式进行实现？

和之前我们学习的其他的数据结构一样，二叉树常见实现方式有顺序存储和链式存储。

那我们就先来看看树的顺序存储： 二叉树的顺序存储结构是用一组连续的存储单元依次自上而下、自左至右存储二叉树的节点元素。 其中普通的二叉树是不适合使用顺序存储的，也就是说不适合使用数组来存储二叉树的节点，这是因为对于一般二叉树，需要按照完全二叉树的形式来存储，可能会浪费一些存储空间。 而像完全二叉树就比较适合使用顺序结构存储。

其实我们通常会把'使用动态数组实现的完全二叉树'这种结构称为堆。 注意：这里的堆和内存四区中的堆是两回事，一个是一种数据结构，一个是操作系统中管理内存的一块区域分段。

堆：使用动态数组实现的完全二叉树。

//任务 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;
}

运行成功样例

程序编译运行后，控制台将输出遍历结果及树属性统计，验证二叉树功能的正确性。