二叉搜索树：高效增删查的秘诀

一、二叉搜索树 BST 定义二叉搜索树Binary Search Tree满足核心规则左子树所有节点值根节点值右子树所有节点值根节点值左右子树也同样满足以上规则关键特性BST 中序遍历结果 升序有序数组二、节点结构和普通二叉树节点完全一致struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };三、BST 查找操作思路比当前节点小 → 去左子树比当前节点大 → 去右子树相等 → 找到走到空 → 不存在cpp运行// 递归查找 TreeNode* searchBST(TreeNode* root, int val) { if(!root || root-val val) return root; if(val root-val) return searchBST(root-left, val); else return searchBST(root-right, val); }四、BST 插入操作思路按大小找位置遇到空节点直接新建节点挂上。TreeNode* insertBST(TreeNode* root, int val) { // 找到空位置新建节点 if(!root) return new TreeNode(val); if(val root-val) root-left insertBST(root-left, val); else if(val root-val) root-right insertBST(root-right, val); // 相等不插入 return root; }五、BST 删除操作面试重点分三种情况叶子节点直接删除只有左 / 只有右子树用子树顶替自己左右都有子树找右子树最小值或左子树最大值替换再删替补节点// 找右子树最小值节点 TreeNode* getMin(TreeNode* root) { while(root-left) root root-left; return root; } TreeNode* deleteBST(TreeNode* root, int val) { if(!root) return nullptr; if(val root-val) { root-left deleteBST(root-left, val); } else if(val root-val) { root-right deleteBST(root-right, val); } else { // 情况1叶子 / 只有单孩子 if(!root-left) return root-right; if(!root-right) return root-left; // 情况2左右都有孩子拿右子树最小值顶替 TreeNode* minNode getMin(root-right); root-val minNode-val; root-right deleteBST(root-right, minNode-val); } return root; }六、中序遍历验证有序性cpp运行void inOrder(TreeNode* root) { if(!root) return; inOrder(root-left); cout root-val ; inOrder(root-right); }七、完整测试代码#include iostream using namespace std; // 复制上面节点、查找、插入、删除、中序遍历函数 int main() { TreeNode* root nullptr; // 插入构建BST root insertBST(root,5); insertBST(root,3); insertBST(root,7); insertBST(root,2); insertBST(root,4); cout BST中序遍历(升序); inOrder(root); cout endl; // 删除节点3 root deleteBST(root,3); cout 删除3后中序遍历; inOrder(root); return 0; }八、BST 适用场景自动排序、有序数据维护高效查找、插入、删除 O (logn)C map /set 底层基于红黑树平衡 BST笔试面试常考手写 BST 增删查九、易错点总结忽略 BST 左小右大规则删除左右都有子树的节点不会找替补节点插入重复值不做判断破坏 BST 结构忘记中序遍历一定升序这个特性十、今日总结BST 核心规则左小右大中序遍历天然升序掌握查找、插入、删除三套递归模板删除三种情况是面试高频考点必须熟练