一、前置准备：文件结构与核心定义
我们采用多文件工程实现，整体文件结构如下：
（1）Tree.h：二叉树结构体定义，所有接口声明
（2）Tree.c：二叉树所有接口的具体实现
（3）Queue.c/Queue.h：队列的实现，用于层序遍历。队列的实现方法在我的往期博客写过，这里就不多过多赘述。
（4）test.c：功能测试代码
1.1二叉树结构体定义（Tree.h）
1. 链式二叉树的核心是节点+指针
1. 每个节点保存自身数据，同时用两个指针分别指向左、右孩子节点；
2. 节点在内存中零散分布，通过指针建立父子关联，不需要连续内存，适配任意形态的二叉树；
3. typedef 重命名为 BTNode ，简化后续代码书写。
1.2队列改造：层序遍历的前置准备
层序遍历需要借助队列实现，但原本的队列默认存储 int 类型，现在需要存储二叉树节点指针。如果直接在 Queue.h 中包含 Tree.h ，会造成头文件循环包含（Tree.h包含Queue.h，Queue.h又包含Tree.h），导致编译报错。
解决方案：结构体前置声明，记得要注释掉Queue.h中原先给int起的别名，并且要在tree.h中包含Queue.h。
1. struct BinaryTreeNode 只是声明结构体名称，不引入完整定义，既让编译器认可「这是一个结构体指针类型」，又避免了循环包含；
2. 队列存储的是二叉树节点的地址，而非节点本身，通过指针即可访问节点的左右孩子，完美适配层序遍历的入队逻辑。
二、二叉树的基础创建
2.1节点申请函数BuyNode（在test.c中实现即可）
1. 用 malloc 在堆区申请一块节点大小的内存，初始化数据和左右指针；
2. 左右指针默认置空，避免野指针；
3. 封装成函数后，创建节点只需要调用 BuyNode(数据) ，代码复用性更强。
2.2手动构建测试二叉树
为了方便测试接口，我们手动创建一棵固定结构的二叉树：
三、二叉树的四大遍历方式
遍历是二叉树最基础、最重要的操作，核心思想是递归分治：把整棵树拆成「根节点+左子树+右子树」，子树重复同样的遍历逻辑。
3.1前序遍历（根左右）
访问顺序：根节点->左子树->右子树，按照我们给出的二叉树来看，前序遍历结果应该是：A B D NULL NULL E NULL NULL C F NULL NULL NULL
1. 递归必须有终止条件：节点为空时停止递归，否则会无限调用导致栈溢出；
2. 遵循「根左右」的顺序，先打印当前节点，再递归遍历左子树，最后递归右子树；
3. 空节点打印 NULL ，方便调试时观察树的结构。
3.2中序遍历（左根右）
访问顺序：左子树->根节点->右子树，按照我们给出的二叉树来看，中序遍历结果应该是：NULL D NULL B NULL E NULL A NULL F NULL C NULL
3.3后序遍历（左右根）
访问顺序：左子树->右子树->根节点，按照我们给出的二叉树来看，中序遍历结果应该是：NULL NULL D NULL NULL E B NULL NULL F NULL C A
三种递归遍历的核心区别：根节点的访问时机不同，左子树永远先于右子树访问。
3.4层序遍历（队列实现）
层序遍历是广度优先遍历，从上到下，从左到右逐层访问节点，无法用递归天然实现，必须借助队列（先进先出）完成。按照我们给的二叉树结构来实现，层序遍历：A B C D E F
1. 利用队列「先进先出」的特性：上一层节点按顺序入队，出队时把自己的孩子入队，天然保证逐层访问；
3. 每取出一个节点，就把它的左右孩子依次入队，保证下一层节点的顺序；
4. 遍历结束后必须销毁队列，释放堆内存。
四、二叉树核心计算接口
所有计算接口均采用递归分治思想：整棵树的结果 = 根节点的贡献 + 左子树结果 + 右子树结果。
4.1二叉树总节点数
整棵树的节点数 = 当前根节点（1个） + 左子树的总节点数 + 右子树的总节点数，空树返回0作为递归终止条件。
4.2二叉树叶子节点数
叶子节点：左右孩子都为空的节点
4.3二叉树第k层节点数
层数同步递减
当前节点在第1层，它的孩子在子树中就是第k-1层；递归到k=1时，说明到达目标层，计数加1。
4.4二叉树的深度/高度
取左右子树更高的那一侧
树的高度由更深的子树决定，根节点本身占1层高度，最终结果为左右子树高度的最大值加1。
4.5查找值为x的节点
1. 先判断当前节点是否为目标，再递归查找左右子树；
2. 左子树找到后直接返回，提前终止右子树的查找，提升效率；
3. 找不到最终返回空指针。
五、二叉树的销毁（二级指针详解）
销毁二叉树必须采用后序遍历的顺序：先销毁左子树、再销毁右子树、最后释放根节点。同时为了避免野指针，销毁后需要把外部的根指针置空。
为什么要用二级指针（传&root）？
（1）一级指针是值传递：函数内的 root 只是外部指针的拷贝，修改形参不会影响外部实参；
（2）二级指针是地址传递：通过 *root 可以直接修改外部原始指针变量，释放内存后把外部指针置为NULL，彻底杜绝野指针。
六、功能测试与运行结果
运行结果
七、全文总结
1. 链式二叉树通过节点+左右指针实现，适配任意形态的二叉树，是最通用的二叉树存储方式；
2. 前/中/后序遍历基于递归分治思想，核心区别是根节点的访问时机；
3. 层序遍历依托队列的先进先出特性实现，需要改造队列存储节点指针，并用前置声明避免头文件循环包含；
4. 节点计数、高度计算、节点查找均采用递归分治，把大问题拆解为左右子树的子问题；
5. 二叉树销毁采用后序遍历+二级指针，释放内存同时置空外部指针，避免野指针。
