《数据结构初阶》【链式二叉树】

往期《数据结构初阶》回顾：
【时间复杂度 + 空间复杂度】
【顺序表 + 单链表 + 双向链表】
【顺序表/链表 精选15道OJ练习】
【顺序栈 + 链式队列 + 循环队列】

前言：

嗨～(✿◠‿◠) 友友们！好久不见啦，不知道这段时间大家在数据结构的知识海洋里遨游得怎么样？🏊
最近天气越来越暖和，阳光也愈发灿烂啦～🌼
🚩 今天咱们就要继续探索新的数据结构—— 二叉树 啦！ 🌳

“学不会？不存在的！汪星人都能懂的二叉树教程🐶，你也一定行！”
相信当你沉浸其中，读完这篇博客后，一定会对二叉树有全新的认识哦~，也一定能收获超多知识干货！✨

---------------树---------------

什么是树？

树（Tree）：是一种非线性的数据结构，它是由 $n$$（n\ge 0）$个有限节点组成一个具有层次关系的集合。

树的递归定义：树是由一个根节点和若干棵子树构成的。

一棵树中至少有一个节点，这个节点就是根节点。

当 $n>0$ 时，其余节点可分为 $m$$（m\ge 0）$个互不相交的有限集合$T_1$、$T_2$、…、$T_m$，其中每个集合本身又是一棵树，并且称为根的子树。

• 例如：在一个表示公司组织架构的树中，公司的最高领导是根节点，其下的各个部门负责人是根节点的子树的根，每个部门又可以有自己的下属员工，形成更下一层的子树。

总结：从上面的定义中，我们可以知道树这种数据结构天然的和递归有关联。

📌爱心❤小贴士：树与非树？

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

树的基本术语有哪些？

关于节点的一些定义：

节点：树中的每个元素称为节点。

• 如上图：A、B、C、D、E、F、G、H、I、J、K、L、M、N、P 、Q均为节点。

根节点：树中没有父节点的节点，也是树的起始点。

• 如上图：A 是根节点。

子节点与父节点：一个节点的下一层连接的节点称为其子节点，该节点则是其子节点的父节点。

• 如上图：B、C、D、E、F、G 是 A 的子节点，A 是 B、C、D、E、F、G 的父节点

兄弟节点：具有相同父节点的节点互为兄弟节点。

• 如上图：K、L、M互为兄弟节点

堂兄弟节点：父节点互为兄弟节点的节点互为堂兄弟节点。

• 如上图：H 和 K 是堂兄弟节点，因为 H 的父节点 D 与 K 的父节点 F 是兄弟节点。

叶子节点：没有子节点的节点，也称为终端节点。

• 如上图：B、C、H、I、K、L、M、N、P、Q 是叶子节点。

内部节点：除叶子节点外的其他节点，即至少有一个子节点的节点。

• 如上图：A、D、E、F、G、J 均为节点。

节点的祖先：从根节点到该节点所经路径上的所有节点。

• 如上图：对于节点 Q ，其祖先为 A、E、J

节点的子孙：以某节点为根的子树中的所有节点。

• 如上图：对于节点 E ，其子孙为 I、J、P 、Q

关于树的一些定义：

节点的度：一个节点拥有的子节点数量。

• 如上图：A 的度为 6，D 的度为 1 等

树的度：树中节点度的最大值。

• 如上图：树的度为 6（A 节点的度）

路径：从一个节点到另一个节点所经过的节点序列。

• 如上图：从 A 到 Q 的路径为 A、E、J、Q

路径长度：路径上的边的数量。

• 如上图：从 A 到 Q 的路径长度为 3

树的深度（高度）：树中节点的最大层数。

• 如上图：树的深度（高度）为 4

层：节点的层次，根节点在第 1 层，其子节点在第 2 层，以此类推。

• 如上图：A 在第 1 层，B、C、D、E、F、G 在第 2 层，H、I、J、K、L、M、N 在第 3 层，P、Q 在第 4 层。

关于森林的定义：

森林：由零棵或多棵互不相交的树组成的集合。

树的实现方式有哪些？

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间 的关系。

实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。

我们这里就简单的了解其中最常用的 孩子兄弟表示法

typedef int TDataType;/*** @brief 树节点结构体定义（孩子-兄弟表示法）* @details 采用左孩子右兄弟表示法，将多叉树转换为二叉树形式存储*          每个节点包含数据域和两个指针域*/
typedef struct TreeNode
{TDataType data;              // 节点中的数据域struct TreeNode* pfirstChild;   // 指向第一个孩子结点struct TreeNode* pNextBrother;  // 指向其下一个兄弟结点
}TNode;

---------------二叉树---------------

什么是二叉树？

二叉树（Binary Tree）： 是一种特殊的树形结构，其特点是每个节点最多有两个子节点，分别称为左子节点和右子节点

• 二叉树的每个节点最多有两个子节点，并且子节点有左右之分，顺序不能颠倒
• 二叉树是一个有限节点的集合，该集合可以为空，或由一个根节点和两棵互不相交的子树组成，这两棵子树分别称为左子树和右子树

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

特征	二叉树	普通树
最大分支数	每个节点≤2个子节点	任意数量子节点
子节点顺序	严格区分左/右	通常无序
空树定义	允许空树（NULL）	至少包含根节点

二叉树的关键特点：

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

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

空树：没有任何节点。

只有根节点：根节点的左右子树均为空。

根节点只有左子树：右子树为空。

根节点只有右子树：左子树为空。

根节点同时有左右子树：左右子树均非空。

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

特殊的二叉树有哪些？

满二叉树（Full Binary Tree）：所有层的节点数都达到最大值，则这个二叉树就是满二叉树。

完全二叉树（Complete Binary Tree）：除了最后一层外，每一层的节点数都达到最大值，且最后一层的节点从左到右连续排列。

二叉搜索树（Binary Search Tree, BST）：左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。

平衡二叉树（Balanced Binary Tree）：每个节点的左右子树高度差不超过 1（如： AVL 树、红黑树、B树）

注：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

所以：满二叉树是特殊的完全二叉树

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

树的性质：

连通性：树是一个连通的无向图，任意两个节点之间都有且仅有一条路径相连。

• 树是边数最少的连通图，加一条边会形成环，减一条边会变成非连通图

无环性：树中不存在回路或环，从根节点到任何其他节点都有唯一的路径。

层次关系：树具有明显的层次结构，根节点位于最高层，其子孙节点分布在不同的下层。

子树性质：树中的每个节点都可以看作是一棵子树的根，该子树包含了以该节点为根的所有后代节点。

节点与边的关系：对于一棵有$n$个节点的树，其边的数量为$n-1$

节点和度的关系：总结点数 = 所有节点度数之和 + 1

• 树中所有节点的度数之和 == 树总边数边数

---

二叉树的性质：

二叉树遍历的性质：

1. 已知前序+中序，或后序+中序可以唯一确定一棵二叉树

2. 但前序+后序不能唯一确定二叉树（除非是满二叉树）

---

层节点数与层数的关系：在满二叉树中，满二叉树的第$k$层的节点数为$2^{k-1}$

• 扩展到二叉树：一棵非空二叉树的第$k$层上最多有$2^{k-1}$个结点

总节点数与高度的关系：
在满二叉树中，高度为$h$的满二叉树的总节点数为$2^h-1$

• 扩展到二叉树：一棵高度为$h$的二叉树最多有$2^h-1$个结点

在满二叉树中，具有$n$个结点的满二叉树的高度为${\log }_2(n+1)$

---

完全二叉树顺序特性：

对于具有$n$个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为$i$的结点有：

1. 双亲结点（父结点）：
   • 若 i = 0，该结点为根结点，无双亲结点
   • 若 i > 0，结点 i 的双亲结点序号为 (i-1)/2（向下取整）
2. 左孩子结点：
   • 若 2i + 1 >= n，则该结点无左孩子
   • 若 2i + 1 < n，则左孩子序号为 2i + 1
3. 右孩子结点：
   • 若 2i + 2 >= n，则该结点无右孩子
   • 若 2i + 2 < n，则右孩子序号为 2i + 2

总节点数与高度的关系：具有$n$个节点的完全二叉树的高度为$\lfloor {\log }_{2}n\rfloor +1$

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

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

特性	普通树	二叉树
节点最大度数	无限制	最多2
子树顺序	一般不区分	严格区分左右
空树	有些定义不允许	明确允许
存储结构	通常使用 孩子兄弟表示法	常用 左右指针法（二叉链）
遍历方式	无中序遍历	有中序遍历

二叉树怎么进行遍历？

二叉树的遍历：二叉树的遍历是指按照一定的规则和顺序，访问二叉树中的每个节点，且每个节点仅被访问一次。

根据节点访问顺序的不同，二叉树的遍历主要分为以下四类：

遍历方式	访问顺序	典型应用场景
前序遍历	根 → 左子树 → 右子树	复制树结构、前缀表达式（波兰式）
中序遍历	左子树 → 根 → 右子树	二叉搜索树的有序输出（升序/降序）
后序遍历	左子树 → 右子树 → 根	删除树结构、后缀表达式（逆波兰式）
层序遍历	按层次从上到下、从左到右	计算树的高度、广度优先搜索（BFS）

下面是一棵二叉树，大家可以自测一下自己是否已经掌握了二叉树的前/中/后序遍历：

答案：

前序：【1 2 3 # # # 4 5 # # 6 # #】

中序：【# 3 # 2 # 1 # 5 # 4 # 6 #】

后序：【# # 3 # 2 # # 5 # # 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; //注意：这里还是要注意不要忘记使用structstruct 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; //注意：这里还是要注意不要忘记使用structstruct 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：
typedef struct BinaryTreeNode* QDateType; //使用typedf重新定义队列中的变量的数据类型，方便后续进行修改//队列节点的结构体
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值为1if (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判断：如果遍历到的节点的值是xif (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.将队列结构体中“元素的数量”置为0pque->size = 0;//2.将队列结构体中“指向队头/队尾的指针”置为空指针pque->queHead = NULL;pque->queTail = NULL;
}//2.实现：“队列的销毁”操作
void QueDestroy(Que* pque)
{assert(pque);//1.将队列结构体中“元素的数量”置为0pque->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 Nprintf("\n");printf("中序遍历: ");InOrder(node1);		    // 预期输出：N 3 N 2 N 1 N 5 N 6 N 4 N 6 Nprintf("\n");printf("后序遍历: ");PostOrder(node1);       // 预期输出：N N 3 N 2 N N N 6 5 N N 6 4 1printf("\n");//2.测试树属性计算printf("节点总数: %d\n", BTSize(node1));       // 预期：7printf("叶子节点数: %d\n", BTLeafSize(node1)); // 预期：3（节点3、6、6）printf("树高度: %d\n", BTHeight(node1));       // 预期：4printf("第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 6printf("\n");//5.测试判断是否为完全二叉树if (BTComplete(node1))printf("该二叉树是完全二叉树\n");elseprintf("该二叉树不是完全二叉树\n");//6.测试二叉树销毁BTDestroy(node1);printf("二叉树已销毁\n");return 0;
}

运行成功样例