写在前面
前面的二叉树学习中，我们已经完成了链式二叉树的基本结构，并实现了前序、中序、后序、层序遍历，以及结点总数、叶子结点数、树高度、第 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 测试 BinaryTreeFind
BTNode* ret = BinaryTreeFind(root, 'E'); if (ret != NULL) { printf("找到了：%c\n", ret->data); } else { printf("没有找到\n"); }如果树中存在E，返回的不是一个简单的真假值，而是这个结点本身的地址。 因此后续还可以继续访问ret->left、ret->right、ret->data。
6.2 测试 BinaryTreeCreate
int 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 二叉树遍历
继续训练递归返回值、左右子树结果组合、双树递归比较以及前序序列建树等问题。
