搜索二叉树（二叉搜索树，BST）绝对是数据结构里最经典、最值得手写模拟的题目之一。不管是考研、面试还是日常开发里自己造轮子，把BST的实现细节从头到尾摸一遍，很多和查找、插入、排序相关的算法题都会突然变得吃透了。这篇笔记我用“模拟实现”的方式，把BST的节点结构、插入、查找、遍历、删除，以及最容易翻车的细节全部拆开讲清楚，每段代码都可以直接跑、直接抄走。
1. 搜索二叉树笔记模拟实现：先盘清需求和设计思路
所谓“搜索二叉树笔记模拟实现”，本质就是用面向过程的编程语言（我这边用的是C++）把BST的核心行为从零搭一遍，不依赖任何库自带的高级数据结构，手动管理节点内存、手动写遍历逻辑、手动处理删除时的各种边界情况。这个名字叫“笔记”，说明定位是学习型项目，重点在透彻理解，而不是做一个生产级别的容器。
做这类模拟，目标函数很明确：五个操作必须有——插入、查找、中序遍历、删除、销毁整棵树。其中删除最要命，因为要分叶子节点、单孩子节点、双孩子节点三种情况处理，逻辑环环相扣，少一个分支就会出诡异结果。还有一个目标容易被忽略：代码必须“可调试”。如果写出来的二叉树，你画不出它的结构图，那排查问题就是盲人摸象。因此我会同步提供一个肉眼可验证的结构预览函数。
设计这套模拟时，我反复权衡的几个问题也在这里交代一下：
- 内存管理用裸指针还是智能指针？学习模拟用裸指针，敲一遍delete才能深刻理解生命周期。
- 递归还是迭代实现？插入查找遍历用手写递归，更好理解分治思想；删除必须支持递归回溯，因为删除后需要更新父节点指针。
- 节点结构带不带父节点指针？不带，因为在插入和删除时用引用传参或返回值替换就能解决父子关系问题，多一个指向反而容易维护混乱。
2. 节点结构设计：最小单元先搭稳
BST的节点只需要三样东西：一个数据域、一个左孩子指针、一个右孩子指针。有的实现会加一个parent指针方便部分操作，但我这次刻意不加，用引用传参和递归返回值的技巧来处理父子关系，这样代码体验更贴近教材原版思路。
#include <iostream> using namespace std; struct BSTNode { int val; BSTNode* left; BSTNode* right; explicit BSTNode(int v) : val(v), left(nullptr), right(nullptr) {} };构造函数加explicit是为了防止隐式转换带来意外构造，比如 BSTNode n = 5 这种写法不报错但容易埋雷，写代码时果断拦截。
节点这一层还要考虑一件事：析构。因为是裸指针，整棵树生命周期结束时必须手动释放。我用一个后序遍历的清理函数来处理，因为后序的顺序是“先左孩子、再右孩子、最后自己”，保证一个节点被删除时它的子树全都已经释放过了，不会出现访问已释放内存的悬垂问题。
void clearTree(BSTNode*& root) { if (root == nullptr) return; clearTree(root->left); clearTree(root->right); delete root; root = nullptr; }delete之后再置空是我排除了大量野指针问题后养成的习惯。很多人写delete只删不置空，continue执行后续代码时就容易踩到脏指针。
3. 插入节点：从零构建一棵树
插入规则很简单：从根开始比较，值比当前节点小就往左走，大就往右走，直到发现空位，新节点就安在这里。先看递归版本，这是理解度最高的写法。
void insertNode(BSTNode*& root, int value) { if (root == nullptr) { root = new BSTNode(value); return; } if (value < root->val) { insertNode(root->left, value); } else if (value > root->val) { insertNode(root->right, value); } else { // 如果相等，直接忽略，不插入重复值 return; } }这个版本最关键的细节是参数写法 BSTNode*& root，一个引用符号改变了一切。如果写的是 BSTNode* root，修改root等于修改形参副本，函数结束就丢了，原树不会有任何变化。这个坑几乎是每个人初学二叉树时都踩过的：代码跑完，树还是空树。加了引用后，root本身就能被赋值，指针的指向才能真正被修改。
另一种是迭代插入，用两个指针滚动前进，一个存储当前节点，一个存储当前节点的父节点。这样找到空位后，才能准确知道新节点挂在父亲的左边还是右边。
void insertNodeIter(BSTNode*& root, int value) { BSTNode* cur = root; BSTNode* parent = nullptr; while (cur != nullptr) { parent = cur; if (value < cur->val) { cur = cur->left; } else if (value > cur->val) { cur = cur->right; } else { return; // 重复值 } } BSTNode* node = new BSTNode(value); if (parent == nullptr) { root = node; } else if (value < parent->val) { parent->left = node; } else { parent->right = node; } }递归版本写起来更短，逻辑更清晰；迭代版本不依赖函数调用栈，极端情况下更省内存。学习阶段两种都建议敲一遍，笔试现场如果限制递归深度，就上迭代版。
4. 查找节点：按值定位，快就快在这里
查找和插入的路径一模一样，只是不建新节点了，找到返回true，走到空都没找到返回false。
bool searchNode(BSTNode* root, int target) { if (root == nullptr) return false; if (target == root->val) return true; if (target < root->val) return searchNode(root->left, target); return searchNode(root->right, target); }迭代版就更简单了，用一层while顺着大小关系一路走：
bool searchNodeIter(BSTNode* root, int target) { BSTNode* cur = root; while (cur != nullptr) { if (target == cur->val) return true; cur = (target < cur->val) ? cur->left : cur->right; } return false; }在删除操作里，我经常需要的不止是“是否存在”，而是“这个节点在哪、它的父节点是谁”。所以我实际写删除辅助层时，还会顺手封装一个返回节点指针的查找函数，让删除流程更干净。这里顺便提醒一句：BST的O(log n)查找复杂度依赖树形结构的平衡性，如果插入顺序恰好是1,2,3,4,5这种递增序列，树就会退化成一条链表，查找效率直接退化到O(n)。理解这个特性，后面看AVL树和红黑树的意义就会立体不少。
5. 遍历输出：用中序遍历检查树的“正确性”
BST有四种遍历方式：前序、中序、后序、层序。学习模拟阶段，中序是灵魂，因为中序输出就是从小到大的有序序列，它既是功能本身，又是验证整棵树结构是否正确的最强工具。
void inorderPrint(BSTNode* root) { if (root == nullptr) return; inorderPrint(root->left); cout << root->val << " "; inorderPrint(root->right); }为什么中序输出一定有序？因为中序遍历的顺序是“左子树、根、右子树”。而BST的定义恰恰是：左子树所有节点小于根，右子树所有节点大于根。所以对每个子树做中序，子树的输出天然就是从小到大的。这种“定义折叠成结果”的感觉，是递归结构特别漂亮的一个体现。
测试插入逻辑时，我用这组序列做过验证：5, 3, 8, 1, 4, 7, 9。插入完成后中序输出为：
1 3 4 5 7 8 9和排序结果完全吻合。这个验证办法强烈推荐每次插完都跑一遍，一眼就能看出树结构有没有问题。
6. 删除节点：最烦但也最核心的操作
删除操作是整个BST模拟中最容易写崩的地方。我先拆解逻辑，再给完整代码。
情况一：删叶子节点
叶子节点无左无右，直接delete，再把父节点指向它的指针置为nullptr。
情况二：删单孩子节点
节点只有一个左孩子或一个右孩子，类似于链表删节点，让唯一的孩子顶上去接替被删节点的位置。
情况三：删双孩子节点
这是重头戏。有两个孩子的节点不能直接拔掉，否则两棵子树都失联。正确做法是找一个替代者：右子树中的最小值，也就是中序后继。把后继的值灌进待删节点里，再去删除那个后继节点。因为后继一定是左孩子为空的节点，所以删除动作又退回成了“删除单孩子节点”或“删除叶子节点”，复杂度闭环了。
为什么不找左子树的最大值（前驱）？理论上也可以，效果一样，只是代码分支换个方向。但教材普遍使用后继，面试时你按后继讲最不容易被追问出bug。
直接看完整删除实现，我用递归加引用传参，把三种情况纳入同一套代码逻辑：
void deleteNode(BSTNode*& root, int value) { if (root == nullptr) return; if (value < root->val) { deleteNode(root->left, value); } else if (value > root->val) { deleteNode(root->right, value); } else { // 找到了目标节点 if (root->left == nullptr && root->right == nullptr) { delete root; root = nullptr; } else if (root->left == nullptr) { BSTNode* tmp = root; root = root->right; delete tmp; } else if (root->right == nullptr) { BSTNode* tmp = root; root = root->left; delete tmp; } else { // 两个孩子的节点：找右子树最小值 BSTNode* minNode = root->right; while (minNode->left != nullptr) { minNode = minNode->left; } root->val = minNode->val; deleteNode(root->right, root->val); } } }两个孩子的分支里，顺序必须先拷贝值，再递归删除右子树中那个具体的值。如果你先删了右子树的某个节点，再回来找最小值，那拿到的是脏数据，整个树直接崩掉。
我调试删除逻辑时固定的套路是构造七个节点的树，然后按叶子节点、单孩子节点、双孩子节点的顺序依次删除，每删一次跑一次中序输出。如果序列始终有序且元素数量对得上，说明删除逻辑是靠谱的。
7. 可视化打印与销毁：让树长啥样能看见
实验性质的项目，光有cout输出的序列还不够。我会额外写一个简单的树形打印函数，按“右-根-左”的顺序递归输出，把树的层级关系可视化出来，调试时非常直观，尤其是删除操作，结构变化一目了然。
void printTree(BSTNode* root, int depth = 0) { if (root == nullptr) return; printTree(root->right, depth + 1); for (int i = 0; i < depth; i++) cout << " "; cout << root->val << endl; printTree(root->left, depth + 1); }这段代码输出时会把右子树显示在上方，左子树在下方，根节点自然靠左突出，整体看起来像一棵侧躺的树。调试的时候特别有用，我可以看到每次插入后新节点是否准确挂到了对应位置，删除后子树是否真的接上了。
最后别忘了销毁整棵树。手动管理内存的代码，结尾必须释放。用前面写好的clearTree走一遍，处理完置空根指针，避免悬挂引用。
clearTree(root);8. 常见问题与排查思路实录
BST模拟实现里的坑其实很集中，翻来覆去就那么几类。我把高频问题整理成一个排查清单，按出现频率排序，逐条说清楚表象和成因，方便你遇到问题直接比对着处理。
问题一：插入后树是空的
现象很好认：中序输出什么都没有，查找也全部false。这是很多人遇到的第一个大坑。原因九成是插入函数的参数没有用引用。没有引用的函数修改的是形参副本，原树指针一动不动。解决方法是把参数改成 BSTNode*& root。
问题二：重复值导致无法判断对错
插入5、4、5，第二次插入5被忽略，树中只有一个5。如果你没在插入时分清相等分支，极端情况下会把重复值反复插入，破坏BST定义，甚至形成环。我在模拟里明确采用了“重复值直接忽略”的策略，复杂度可控，面试时也能说清楚。
问题三：删除双孩子节点后树中元素变少或变多
先确认中序序列有没有缺失重复。若变多，多半是双孩子分支里只用root->val = minNode->val，但没删掉原来的minNode节点，导致那个最小值节点还被保留。若变少，则是递归删除时删错了节点。解决办法是先把root被替代后的值算清，再递归到右子树删对应值。
问题四：层序输出乱序或漏节点
层序遍历需要用队列辅助，如果你只用了递归前序，输出顺序肯定不是层序。这不是bug，是遍历定义不同。模拟实验不用纠结，除非是做“按层打印”专题。
问题五：delete之后代码又访问节点内存
这个问题叫“悬垂指针”。delete只是释放内存，但指针变量本身还保留着旧地址。如果后续又用这个指针操作，内存访问行为完全不可预期。我每一处delete后都立即把指针置nullptr，就是为了堵住这个洞。虽然偶尔会多写一行，但换来得是能被安全操作的空指针。
9. 进一步思考：BST模拟完了，还有哪些进阶方向
能把插入、查找、中序遍历、删除四个核心功能完整模拟下来，知识框架已经合格了。但如果你想在数据结构这条路上继续加深，这几个方向建议按顺序往前推：
- 先实现“树高计算”和“节点计数”两个函数，强化递归收底逻辑。
- 再上手AVL树，在BST基础上给节点加平衡因子，插入删除后做旋转。
- 然后看红黑树，理解为什么工程中用红黑树而不用普通BST或严格AVL。
- 最后可以对比不同遍历方式的应用场景，比如前序序列化、后序销毁、中序排序。
这个路线不算陡，每一层都是用上一层的原理去解释下一层的设计，走完一轮，基本上数据结构里的树这部分就通透了一多半。
我个人每次重写BST模拟，最深的体会是：代码长度不是重点，重点是“每个边界条件的理由都说得清”。叶子节点为什么能直接删？单孩子节点为什么顶替不破坏排序？双孩子节点为什么要用后继替换？把这几个问题都自己解释一遍，比你硬背十遍代码都有用。
