（注：本文代码均为c++）
一.链式结构二叉树
1.⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 ，
其结构如下：
优点：
①灵活存储：相比数组存储二叉树，链式结构在内存分配上更灵活，不需要预先分配连续的大块内存空间，适合存储节点数量不确定或动态变化的二叉树。
② 方便插入和删除：在插入或删除节点时，只需调整相关节点的指针，不需要像数组那样移动大量元素。
2.前，中，后序遍历
遍历规则（以上图二叉树为例）
按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：
1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前
访问顺序为：根结点、左⼦树、右⼦树
2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）
访问顺序为：左⼦树、根结点、右⼦树
3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后
访问顺序为：左⼦树，右子树，根结点。
（注：前中后序遍历是根据根结点的位置确定的。）
以前序遍历为例
代码实现了二叉树的前序遍历。程序先检查根节点是否为空，如果为空就输出 "nullptr" 并返回。若根节点不为空，就先输出根节点的数据，然后递归地对左子树和右子树进行前序遍历。通过这样的方式，就能按前序遍历的顺序访问二叉树的各个节点。
图解遍历
二叉树的前序遍历过程。上方的二叉树结构清晰，节点间通过 “递归” 和 “回退” 箭头相连，直观呈现遍历顺序。先访问根节点 1 ，接着递归访问左子树（节点 2 、 3 ），遇到空节点回溯，再递归访问右子树（节点 4 、 5 ）及对应空节点 。下方的函数调用图，以代码形式进一步细化，每个节点对应一次 Preorder 函数调用，详细展现了函数调用栈的展开与收缩，完整诠释了从根节点出发，先根、再左、后右的前序遍历逻辑，深刻理解递归在二叉树遍历中的精妙运用。
二.链式结构二叉树的模拟实现
① 头文件“Tree.h”
这是段代码，定义了二叉树相关的数据结构和遍历操作函数。通过 typedef 自定义了二叉树结点的数据类型 BTDataType ，并构建了二叉树结点结构体 BinaryTreeNode 。还声明了创建二叉树结点的函数 BTBuyNode ，以及二叉树前序遍历 PreOder 、中序遍历 InOder 、后序遍历 PostOder 函数，是二叉树算法实现的基础代码片段。
以上是一系列关于二叉树操作的 函数声明： ①BinaryTreeSize 用于统计二叉树的结点总数，通过递归遍历左右子树累加结点数实现； ②BinaryTreeLeafSize 专注于计算叶子结点个数，递归判断每个结点是否为叶子结点并计数；
③BinaryTreeLevelKSize 可求出二叉树第 k 层的结点数量，递归深入到指定层次进行统计 ；
④BinaryTreeDepth 用来确定二叉树的深度或高度，比较左右子树深度取大值并加上根节点层 ；
⑤BinaryTreeFind 能在二叉树中查找值为 x 的结点，通过递归在树中搜寻；
⑥BinaryTreeDestory 负责销毁二叉树，按后序遍历释放各结点内存，避免内存泄漏。
②“Tree.cpp”
第一段代码实现了 BTBuyNode 函数，用于申请二叉树结点。它通过 malloc 分配内存，若分配失败则打印错误信息并返回空指针，成功则初始化结点数据，将左右子树指针置空后返回新结点。
第二段代码是 PreOder 函数，实现二叉树的前序遍历。当根节点为空时输出 "nullptr" 并返回，否则先输出根节点数据，再递归对左子树、右子树进行前序遍历。
以上两段代码，分别实现二叉树的中序遍历与后序遍历。
InOder 函数用于中序遍历，若根节点为空，输出 "nullptr" 后返回；否则，先递归对左子树进行中序遍历，再输出根节点数据，最后递归对右子树进行中序遍历。
PostOder 函数实现后序遍历，根节点为空时同样输出 "nullptr" 并返回，接着先递归遍历左子树，再递归遍历右子树，最后输出根节点数据。
BinaryTreeSize 用于计算二叉树结点个数，采用递归方式，若根节点为空返回0，否则加上根节点及左右子树结点数。
BinaryTreeLeafSize 统计叶子结点个数，根节点为空返回0，是叶子结点返回1，否则递归计算左右子树叶子结点数之和。
BinaryTreeLevelKSize 计算二叉树第 k 层结点个数，根节点为空返回0， k 为1时返回1，否则递归计算左右子树第 k - 1 层结点数之和。
BinaryTreeDepth 函数用于计算二叉树的深度（高度），通过递归分别获取左、右子树的深度，取较大值并加1（根节点所在层）得到整棵树的深度。
BinaryTreeFind 函数则用于在二叉树中查找值为 x 的结点，递归遍历左右子树，一旦找到目标值所在结点即返回，若整棵树遍历完未找到则返回空指针。
BinaryTreeDestory 函数，用于销毁二叉树。它采用后序遍历的思路，先递归销毁左子树，再递归销毁右子树，确保子树结点都释放后，释放根节点所占用的内存，并将指向根节点的指针置为 nullptr ，有效避免内存泄漏。
③test.cpp
定义 CreateTree 函数，用于构建一棵二叉树。函数通过调用 BTBuyNode 依次创建包含字符 'A' 到 'F' 的结点，然后按照特定的父子关系将这些结点连接起来， nodeA 作为根节点，其左子树为 nodeB 、右子树为 nodeD 等 ，最终返回根节点 nodeA 。
构建一个用于测试二叉树操作的程序。
test 函数首先调用 CreateTree 函数创建一棵二叉树，并获取其根节点。
接着，程序对这棵二叉树进行多种操作测试：
执行前序遍历，通过 PreOder 函数输出二叉树的前序遍历结果，展示树的节点访问顺序。
利用 BinaryTreeSize 等函数，分别计算并输出二叉树的结点个数、叶子结点个数、第三层结点个数以及树的高度，全方位分析二叉树的结构特征。
通过 BinaryTreeFind 函数查找值为 'E' 的结点，根据查找结果输出“找到了”或“未找到”，验证二叉树的查找功能。
最后， main 函数调用 test 函数启动整个测试流程。
测试结果如下图所示：
