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) {}
};
插入操作：递归实现，保持BST性质
从根开始比较，小于当前节点往左走，大于往右走；遇到空位置就新建节点插入。
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val val) {
root->left = insertIntoBST(root->left, val);
} else {
root->right = insertIntoBST(root->right, val);
}
return root;
}
立即学习“C++免费学习笔记（深入）”；
- 插入不改变原有结构，只新增叶子节点
- 重复值可按需求处理（如忽略、或允许重复并插入右子树）
- 非递归版本可用 while 循环 + 指针追踪父节点实现
查找操作：简单递归或迭代
利用BST有序性，每次比较后只进一个子树，时间复杂度平均 O(log n)。
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) return root;
if (val val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
- 返回匹配节点指针，未找到返回 nullptr
- 迭代写法更省内存：用 while 遍历，更新 root = root->left 或 root->right
删除操作：分三种情况处理
删除是 BST 最复杂的操作，需保证删除后仍为 BST。关键在“替代节点”的选择：
- 无子节点（叶子）：直接删，返回 nullptr
- 只有一个子节点：用该子节点顶替被删节点
- 有两个子节点：找左子树最大值（或右子树最小值）替换，再递归删除该替代值
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (key val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
// 找到要删除的节点
if (!root->left) return root->right;
if (!root->right) return root->left;
// 两个孩子：找左子树最大值（中序前驱）
TreeNode* predecessor = root->left;
while (predecessor->right) predecessor = predecessor->right;
root->val = predecessor->val;
root->left = deleteNode(root->left, predecessor->val);
}
return root;
}
注意：用右子树最小值（中序后继）同样可行，逻辑对称。选哪个取决于风格偏好，不影响正确性。
