【数据结构】二叉搜索树 C++ 简单实现：增删查改全攻略

二叉搜索树（Binary Search Tree, BST）的 C++ 简单实现
包含最常见的增、删、查、改操作，以及一些常用辅助函数。

以下代码尽量写得清晰、结构化，适合学习与理解。

#include<iostream>#include<queue>#include<vector>usingnamespacestd;// BST 节点定义structNode{intval;Node*left;Node*right;Node(intv):val(v),left(nullptr),right(nullptr){}};classBinarySearchTree{private:Node*root;// 辅助函数：递归插入Node*insertHelper(Node*node,intval){if(node==nullptr){returnnewNode(val);}if(val<node->val){node->left=insertHelper(node->left,val);}elseif(val>node->val){node->right=insertHelper(node->right,val);}// 相等时可以选择不插入（或覆盖/计数，此处选择不插入）returnnode;}// 辅助函数：查找节点（返回节点指针）Node*findHelper(Node*node,intval){if(node==nullptr||node->val==val){returnnode;}if(val<node->val){returnfindHelper(node->left,val);}else{returnfindHelper(node->right,val);}}// 辅助函数：找最小值节点（用于删除时找后继）Node*findMin(Node*node){while(node&&node->left){node=node->left;}returnnode;}// 辅助函数：删除节点（递归版）Node*removeHelper(Node*node,intval){if(node==nullptr){returnnullptr;}if(val<node->val){node->left=removeHelper(node->left,val);}elseif(val>node->val){node->right=removeHelper(node->right,val);}else{// 找到要删除的节点// 情况1：没有子节点（叶子）if(node->left==nullptr&&node->right==nullptr){deletenode;returnnullptr;}// 情况2：只有一个子节点elseif(node->left==nullptr){Node*temp=node->right;deletenode;returntemp;}elseif(node->right==nullptr){Node*temp=node->left;deletenode;returntemp;}// 情况3：有两个子节点 → 用右子树的最小节点替换else{Node*successor=findMin(node->right);node->val=successor->val;// 复制值node->right=removeHelper(node->right,successor->val);// 删除后继}}returnnode;}// 辅助函数：中序遍历（验证 BST 是否正确）voidinorderHelper(Node*node){if(node==nullptr)return;inorderHelper(node->left);cout<<node->val<<" ";inorderHelper(node->right);}// 销毁整棵树（析构函数调用）voiddestroyTree(Node*node){if(node==nullptr)return;destroyTree(node->left);destroyTree(node->right);deletenode;}public:BinarySearchTree():root(nullptr){}~BinarySearchTree(){destroyTree(root);}// 插入voidinsert(intval){root=insertHelper(root,val);}// 查找（是否存在）boolfind(intval){returnfindHelper(root,val)!=nullptr;}// 查找并返回节点指针（用于修改值）Node*findNode(intval){returnfindHelper(root,val);}// 删除voidremove(intval){root=removeHelper(root,val);}// 修改某个节点的值（先查找再修改）boolupdate(intoldVal,intnewVal){Node*node=findNode(oldVal);if(node==nullptr){returnfalse;}// 先删除旧值，再插入新值（最安全，避免破坏 BST 性质）remove(oldVal);insert(newVal);returntrue;}// 中序遍历（应该输出有序序列）voidinorder(){cout<<"中序遍历: ";inorderHelper(root);cout<<endl;}// 层序遍历（调试用）voidlevelOrder(){if(!root)return;queue<Node*>q;q.push(root);cout<<"层序遍历: ";while(!q.empty()){Node*node=q.front();q.pop();cout<<node->val<<" ";if(node->left)q.push(node->left);if(node->right)q.push(node->right);}cout<<endl;}// 判断是否为空boolempty()const{returnroot==nullptr;}// 获取根节点值（仅用于调试）intgetRootVal()const{returnroot?root->val:-1;}};// 测试代码intmain(){BinarySearchTree bst;// 插入测试vector<int>arr={50,30,70,20,40,60,80,15,25,35,45};for(intx:arr){bst.insert(x);}cout<<"插入后："<<endl;bst.inorder();// 应该有序bst.levelOrder();// 查找cout<<"\n查找 40: "<<(bst.find(40)?"存在":"不存在")<<endl;cout<<"查找 100: "<<(bst.find(100)?"存在":"不存在")<<endl;// 修改（把 40 改为 42）cout<<"\n修改 40 → 42: "<<(bst.update(40,42)?"成功":"失败")<<endl;bst.inorder();// 删除cout<<"\n删除 30："<<endl;bst.remove(30);bst.inorder();cout<<"\n删除 70（有两个孩子）："<<endl;bst.remove(70);bst.inorder();cout<<"\n删除 15（叶子节点）："<<endl;bst.remove(15);bst.inorder();return0;}

快速记忆要点（面试/刷题常用）

操作 | 时间复杂度（平均） | 时间复杂度（最坏） | 备注
—|—|—
查找 | O(log n) | O(n) | 最坏退化为链表
插入 | O(log n) | O(n) | 同上
删除 | O(log n) | O(n) | 两个孩子的情况最复杂
中序遍历 | O(n) | O(n) | 天然有序

常见面试追问方向

1. 如何判断一棵二叉树是否是 BST？（中序遍历是否严格递增）
2. 如何求 BST 的第 k 小元素？（中序遍历计数 / 记录子树大小）
3. BST 如何转成双向链表？（中序遍历 + 指针调整）
4. 如何在 BST 中找最近公共祖先？（类似二叉树 LCA，但利用大小关系更快）
5. 如何实现一个支持重复元素的 BST？（在 Node 中加 count 字段）

需要哪一部分再展开讲解（比如删除两种写法对比、平衡 BST 引出 AVL/红黑树、BST 转链表代码等），可以直接告诉我～