二叉搜索树（BST）的核心性质是左子树所有节点值小于根、右子树所有节点值大于根，且左右子树本身也必须是BST；其节点结构含val、left、right指针，BST类仅持根指针；关键操作中，插入按大小递归插入空位，查找可迭代实现，删除分无子、单子、双子三种情况处理，推荐用右子树最小值替代双子节点；中序遍历结果严格升序，可用于验证正确性。
二叉搜索树的核心性质
二叉搜索树（BST）不是普通二叉树，它有明确的大小约束：左子树所有节点值都小于根节点，右子树所有节点值都大于根节点，且左右子树本身也必须是BST。这个递归定义决定了插入、查找、删除都必须维护该性质，不能只看一层父子关系。
节点结构与基础框架
先定义一个简洁清晰的节点结构，用指针管理左右子树，避免裸指针裸删带来的风险：
// 节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {}
};
整个BST类只需持有一个指向根节点的指针，不额外存size或parent等字段——保持轻量，按需扩展。
立即学习“C++免费学习笔记（深入）”；
关键操作：插入、查找、删除
插入：从根开始比较，小则进左，大则进右，遇到空位置就新建节点。递归写法最直观：
- 若当前为空，直接返回新节点
- 若val小于当前节点值，递归处理左子树并更新left指针
- 若val大于当前节点值，递归处理右子树并更新right指针
- 相等时不插入（BST通常不允许重复值；如需支持，可加count字段）
查找：同样递归或迭代均可。迭代更省内存，逻辑直白：
- 从root出发，不为空时循环
- 相等则返回true；小于则跳left；大于则跳right
- 走到空指针说明不存在
删除是最易出错的部分，分三种情况处理：
- 待删节点无子节点：直接删，父节点对应指针置nullptr
- 只有一个子节点：用子节点替代自己（连上父节点，继承子树）
- 有两个子节点：找左子树最大值或右子树最小值来替换（二者都满足BST性质），再递归删除那个被挪走的节点
推荐统一用“右子树最小值”策略，实现稳定：
// 找右子树最小节点（中序后继）
TreeNode* findMin(TreeNode* node) {
while (node->left) node = node->left;
return node;
}
中序遍历验证BST正确性
BST的中序遍历结果一定是严格升序数组。这是调试和单元测试的重要依据：
- 递归中序：左 → 根 → 右，把val依次push_back到vector
- 运行后检查vector是否单调递增
- 也可用迭代+栈方式避免递归栈溢出（尤其深树场景）
不依赖输出，而是用prev_val记录前一个值，边遍历边比较，空间O(1)，适合大数据量校验。
基本上就这些。手写BST重在理解递归结构和边界处理，不必追求炫技，把插入、查、删三个函数写稳，再加个中序验证，就能覆盖95%的使用场景。
