初学二叉搜索树踩坑多？C++ 从原理到代码，搞定增删查全流程

Ne0inhk

— 14 min read
初学二叉搜索树踩坑多？C++ 从原理到代码，搞定增删查全流程

个人主页



🎬 个人主页：Vect个人主页

🎬 GitHub：Vect的代码仓库
🔥 个人专栏: 《数据结构与算法》《C++学习之旅》《计算机基础》

⛺️Per aspera ad astra.

文章目录

1. 二叉搜索树相关概念

如下图所示，二叉搜索树(binary search tree)满足下列条件：

  1. 对于根节点，左子树中所有节点的值<根节点的值<右子树中所有节点的值
  2. 任意节点的左、右字数也是二叉搜索树，同样满足条件1
在这里插入图片描述

而下图就不是二叉搜索树：

在这里插入图片描述

2. 二叉搜索树的操作

我们将二叉搜索树封装为一个类BSTree，并声明一个_root变量，指向树的根节点

// 节点类template<classK>structBSTNode{ BSTNode<K>* _left; BSTNode<K>* _right; K _key;// 构造BSTNode(const K& val):_left(nullptr),_right(nullptr),_key(val){}};// 二叉搜索树类template<classK>classBSTree{public:typedef BSTNode<K> Node;private: Node* _root;};

2.1. 查找节点

给定目标val，可以声明一个节点cur，从二叉搜索树的根节点_root出发，循环比较cur._key和val之间的大小关系：

  • 若val < cur._key，说明目标节点在cur的左子树，执行cur = cur._left
  • 若val > cur._key，说明目标节点在cur的右子树，执行cur = cur._right
  • 若val == cur._key，说明找到目标节点，跳出循环并返回该节点

与二分查找原理一致，每轮排除一半的情况，当二叉树平衡时，循环次数最多为二叉树的高度， O ( l o g n ) O(logn) O(logn)

// 查找节点  Node*find(const K& val){ Node* cur = _root;while(cur){if(val < cur->_key) cur = cur->_left;elseif(val > cur->_key) cur = cur->_right;elsebreak;}return cur;}

2.2. 插入节点

给定一个待插入元素val，为了保持左子树<根节点<右子树的性质，插入流程如下：

  1. 查找插入位置： 与查找操作相同逻辑，从根节点出发，根据当前节点值和val的大小关系循环向下搜索，直到越过叶子节点（遍历到None）跳出循环
  2. 在该位置插入节点：new一个新节点，将新节点置于None的位置

注意：

  • 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
  • 为了实现插入节点，我们需要借助节点pre 保存上一轮循环的节点。这样在遍历至 None时，我们可以获取到其父节点，从而完成节点插入操作。
boolinsert(const K& val){// 空树 直接插入if(_root ==nullptr){ Node* newNode =newNode(val); _root = newNode;returntrue;}// 非空树 先找待插入节点的位置 Node* cur = _root; Node* curPre =nullptr;// 保存cur的父节点 while(cur){if(val == cur->_key)returnfalse;// 重复值 不插入elseif(val < cur->_key){// 小于键值 往左走 同时更新cur的父节点 curPre = cur; cur = cur->_left;}else{// 大于键值 往右走 同时更新cur的父节点 curPre = cur; cur = cur->_right;}}// cur的位置是待插入位置 Node* newNode =newNode(val);// 判断cur在curPre的左边还是右边 确定新节点位置if(curPre->_left == cur) curPre->_left = newNode;else curPre->_right = newNode;returntrue;}

2.3. 删除节点

先在二叉树中查找到目标节点，再将其删除。与插入节点一样，我们需要保证在删除操作完成后，保证二叉搜索树的“左子树 < 根节点 < 右子树”的性质不变

根据待删除节点的孩子数量，分0、1和2三种情况

  • 待删除结点是叶子节点，直接删除
在这里插入图片描述
  • 待删除节点有一个孩子，将待删除节点的子节点和其替换即可
在这里插入图片描述
  • 待删除节点2个孩子，不能直接删除，需要用一个节点替换该节点，保持“左子树 < 根节点 < 右子树”的性质不变，可以选择右子树最小节点或左子树最大节点

假设我们选择右子树最小节点，如下流程：

  1. 找到待删除节点cur的右子树最小节点rightMin
  2. 用rightMin的值覆盖cur，并删除rightMin
在这里插入图片描述

总共有如下几种情况：

cur 有两个孩子；rightMin 在更下方；rightMin 只有右孩子（B1）触发：cur->_right有左孩子，沿左链找到 rightMin，且 rightMin->_right != nullptr操作：cur->_key = rightMin->_key；令 rightMinPre->_left = rightMin->_right；删除 rightMin。示意：

cur(•) \ ... / rightMin \ X

cur 有两个孩子；rightMin 在更下方；rightMin 无右孩子（B0）触发：cur->_right有左孩子，沿左链找到 rightMin，且 rightMin->_right == nullptr操作：cur->_key = rightMin->_key；令 rightMinPre->_left = nullptr；删除 rightMin。示意：

cur(•) \ ... / rightMin

cur 有两个孩子；rightMin 就是 cur->_right；rightMin 只有右孩子（A1）触发：cur->_right没有左孩子，且 cur->_right->_right != nullptr操作：cur->_key = rightMin->_key；令 cur->_right = rightMin->_right；删除 rightMin。示意：

cur(•) / \ (...) rightMin \ X

cur 有两个孩子；右子树最小节点 rightMin 就是 cur->_right；rightMin 无右孩子（A0）触发：cur->_right没有左孩子，且 cur->_right->_right == nullptr操作：cur->_key = rightMin->_key；令 cur->_right = nullptr；删除 rightMin。示意：

cur(•) / \ (...) rightMin 
boolerase(const K& val){// 空树无法删除if(_root ==nullptr)returnfalse;// 查找待删除节点 Node* cur = _root; Node* curPre =nullptr;while(cur){if(val < cur->_key){// 向左找 curPre = cur; cur = cur->_left;}elseif(val > cur->_key){// 向右找 curPre = cur; cur = cur->_right;}elsebreak;// 命中}// cur为空 无法删除if(cur ==nullptr)returnfalse;// 找到cur了// 孩子0/1个的情况if(cur->_left ==nullptr|| cur->_right ==nullptr){// 找到待删除节点的孩子 Node* curNext = cur->_left ==nullptr? cur->_right : cur->_left;if(cur != _root){// 删除的不是根节点if(curPre->_left == cur) curPre->_left = curNext;else curPre->_right = curNext;}else{// 删除的是根节点 _root = curNext;}delete cur;}else{// 2个孩子// 1. 找右子树最小节点 Node* rightMin = cur->_right; Node* rightMinPre = cur;while(rightMin->_left){ rightMinPre = rightMin; rightMin = rightMin->_left;}// 2. 用rightMin的值覆盖待删除节点的值 cur->_key = rightMin->_key;// 3. 删除rightMin 要处理rightMin的孩子 Node* rightMinNext = rightMin->_right;if(rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;else rightMinPre->_right = rightMinNext;// 右子树最小节点是cur->_right的情况delete rightMin;}returntrue;}

再次总结：

查找阶段

  • 用 cur 定位待删，curPre 记录父。
  • 终止条件：命中或走到空。
  • 注意：若支持自定义比较器，等价判断应为“!(val<key) && !(key<val)”。

0/1 个孩子：真正移除 cur 节点

  • curNext = (cur->_left ? cur->_left : cur->_right)。
  • 若 cur != _root：把 curPre 的相应孩子指向 curNext。
  • 若 cur == _root：_root = curNext。
  • delete cur。
  • 要点：这是必须对“根”特判的地方（根没有父指针可改）。

2 个孩子：值覆盖 + 删后继（不移动 cur 本体）

  • 覆盖键值：cur->_key = rightMin->_key;（若有 value，一并拷/搬移）。
  • 要点：这里不需要根特判，因为根节点对象没被删除，只是“值被改写”。

删除 rightMin：

Node* rightMinNext = rightMin->_right; // 只可能有右孩子或空 if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext; else rightMinPre->_right = rightMinNext; // 当 rightMin 就是 cur->_right delete rightMin;

找右子树最小：

Node* rightMin = cur->_right; Node* rightMinPre = cur; while (rightMin->_left) { rightMinPre = rightMin; rightMin = rightMin->_left; }

3. 二叉搜索树的实现

#pragmaonce#include<iostream>#include<vector>usingnamespace std;namespace BSTKey {template<classK>structBSTNode{ BSTNode<K>* _left; BSTNode<K>* _right; K _key;// 构造BSTNode(const K& val):_left(nullptr),_right(nullptr),_key(val){}};template<classK>classBSTree{public:typedef BSTNode<K> Node;BSTree()=default;// 析构 需要辅助析构函数~BSTree(){destroy(_root); _root =nullptr;}// 查找节点  Node*find(const K& val){ Node* cur = _root;while(cur){if(val < cur->_key) cur = cur->_left;elseif(val > cur->_key) cur = cur->_right;elsebreak;}return cur;}boolinsert(const K& val){// 空树 直接插入if(_root ==nullptr){ Node* newNode =newNode(val); _root = newNode;returntrue;}// 非空树 先找待插入节点的位置 Node* cur = _root; Node* curPre =nullptr;// 保存cur的父节点 while(cur){if(val == cur->_key)returnfalse;// 重复值 不插入elseif(val < cur->_key){// 小于键值 往左走 同时更新cur的父节点 curPre = cur; cur = cur->_left;}else{// 大于键值 往右走 同时更新cur的父节点 curPre = cur; cur = cur->_right;}}// cur的位置是待插入位置 Node* newNode =newNode(val);// 判断cur在curPre的左边还是右边 确定新节点位置if(curPre->_left == cur) curPre->_left = newNode;else curPre->_right = newNode;returntrue;}boolerase(const K& val){// 空树无法删除if(_root ==nullptr)returnfalse;// 查找待删除节点 Node* cur = _root; Node* curPre =nullptr;while(cur){if(val < cur->_key){// 向左找 curPre = cur; cur = cur->_left;}elseif(val > cur->_key){// 向右找 curPre = cur; cur = cur->_right;}elsebreak;// 命中}// cur为空 无法删除if(cur ==nullptr)returnfalse;// 找到cur了// 孩子0/1个的情况if(cur->_left ==nullptr|| cur->_right ==nullptr){// 找到待删除节点的孩子 Node* curNext = cur->_left ==nullptr? cur->_right : cur->_left;if(cur != _root){// 删除的不是根节点if(curPre->_left == cur) curPre->_left = curNext;else curPre->_right = curNext;}else{// 删除的是根节点 _root = curNext;}delete cur;}else{// 2个孩子// 1. 找右子树最小节点 Node* rightMin = cur->_right; Node* rightMinPre = cur;while(rightMin->_left){ rightMinPre = rightMin; rightMin = rightMin->_left;}// 2. 用rightMin的值覆盖待删除节点的值 cur->_key = rightMin->_key;// 3. 删除rightMin 要处理rightMin的孩子 Node* rightMinNext = rightMin->_right;if(rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;else rightMinPre->_right = rightMinNext;// 右子树最小节点是cur->_right的情况delete rightMin;}returntrue;}voidinOrder(){_inOrder(_root); cout << endl;}private: Node* _root;// 后续析构voiddestroy(Node* root){if(root ==nullptr)return;destroy(root->_left);destroy(root->_right);delete root;}void_inOrder(Node* root){if(root ==nullptr)return;_inOrder(root->_left); cout << root->_key <<" ";_inOrder(root->_right);}};voidtestBST(){ BSTree<int> bst; vector<int> arr ={8,3,10,1,6,14,5,7,13}; cout <<"=== 1. 创建二叉搜索树 ===\n"; cout <<"初始数据：-> ";for(constauto& e : arr) cout << e <<" "; cout <<"\n创建完成数据：-> ";for(constauto& e : arr) bst.insert(e); bst.inOrder(); cout <<"=== 2. 查找数据 ===\n"; cout <<"查找不存在数据：28 查找结果："<< bst.find(28)<< endl; cout <<"查找存在数据：14 查找结果："<< bst.find(14)<< endl; cout <<"\n=== 3. 删除数据 ===\n"; cout <<"删除前的序列：->"; bst.inOrder(); cout <<"删除节点6后的序列：->"; bst.erase(6); bst.inOrder(); cout <<"删除不存在的节点86后的序列：->"; bst.erase(86); bst.inOrder(); cout <<"\n销毁二叉树：->"; bst.~BSTree(); bst.inOrder();}}

4. 二叉搜索树的应用

4.1. K模型

只有key作为关键码（需要搜索到的值），结构中只存储key即可

例如：给一个单词word，判断该单词是否正确

  • 以词库中所有单词集合中的每个单词作为key，构建一颗二叉搜索树
  • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

又比如门禁系统，只关注对象在不在

第三节实现的就是K模型

4.2. KV模型

每个关键码key，都有与之对应的值value，即<key，value>的键值对，例如：

  • 简单英汉词典中英文和中文是相互对应的关系，通过英文可快速找到其对应的中文，例如：<book,书>就是一种键值对
  • 车库收费系统，一个键值记录车牌号，另一个键值记录停留时间，随后交给收费系统处理缴费事宜
  • 统计单词出现次数，统计成功之后，给定单词就可快速找到其出现的次数，单词与其出现的次数就是<word,count>一种键值对

我们将K模型改造成KV模型

template<classK,classV>structBSTNode{ K _key; V _value; BSTNode<K, V>* _left; BSTNode<K, V>* _right;BSTNode(const K& k,const V& v):_key(k),_value(v),_left(nullptr),_right(nullptr){}};template<classK,classV>classBSTree{public:typedef BSTNode<K, V> Node;// ... 接口实现private: Node* _root =nullptr;// ...辅助接口实现}};
// 输入中文 输出对应英文voiddictionary(){ BSTree<string, string> dict; dict.insert("书包","bag"); dict.insert("水果","fruit"); dict.insert("钢笔","pen"); dict.insert("书","book"); dict.insert("树","tree");// 插入词库中所有单词 string str;while(cin >> str){auto ret = dict.find(str);if(ret ==nullptr) cout <<"输入错误或词库中未包含该词"<< str << endl;else cout << str <<"英文单词：->"<< ret->_value << endl;}}// 计数voidcount(){ string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"}; BSTree<string,int> cntTree;for(constauto& s : arr){// 先查找水果在不在搜索树中// 1. 不在，说明水果第一次出现，则插入<水果, 1>// 2. 在，则查找到的节点中水果对应的次数++auto ret = cntTree.find(s);if(ret ==nullptr) cntTree.insert(s,1);else ret->_value++;} cntTree.inOrder();}

完整代码请详见此链接：二叉搜索树
二叉搜索树的核心价值，在于用 “左子树 < 根节点 < 右子树” 的简单规则，换来了查找、插入、删除操作的高效性 —— 平衡状态下$ O (logn)$ 的时间复杂度，让它成为处理动态数据查找场景的基础选择。无论是仅需判断 “存在性” 的 K 模型，还是需键值关联的 KV 模型，都能通过其核心操作快速适配，覆盖词典查询、计数统计等常见需求。

但需注意，二叉搜索树的性能依赖结构平衡：若插入数据有序，会退化为单链表，此时操作复杂度飙升至 O ( n ) O(n) O(n)。这也催生了 AVL 树、红黑树等平衡二叉搜索树 —— 它们通过自平衡机制维持树的高度，兼顾了二叉搜索树的简洁性与稳定高效的性能，是后续深入学习的重要方向。

Read more

基于YOLO26/11/v8算法的Web目标检测系统，人脸表情识别系统，Django+Vue3 的前后端分离，实现摄像头实时识别，YOLO26/YOLO11/v8 + LLM大模型智能分析，科研必备

基于YOLO26/11/v8算法的Web目标检测系统，人脸表情识别系统，Django+Vue3 的前后端分离，实现摄像头实时识别，YOLO26/YOLO11/v8 + LLM大模型智能分析，科研必备

✨ 更新日志 * ✔️ 2026/3/3，2.0 版本，前端导航栏改为侧边栏系统，视频流采用websocket框架延迟更低， YOLO26/YOLO11/YOLOv8 视频流更稳定，在之前的系统增加 LLM 大模型智能分析，是科研必备，支持 YOLO26/11/v8 分类模型、目标检测、分割、obb、关键点检测任务，还支持双模型联合检测与识别，如人脸表情识别、人脸识别等一些识别任务需要检测模型与分类模型共同完成，在人脸表情识别中，单独使用检测模型去识别人脸表情也不是不可以，但有一个问题数据集如果全是头部照片的话，当模型预测的照片是全身照片时，模型识别准确率就没有这么高了， 那么这时候可以用检测模型识别人脸，把人脸信息输入到表情分类模型进行分类即可，反正这是一个通用的系统，更换自己模型即可，大家懂得都懂的，更多功能看下文即可。 摘要 在人工智能迈向通用化（AGI）的今天，“视觉感知 + 语言理解”的多模态联合是未来的趋势。单纯的检测画框已经无法满足复杂的业务需求，如何让系统“看懂”

By Ne0inhk

Rembg WebUI响应式设计：多设备适配方案

Rembg WebUI响应式设计：多设备适配方案 1. 智能万能抠图 - Rembg 在图像处理与内容创作日益普及的今天，自动去背景技术已成为设计师、电商运营、AI开发者不可或缺的工具。传统手动抠图效率低、成本高，而基于深度学习的智能抠图方案正逐步成为主流。其中，Rembg 凭借其开源、高精度和通用性强的特点，迅速在开发者社区中脱颖而出。 Rembg 的核心是 U²-Net（U-square Net） 模型，一种专为显著性目标检测设计的嵌套 U-Net 架构。该模型通过双层嵌套残差模块，在不依赖大量标注数据的前提下，实现对图像主体的精准识别与边缘提取。无论是人像发丝、宠物毛发，还是复杂轮廓的商品，Rembg 都能生成高质量的透明 PNG 图像，满足工业级应用需求。 更重要的是，Rembg 支持本地部署、无需联网验证权限，并可集成 ONNX 推理引擎进行 CPU 优化，极大提升了服务的稳定性与可移植性。

By Ne0inhk

前端人拿不到offer，九成是不知道这个新风向

今年大部分互联网公司面试的题目已经开始小部分八股文，大部分场景题了，公司需要的不仅是知识扎实，而且招进来就能上手项目的面试者… 2026最新高频场景题 * 1. 请求失败会弹出一个toast,如何保证批量请求失败，只弹出一个toast * 2. 如何减少项目里面if-else * 3. babel-runtime 作用是啥 * 4. 如何实现预览PDF文件 * 5. 如何在划词选择的文本上添加右键菜单(划词:鼠标滑动选择一组字符，对组字符进行操作) * 6. 富文本里面，是如何做到划词的(鼠标滑动选择一组字符，对组字符进行操作)? * 7. 如何做好前端监控方案 * 8. 如何标准化处理线上用户反馈的问题 * 9. px如何转为rem * 10. 浏览器有同源策略，但是为何 cdn 请求资源的时候不会有 跨域限制 * 11. cookie可以实现不同域共享吗 * 12. axios是否可以取消请求 * 13. 前端如何实现折叠面板效果? * 14. dom里面，如何判定a元素是否是b元素的子元 * 15. 判断一个对象是否为空，包含了其原型链上是否有自

By Ne0inhk

1Panel+Ollama+WebUI：打造本地AI模型的完整指南（附Gemini插件教程）

1Panel、Ollama与Open WebUI：构建你的私有化AI模型应用平台实战 在AI技术日益普及的今天，许多开发者和技术爱好者不再满足于仅仅调用云端API。他们渴望在本地环境中部署、管理和实验自己的AI模型，无论是出于数据隐私的考量、网络环境的限制，还是纯粹对技术探索的热爱。构建一个稳定、易用且可扩展的本地AI平台，成为了一个极具吸引力的目标。本文将为你呈现一套完整的解决方案，它并非简单的工具堆砌，而是一个经过精心设计的、以1Panel为控制中枢，Ollama为模型引擎，Open WebUI为交互前端的集成化平台。我们将深入探讨如何将它们无缝衔接，并重点解锁通过插件系统集成如Gemini等第三方模型的高级玩法，让你在本地也能拥有媲美云端服务的AI应用体验。 1. 平台基石：1Panel与OpenResty的部署与配置 构建任何复杂应用，一个稳定且管理便捷的基础环境是首要前提。1Panel作为一个现代化的Linux服务器运维管理面板，以其直观的Web界面和容器化应用管理能力，极大地简化了服务器运维工作。而OpenResty，作为Nginx的增强版本，集成了LuaJIT，为

By Ne0inhk