【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

深度解析 MySQL 与 MCP 集成：从环境构建到 AI 驱动的数据交互全流程

深度解析 MySQL 与 MCP 集成：从环境构建到 AI 驱动的数据交互全流程

前言 在当前大语言模型（LLM）应用开发的浪潮中，MCP（Model Context Protocol）协议正在成为连接 AI 模型与本地数据设施的关键桥梁。本文将以 MySQL 数据库为例，详细拆解如何通过 MCP 协议让 AI 模型直接操作关系型数据库，涵盖从服务器发现、数据库架构设计、数据初始化、MCP 配置文件编写到复杂自然语言查询与写入的全过程。 第一部分：MCP 服务器的发现与配置获取 在进行任何数据交互之前，首要任务是确立连接协议与服务源。通过蓝耘 MCP 广场，开发者可以快速检索并获取所需的 MCP 服务器配置。 在搜索栏输入 mysql 关键字，系统会立即检索出相关的 MCP 服务器资源。如下图所示，搜索结果中清晰展示了 MySQL 对应的 MCP 服务卡片。 点击选中该 MCP 服务器后，

By Ne0inhk
OpenClaw04_Gateway常见问题

OpenClaw04_Gateway常见问题

OpenClaw04_Gateway常见问题 文章目录 * OpenClaw04_Gateway常见问题 * 一、基础概念篇 * Q1: OpenClaw Gateway 是什么？它的核心职责是什么？ * Q2: Gateway 与 Agent 的关系是什么？为什么不能把 Gateway 当作 OpenClaw 的核心？ * Q3: Gateway 的默认端口是什么？Canvas Host 又是什么？ * 二、配置管理篇 * Q4: OpenClaw 的配置文件在哪里？是什么格式？ * Q5: 如何修改 Gateway 的监听端口和绑定地址？ * Q6: 配置更改后需要重启 Gateway 吗？ * Q7: 如何启动多个 Gateway 实例进行隔离测试？ * 三、路由与会话篇 * Q8: 什么是

By Ne0inhk
Spring AI 集成国内大模型实战：千问/豆包（含多模态）+ Spring Boot 4.0.1 全攻略

Spring AI 集成国内大模型实战：千问/豆包（含多模态）+ Spring Boot 4.0.1 全攻略

引言 Spring AI 作为 Spring 官方推出的 AI 开发框架，极大简化了 Java 开发者集成大模型的流程；而 Spring Boot 4.0.1 作为最新稳定版，凭借 Java 17+ 优化、原生镜像等特性，能让 AI 应用兼具开发效率与运行性能。 国内开发者常面临的痛点是：如何基于 Spring AI 适配阿里通义千问、字节豆包等本土化大模型？是否支持多模态（图文问答）能力？本文将从「环境准备→文本交互集成→多模态能力落地」全流程拆解，结合 Spring Boot 4.0.1 给出可直接复用的代码示例，覆盖国内模型的核心使用场景。 一、前置准备：

By Ne0inhk
Nacos - 构建 Spring Cloud Alibaba 服务发现体系

Nacos - 构建 Spring Cloud Alibaba 服务发现体系

👋 大家好，欢迎来到我的技术博客！ 💻 作为一名热爱 Java 与软件开发的程序员，我始终相信：清晰的逻辑 + 持续的积累 = 稳健的成长。 📚 在这里，我会分享学习笔记、实战经验与技术思考，力求用简单的方式讲清楚复杂的问题。 🎯 本文将围绕一个常见的开发话题展开，希望能为你带来一些启发或实用的参考。 🌱 无论你是刚入门的新手，还是正在进阶的开发者，希望你都能有所收获！ 文章目录 * Nacos - 构建 Spring Cloud Alibaba 服务发现体系 🚀 * 一、Spring Cloud Alibaba 与 Nacos 简介 🌐 * 1.1 Spring Cloud Alibaba 概述 * 1.2 Nacos 在 Spring Cloud Alibaba 中的角色 * 1.3 核心组件架构

By Ne0inhk