写在前面前面的二叉树学习中我们已经完成了链式二叉树的基本结构并实现了前序、中序、后序、层序遍历以及结点总数、叶子结点数、树高度、第 K 层结点数等常见接口。这些接口解决的主要是两个问题如何遍历一棵已经存在的二叉树如何通过递归统计二叉树中的信息但一套相对完整的二叉树基础接口还需要解决另外几个很实际的问题给定一个值如何在二叉树中查找对应结点一棵动态申请出来的二叉树用完以后应该如何正确销毁如果给定一组带空结点标记的前序遍历序列如何重新构建出原来的二叉树因此本篇继续完善本地二叉树代码新增三个接口// 二叉树查找值为 x 的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树销毁 void BinaryTreeDestory(BTNode** root); // 通过前序遍历的数组构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);这三个接口虽然功能不同但本质上仍然离不开我们前面一直在使用的核心思想把一棵树的问题拆成「当前结点的问题 左子树的问题 右子树的问题」。本文全部代码已托管至 Gitee代码采用头文件与实现文件分离的模块化写法可直接拉取本地编译调试。Gitee 仓库地址数据结构/BinaryTree · Luminous/Code_2026 - 码云 - 开源中国一、二叉树查找递归结果不能丢1.1 问题分析现在有一棵普通二叉树希望查找值为 x 的结点。与二叉搜索树不同普通二叉树的结点并没有满足「左小右大」之类的顺序关系所以我们不能根据数值大小直接决定向左还是向右。因此只能逐个搜索先判断当前结点当前结点不是目标值就去左子树找左子树没找到再去右子树找。递归函数的定义可以理解为BinaryTreeFind(root, x)在以 root 为根的二叉树中寻找值为 x 的结点找到就返回该结点地址找不到返回 NULL。1.2 递归终止条件如果当前子树已经为空if (root NULL) return NULL;说明这一条路径走到底了并没有找到目标结点。如果当前根结点就是目标值if (root-data x) { return root; }那么直接返回当前结点即可。1.3 为什么左子树的返回值一定要保存接下来搜索左子树BTNode* leftRet BinaryTreeFind(root-left, x);这里不能只写BinaryTreeFind(root-left, x);因为递归函数真正有价值的内容不仅仅是「调用了一次」而是它返回的查找结果。 例如左子树深处真的找到了结点那么递归会一路把这个结点的地址向上传递。所以必须保存返回值BTNode* leftRet BinaryTreeFind(root-left, x);如果找到if (leftRet ! NULL) { return leftRet; }就不需要继续搜索右子树了。只有左子树没找到才搜索右子树BTNode* rightRet BinaryTreeFind(root-right, x); return rightRet;1.4 完整代码// 二叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) return NULL; if (root-data x) { return root; } // 先去左子树查找 BTNode* leftRet BinaryTreeFind(root-left, x); if (leftRet ! NULL) { return leftRet; } // 左子树没有找到再去右子树查找 BTNode* rightRet BinaryTreeFind(root-right, x); return rightRet; }实际上最后两行也可以直接写成return BinaryTreeFind(root-right, x);不过学习阶段保留rightRet能更直观地看出返回值是如何向上传递的。二、二叉树销毁为什么必须先销毁孩子前面的二叉树结点都是通过 malloc 动态申请出来的。 既然申请了堆空间在二叉树使用结束以后就需要主动释放否则会造成内存泄漏。那么问题来了应该按照什么顺序销毁二叉树2.1 不能先释放父结点假设直接这样写free(root); BinaryTreeDestory(root-left); BinaryTreeDestory(root-right);这是错误的。因为free(root);执行完成以后root 指向的结点空间已经释放。 这时候继续访问root-left、root-right就是访问已经失效的内存。因此父结点必须最后释放。 顺序应该是销毁左子树 ↓ 销毁右子树 ↓ 释放当前根结点这实际上就是后序遍历思想左 - 右 - 根。2.2 为什么销毁函数使用二级指针我们最终不仅希望释放结点还希望让外部保存的根指针变成NULL。假如函数写成void BinaryTreeDestory(BTNode* root)即使在函数内部写root NULL;修改的也只是形参 root 自己。 外部真正保存树根地址的指针并不会发生改变。这和我们之前学习顺序表、链表时遇到的指针传参问题是相同的。如果希望修改外部的BTNode* root;就需要把它的地址传进去BinaryTreeDestory(root);所以函数参数应该是BTNode** root。2.3 完整代码// 二叉树销毁 void BinaryTreeDestory(BTNode** root) { if (*root NULL) { return; } // 递归销毁左子树 BinaryTreeDestory((*root)-left); // 递归销毁右子树 BinaryTreeDestory((*root)-right); // 释放当前结点 free(*root); // 外部根指针置空 *root NULL; }这里(*root)-left表示把当前结点左孩子指针本身的地址传进去。 这样递归销毁左子树以后(*root)-left也会被自动置成 NULL右子树同理。最后再执行free(*root); *root NULL;最终整棵树销毁完成以后外部root NULL。三、为什么二叉树只靠普通前序遍历无法唯一构建接下来继续解决一个很重要的问题已知一棵树的前序遍历结果能不能把原来的树重新建出来例如ABC只知道序列A B C是不够的。 它可能是A / B / C也可能是A \ B \ C甚至还可能存在其他结构。问题就在于普通前序遍历只保存了非空结点没有记录空位置。因此为了能够还原树结构需要把空结点也记录下来。 例如规定#表示空树。假设一棵树为A / \ B C带空结点的前序序列就是AB##C##展开来看A B # # C # #这样每一个空位置都被保留下来了二叉树结构就可以唯一确定。四、根据前序序列递归建树我们希望实现BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);其中a保存前序遍历序列n数组长度pi当前读取位置的下标#表示空结点。4.1 为什么 pi 不能直接传 int假设写BTNode* BinaryTreeCreate(BTDataType* a, int n, int pi);那么每一次递归调用拿到的都是自己的局部副本。 左子树处理完以后右子树无法知道前面已经读取到什么位置。因此我们实际上希望整个递归过程中所有函数共享同一个遍历下标。所以需要传int* pi每处理一个字符执行(*pi);所有递归层看到的下标都会一起向后移动。4.2 建树递归过程首先判断是否越界if (*pi n) { return NULL; }如果当前位置是#表示这里应该是一棵空树if (a[*pi] #) { (*pi); return NULL; }注意即使遇到 #也必须让下标向后走一位。否则下一次递归仍然会读到同一个 #。4.3 创建当前根结点如果当前字符不是 #BTNode* newNode BuyBTNode(a[*pi]); (*pi);创建当前结点以后根据前序遍历「根 - 左 - 右」的顺序 先构建左子树newNode-left BinaryTreeCreate(a, n, pi);再构建右子树newNode-right BinaryTreeCreate(a, n, pi);最后把当前已经构建好的子树根结点向上返回return newNode;4.4 完整建树代码// 通过前序遍历的数组构建二叉树 // #代表空结点n为数组长度pi为下标指针 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { // 下标越界 if (*pi n) { return NULL; } // # 表示空结点 if (a[*pi] #) { (*pi); return NULL; } // 创建当前根结点 BTNode* newNode BuyBTNode(a[*pi]); (*pi); // 前序序列根 - 左 - 右 newNode-left BinaryTreeCreate(a, n, pi); newNode-right BinaryTreeCreate(a, n, pi); return newNode; }这里我把合并判断拆成了两个判断。 原因是*pi n表示已经没有字符可以读取这种情况下其实没有必要继续(*pi);分别处理会更加严谨。五、头文件新增接口在BinaryTree.h中加入// 二叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树销毁 void BinaryTreeDestory(BTNode** root); // 通过前序遍历的数组构建二叉树 // #代表空结点n数组长度pi下标指针 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);至此本地二叉树代码又补充了三个比较重要的基础功能。六、接口测试6.1 测试 BinaryTreeFindBTNode* ret BinaryTreeFind(root, E); if (ret ! NULL) { printf(找到了%c\n, ret-data); } else { printf(没有找到\n); }如果树中存在E返回的不是一个简单的真假值而是这个结点本身的地址。 因此后续还可以继续访问ret-left、ret-right、ret-data。6.2 测试 BinaryTreeCreateint main() { BTDataType a[] ABD##E##CF##G##; int i 0; BTNode* root BinaryTreeCreate( a, sizeof(a) / sizeof(a[0]) - 1, i ); BinaryTreePrevOrder(root); printf(\n); BinaryTreeInOrder(root); printf(\n); BinaryTreePostOrder(root); printf(\n); BinaryTreeDestory(root); return 0; }这样就可以完成完整流程字符序列 ↓ 递归构建二叉树 ↓ 遍历验证结构 ↓ 销毁整棵树七、三个接口背后的递归思想这一篇新增了三个接口看起来做的是三件完全不同的事情。 实际上把它们放在一起看会发现非常有意思。BinaryTreeFind函数负责在当前子树中找到目标结点并把结果返回给上一层。 核心是当前结点 ↓ 左子树查找 ↓ 右子树查找BinaryTreeDestory函数负责先处理完左右子树再释放自己。 核心是销毁左子树 ↓ 销毁右子树 ↓ 释放当前根BinaryTreeCreate函数负责根据当前位置创建当前结点再递归构建左右子树。 核心是创建当前根 ↓ 构建左子树 ↓ 构建右子树其实它们分别对应了非常典型的递归处理模式查找获得子问题结果销毁先解决子问题再解决当前问题建树先解决当前问题再创建子问题这也是学习二叉树以后递归思维开始真正变得清晰的地方。八、一个值得特别记住的递归细节这次实现BinaryTreeFind时有一个细节非常重要BTNode* leftRet BinaryTreeFind(root-left, x);为什么不能只写BinaryTreeFind(root-left, x);因为递归函数不仅仅是在「继续执行」还在向上返回答案。 如果返回值没有保存或者继续 return那么下面所有递归得到的答案都会被丢掉。这个问题在后面做二叉树题时会再次出现而且非常典型。 下一篇的 LeetCode 572. 另一棵树的子树我就因为没有正确处理递归返回值以及错误改变了 subRoot出现了错误。这也是为什么数据结构基础接口完成以后还需要专门通过题目继续训练递归。写在最后到这里我们继续完善了二叉树的三个基础接口BinaryTreeFind在普通二叉树中递归寻找目标结点BinaryTreeDestory使用后序思想释放所有动态结点BinaryTreeCreate根据带 # 的前序序列递归还原二叉树相比单纯记住代码更重要的是理解二叉树递归函数到底负责解决什么问题又应该把什么结果交给上一层。前面的遍历、结点统计、树高等问题让我们建立了最基础的递归框架而查找、销毁、建树则进一步说明递归既可以用来「读取树」也可以用来「修改树、创建树和释放树」。下一篇开始进入新的二叉树专题练习。 将通过LeetCode 965. 单值二叉树LeetCode 100. 相同的树LeetCode 572. 另一棵树的子树LeetCode 144. 二叉树的前序遍历TSINGK110 二叉树遍历继续训练递归返回值、左右子树结果组合、双树递归比较以及前序序列建树等问题。