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