【C++】模拟实现 二叉搜索树

Ne0inhk

— 14 min read
前言
二叉搜索树（Binary Search Tree，BST）作为一种经典的树形数据结构，凭借其高效的动态查找、插入和删除特性，在计算机科学领域有着广泛的应用。从底层实现来看，C++ 标准库中的 map、set、multimap、multiset 等关联式容器，其核心逻辑正是基于二叉搜索树（红黑树作为其平衡优化版本）构建。

相较于面向对象编程中的多态特性（侧重行为的动态绑定与代码复用），二叉搜索树聚焦于数据的有序存储与高效检索，其核心价值在于利用 “左子树值≤根节点值≤右子树值” 的结构性约束，将查找、插入、删除操作的时间复杂度控制在近似 O(logN)（理想的平衡状态下）；而在最坏的单支树场景下，时间复杂度退化为 O(N)，这也体现了数据结构设计中 “结构与性能” 的强关联性。

本文将从二叉搜索树的核心定义出发，逐步拆解节点设计、树的构建、插入、查找、删除等核心操作的实现逻辑，并区分 “仅存关键码（key）” 与 “键值对（key/value）” 两种典型应用场景，最终给出完整的可运行代码实现。代码实现过程中兼顾 C++11 语法特性（如 using 类型别名）、代码封装性（私有成员访问控制）与逻辑健壮性（边界条件处理），力求在清晰性与工程性之间找到平衡。

二叉搜索树

一、二叉搜索树的概念

二叉搜索树又称二叉排序树，满足以下核心特性：

  • 左子树不为空，则左子树上所有节点的值都小于等于根节点的值
  • 右子树不为空，则右子树上所有节点的值都大于等于根节点的值
  • 左右子树也分别为二叉搜索树

二叉搜索树中可以支持插入相同的值，也可以不支持插入相等的值。其中map、set、multimap、multiset系列的如期底层就是二叉搜索树，其中map、set不支持插入相等值，multimap、multiset支持插入相等的值。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

二、二叉搜索树的性能分析

最好情况：树的结构接近完全二叉树，高度为 logN，此时查找、插入、删除操作的时间复杂度为 O(logN)；
最坏情况：树退化为单支树，高度为 N，此时操作的时间复杂度退化为 O(N)。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

三、二叉搜索树的整体框架

3.1 节点

二叉搜索树本质是由节点连接而成的链式结构，每个节点包含关键码、左孩子指针、右孩子指针，具体实现如下：

#pragmaonce#include<iostream>usingnamespace std;// 二叉搜索树节点结构template<classK>structBSTNode{ K _key;// 节点存储的关键码 BSTNode<K>* _left;// 左孩子节点指针 BSTNode<K>* _right;// 右孩子节点指针// 构造函数：初始化节点BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};

3.2 树的类封装

将二叉搜索树封装为类，根节点作为私有成员（保证数据封装性），使用 C++11 的 using 简化节点类型名：

template<classK>classBSTree{using Node = BSTNode<K>;// C++11 类型别名，替代传统 typedefpublic:// 核心操作声明（插入、查找、删除、中序遍历）boolInsert(const K& key);boolFind(const K& key);boolErase(const K& key);voidInOrder();private:// 私有辅助函数：中序遍历的递归实现void_InOrder(Node* root); Node* _root =nullptr;// 根节点指针，初始化为空};

3.3 插入

插入逻辑：

  • 若树为空，直接创建新节点作为根节点；
  • 若树不为空，按二叉搜索树规则遍历：插入值大于当前节点则向右走，小于则向左走，找到空位置后插入新节点；

若不支持重复值插入，遇到与当前节点值相等的情况则返回插入失败。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
int a[]={8,3,1,10,6,4,7,14,13};
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传


外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
template<classK>boolBSTree<K>::Insert(const K& key){// 情况1：树为空，直接创建根节点if(_root ==nullptr){ _root =newNode(key);returntrue;}// 情况2：树不为空，遍历找到插入位置 Node* cur = _root; Node* parent =nullptr;// 记录当前节点的父节点（用于后续连接新节点）while(cur){if(cur->_key < key){ parent = cur; cur = cur->_right;// 大于当前节点，向右遍历}elseif(cur->_key > key){ parent = cur; cur = cur->_left;// 小于当前节点，向左遍历}else{// 找到相等值，不插入（若支持重复值，可改为向右/左遍历）returnfalse;}}// 找到空位置，创建新节点并连接到父节点 cur =newNode(key);if(parent->_key < key){ parent->_right = cur;// 新节点值更大，连接到父节点右孩子}else{ parent->_left = cur;// 新节点值更小，连接到父节点左孩子}returntrue;}

3.4 查找

  • 从根节点开始比较：查找值大于根节点则向右查找，小于则向左查找；
  • 遍历至空节点则说明查找失败，找到相等值则返回成功；

若支持重复值，通常要求返回中序遍历的第一个目标值（需额外逻辑，本文实现基础版）。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
template<classK>boolBSTree<K>::Find(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;// 大于当前节点，向右查找}elseif(cur->_key > key){ cur = cur->_left;// 小于当前节点，向左查找}else{returntrue;// 找到目标值，返回成功}}returnfalse;// 遍历至空，查找失败（补充原代码缺失的返回值）}

3.5 删除

删除逻辑：

  1. 先查找目标节点：不存在则返回失败；
  2. 存在则分三种情况处理（合并叶子节点与单孩子节点逻辑）：
    • 左孩子为空：将父节点的对应指针指向当前节点的右孩子，删除当前节点；
    • 右孩子为空：将父节点的对应指针指向当前节点的左孩子，删除当前节点；

左右孩子都不为空：采用 “替换法”—— 找右子树的最小节点（最左节点）或左子树的最大节点（最右节点）替换目标节点，再删除替换节点（替换节点必为单孩子 / 叶子节点）。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传


外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
template<classK>boolBSTree<K>::Erase(const K& key){ Node* cur = _root; Node* parent =nullptr;while(cur){if(cur->_key < key){ parent = cur; cur = cur->_right;}elseif(cur->_key > key){ parent = cur; cur = cur->_left;}else// 找到要删除的节点{// 情况1：左孩子为空（叶子节点/仅右孩子）if(cur->_left ==nullptr){// 处理根节点删除的特殊情况if(cur == _root){ _root = cur->_right;}else{// 父节点的左/右指针指向当前节点的右孩子if(parent->_left == cur){ parent->_left = cur->_right;}else{ parent->_right = cur->_right;}}delete cur;// 释放节点内存}// 情况2：右孩子为空（叶子节点/仅左孩子）elseif(cur->_right ==nullptr){// 处理根节点删除的特殊情况if(cur == _root){ _root = cur->_left;}else{// 父节点的左/右指针指向当前节点的左孩子if(parent->_right == cur){ parent->_right = cur->_left;}else{ parent->_left = cur->_left;}}delete cur;// 释放节点内存}// 情况3：左右孩子都不为空（替换法删除）else{// 找右子树的最小节点（最左节点）作为替换节点 Node* replaceParent = cur; Node* replace = cur->_right;while(replace->_left)// 遍历至右子树最左节点{ replaceParent = replace; replace = replace->_left;}// 替换目标节点的关键码 cur->_key = replace->_key;// 连接替换节点的父节点与替换节点的右孩子（替换节点左必为空）if(replaceParent->_left == replace){ replaceParent->_left = replace->_right;}else{ replaceParent->_right = replace->_right;}delete replace;// 释放替换节点内存}returntrue;// 删除成功}}returnfalse;// 未找到目标节点，删除失败}

3.6 中序遍历（验证二叉搜索树的有序性）

二叉搜索树的中序遍历结果为升序序列，是验证树结构正确性的核心方式。通过 “公有接口 + 私有递归函数” 的方式访问私有根节点：

template<classK>voidBSTree<K>::_InOrder(Node* root){if(root ==nullptr){return;}_InOrder(root->_left);// 遍历左子树 cout << root->_key <<" ";// 访问当前节点_InOrder(root->_right);// 遍历右子树}template<classK>voidBSTree<K>::InOrder(){_InOrder(_root);// 调用私有递归函数 cout << endl;}

四、二叉搜索树的两种应用场景

4.1 仅关键码（key）场景

核心特点

节点仅存储关键码 key，操作仅关注 “key 是否存在”，不支持修改 key（修改会破坏树的结构），支持增删查。

典型场景

  • 小区车库车牌验证：录入业主车牌，车辆进场时查找车牌是否存在；
  • 英文单词拼写检查：将词库单词存入树，遍历文章单词并查找，不存在则标红。

4.2 键值对（key/value）场景

核心特点

节点存储 key + value（value 为任意类型），增删查以 key 为关键字，支持修改 value（不修改 key）。

典型场景

  • 中英互译字典：key 为英文单词，value 为中文释义，查找 key 即可获取释义；
  • 停车计费系统：key 为车牌，value 为入场时间，离场时查找 key 计算停车时长；
  • 单词词频统计：key 为单词，value 为出现次数，查找单词存在则 value++。
// 键值对版本的节点结构template<classK,classT>structBSTNodeKV{ K _key; T _value; BSTNodeKV<K, T>* _left; BSTNodeKV<K, T>* _right;BSTNodeKV(const K& key,const T& value):_key(key),_value(value),_left(nullptr),_right(nullptr){}};// 键值对版本的二叉搜索树template<classK,classT>classBSTreeKV{using Node = BSTNodeKV<K, T>;public:// 插入键值对boolInsert(const K& key,const T& value){if(_root ==nullptr){ _root =newNode(key, value);returntrue;} Node* cur = _root; Node* parent =nullptr;while(cur){if(cur->_key < key){ parent = cur; cur = cur->_right;}elseif(cur->_key > key){ parent = cur; cur = cur->_left;}else{returnfalse;// 不支持重复key}} cur =newNode(key, value);if(parent->_key < key){ parent->_right = cur;}else{ parent->_left = cur;}returntrue;}// 查找key并返回value的指针（方便修改value） T*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{return&(cur->_value);// 返回value地址，支持修改}}returnnullptr;// 查找失败}// 删除（逻辑与key版本一致，略）boolErase(const K& key){ Node* cur = _root; Node* parent =nullptr;while(cur){if(cur->_key < key){ parent = cur; cur = cur->_right;}elseif(cur->_key > key){ parent = cur; cur = cur->_left;}else{if(cur->_left ==nullptr){if(cur == _root){ _root = cur->_right;}else{if(parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;}elseif(cur->_right ==nullptr){if(cur == _root){ _root = cur->_left;}else{if(parent->_right == cur) parent->_right = cur->_left;else parent->_left = cur->_left;}delete cur;}else{ Node* replaceParent = cur; Node* replace = cur->_right;while(replace->_left){ replaceParent = replace; replace = replace->_left;}// 替换key和value cur->_key = replace->_key; cur->_value = replace->_value;if(replaceParent->_left == replace) replaceParent->_left = replace->_right;else replaceParent->_right = replace->_right;delete replace;}returntrue;}}returnfalse;}// 中序遍历（打印key和value）voidInOrder(){_InOrder(_root); cout << endl;}private:void_InOrder(Node* root){if(root ==nullptr)return;_InOrder(root->_left); cout <<"key: "<< root->_key <<", value: "<< root->_value <<" ";_InOrder(root->_right);} Node* _root =nullptr;};

五、代码易错说明

  1. 代码规范性优化：
    • 类的成员函数声明与实现分离，提升代码可读性；
    • 变量命名语义化（如 replaceParent 替代原 parent，避免歧义）；
    • 补充关键逻辑注释，降低维护成本。
  2. 功能增强：
    • 键值对版本的查找函数返回 value 指针，支持修改 value；
    • 中序遍历打印 key 和 value，便于验证键值对的正确性。

六、使用示例

// 测试key版本的二叉搜索树voidTestBSTree(){ BSTree<int> t;int a[]={8,3,1,10,6,4,7,14,13};for(auto e : a){ t.Insert(e);} cout <<"中序遍历（升序）："; t.InOrder();// 输出：1 3 4 6 7 8 10 13 14 cout <<"查找6："<<(t.Find(6)?"成功":"失败")<< endl;// 成功 cout <<"删除3："<<(t.Erase(3)?"成功":"失败")<< endl;// 成功 cout <<"删除后中序遍历："; t.InOrder();// 输出：1 4 6 7 8 10 13 14}// 测试键值对版本的二叉搜索树voidTestBSTreeKV(){ BSTreeKV<string,int> dict; dict.Insert("apple",1); dict.Insert("banana",2); dict.Insert("orange",3); cout <<"中序遍历键值对："; dict.InOrder();// 输出：key: apple, value: 1 key: banana, value: 2 key: orange, value: 3// 修改banana的valueint* p = dict.Find("banana");if(p){*p =20;} cout <<"修改后中序遍历："; dict.InOrder();// 输出：key: apple, value: 1 key: banana, value: 20 key: orange, value: 3}intmain(){TestBSTree();TestBSTreeKV();return0;}

总结

二叉搜索树的核心是 “有序性”，其所有操作均围绕这一特性展开。本文实现的基础版本覆盖了二叉搜索树的核心功能，而实际工程中（如 C++ 标准库）会通过红黑树对其进行平衡优化，避免单支树的性能退化。理解二叉搜索树的底层逻辑，是掌握关联式容器、高效检索算法的关键基础。

Read more

Llama.cpp 全实战指南：跨平台部署本地大模型的零门槛方案

【个人主页：玄同765】 大语言模型（LLM）开发工程师｜中国传媒大学·数字媒体技术（智能交互与游戏设计） 深耕领域：大语言模型开发 / RAG知识库 / AI Agent落地 / 模型微调 技术栈：Python / LangChain/RAG（Dify+Redis+Milvus）| SQL/NumPy | FastAPI+Docker ️ 工程能力：专注模型工程化部署、知识库构建与优化，擅长全流程解决方案        「让AI交互更智能，让技术落地更高效」 欢迎技术探讨/项目合作！ 关注我，解锁大模型与智能交互的无限可能！ 摘要 本文全面解析轻量级大模型推理框架 Llama.cpp，详细讲解其在 Windows（Winget）、Linux、macOS 三大平台的安装步骤，针对新手优化了模型获取、文件整理、可视化部署的全流程，涵盖命令行交互、OpenAI

By Ne0inhk
AI编程工具对比：Cursor、GitHub Copilot与Claude Code

AI编程工具对比：Cursor、GitHub Copilot与Claude Code

文章目录 * AI编程工具对比：Cursor、GitHub Copilot与Claude Code * 一、产品定位与核心架构 * 1.1 Cursor：AI原生IDE的代表 * 1.2 GitHub Copilot：代码补全的行业标杆 * 1.3 Claude Code：终端Agent的革新者 * 二、核心功能深度对比 * 2.1 代码生成与理解能力 * 2.2 自动化与工作流集成 * 2.3 隐私与数据安全 * 三、成本效益分析 * 3.1 定价模式对比 * 3.2 投资回报比 * 四、适用场景与用户画像 * 4.1 最佳应用场景 * 4.2 用户反馈摘要 * 五、

By Ne0inhk

Copilot 的agent、ask、edit、plan模式有什么区别

Copilot 的 ask、edit、agent、plan 四种模式，核心区别在于权限范围、操作主动性、代码修改权限、适用场景，以下从定义、工作机制、核心特点、典型场景与操作流程展开，帮你快速区分并选对模式。 一、核心区别速览（表格版） 二、分模式详细解析 1. Ask 模式：纯问答与代码理解 * 工作机制：基于当前文件 / 选中代码的上下文，回答自然语言问题，不修改任何代码，仅输出文字解释、建议或思路。 * 典型用法： * 解释某段代码逻辑（如 “这段 Python 函数做了什么”）； * 咨询技术方案（如 “如何在 Go 中实现重试机制”）； * 调试思路（如 “这个死循环可能的原因”）。 * 关键特点：安全无风险，适合学习、快速澄清和非修改类咨询。

By Ne0inhk
AIGC时代：如何打造卓越的技术文档？

AIGC时代：如何打造卓越的技术文档？

文章目录 * 一、AIGC时代的技术文档规划布局：构建智能知识框架 * 宏观布局：智能绘制技术文档的蓝图 * 微观细节：智能剖析技术要点 * 二、AIGC时代的技术文档语言表达：智能描绘技术 * 专业术语：智能解释与链接 * 避免歧义：智能确保语言精确性 * 三、AIGC时代的技术文档更新与维护：智能保持时效性与实用性 * 及时更新：智能跟踪技术发展 * 版本控制：智能记录变化与演进历程 * 用户反馈：智能倾听与持续改进 在AIGC（人工智能生成内容）的浪潮中，技术的海洋变得更加广阔且深邃。每一片水域都蕴藏着无限的机遇与挑战，而一份出色的技术文档，就如同一位智慧的导航者，引领我们穿越复杂技术的迷雾，探索成功的彼岸。它不仅是知识传承的宝贵载体，更是团队协作的坚实桥梁，为产品的辉煌成就默默奠基。然而，在AIGC时代，如何制作一份既全面深入、又紧跟时代步伐，且易于理解的技术文档，成为了一项新的挑战。 一、AIGC时代的技术文档规划布局：构建智能知识框架 在AIGC时代，技术文档的规划布局需要更加智能化和系统化。一个清晰、智能的知识框

By Ne0inhk