《大话数据结构》第8章精读：二叉排序树（BST）完整 C++ 实现（插入、查找、删除、遍历）

发布时间：2026/9/24 20:51:14

《大话数据结构》第8章精读：二叉排序树（BST）完整 C++ 实现（插入、查找、删除、遍历）
1. 二叉排序树的定义进入《大话数据结构》第8章「查找」本章第一个重点就是二叉排序树Binary Sort Tree / Binary Search Tree简称 BST。它把“排序”和“查找”结合在一起是后续平衡二叉树、B 树等内容的基础。二叉排序树可以是一棵空树如果不是空树它必须满足以下性质若左子树不为空则左子树上所有节点的值均小于根节点的值若右子树不为空则右子树上所有节点的值均大于根节点的值左右子树本身也都是二叉排序树。关键结论对二叉排序树进行中序遍历会得到一个递增的有序序列。这也是它能够把“查找”和“排序”结合起来的重要原因。2. 节点定义与基本结构下面使用 C 定义 BST 节点。每个节点保存一个整型关键字以及指向左右孩子的两个指针。#include iostream #include queue using namespace std; struct BSTNode { int data; // 节点关键字 BSTNode *lchild; // 左孩子指针 BSTNode *rchild; // 右孩子指针 BSTNode(int d) : data(d), lchild(nullptr), rchild(nullptr) {} };说明data当前节点保存的值。lchild左孩子指针指向一棵更小的二叉排序树。rchild右孩子指针指向一棵更大的二叉排序树。构造函数使用初始化列表一次性完成成员初始化避免指针成为未初始化的野指针。3. BSTree 类与递归插入插入操作按“比较、递归、挂接”的思路进行如果当前节点为空就新建节点如果插入值小于当前节点则递归插入左子树如果大于当前节点则递归插入右子树如果相等通常不重复插入也可以根据业务需求进行更新。class BSTree { private: BSTNode* root; // 递归插入 BSTNode* insert(BSTNode* node, int key) { if (node nullptr) { return new BSTNode(key); } if (key node-data) { node-lchild insert(node-lchild, key); } else if (key node-data) { node-rchild insert(node-rchild, key); } // 相等则不插入或根据实际需求更新节点 return node; }插入元素{50, 30, 70, 20, 40, 60, 80}后会形成如下结构50 / \ 30 70 / \ / \ 20 40 60 80可以看到根节点 50 的左子树全部小于 50右子树全部大于 50每一棵子树也满足同样的性质。4. 递归查找查找操作与二分查找思想类似每次比较当前节点与目标值如果相等则查找成功如果目标值小于当前节点则进入左子树继续查找否则进入右子树继续查找。走到空指针仍未找到说明树中不存在该值。// 递归查找 BSTNode* search(BSTNode* node, int key) { if (node nullptr || node-data key) { return node; } if (key node-data) { return search(node-lchild, key); } else { return search(node-rchild, key); } }查找路径总是沿着“小于走左大于走右”的方向向下延伸。树的形态越接近完全二叉树查找效率越接近O(log n)。5. 查找最小节点在一棵二叉排序树中沿左孩子不断前进最后一个非空节点就是当前子树中的最小节点。这个操作在删除有两个孩子的节点时会反复用到。// 找到以 node 为根的子树中的最小节点 BSTNode* findMin(BSTNode* node) { while (node node-lchild) { node node-lchild; } return node; }也可以使用递归方式实现但这里使用循环更直观只要左孩子还存在就继续向左走。6. 递归删除删除是 BST 中最容易写错的操作核心在于处理目标节点的三种情况叶子节点、只有一个孩子的节点、有两个孩子的节点。// 递归删除 BSTNode* remove(BSTNode* node, int key) { if (node nullptr) return nullptr; if (key node-data) { node-lchild remove(node-lchild, key); } else if (key node-data) { node-rchild remove(node-rchild, key); } else { // 找到了要删除的节点 if (node-lchild nullptr) { // 只有右孩子或没有孩子 BSTNode* temp node-rchild; delete node; return temp; } else if (node-rchild nullptr) { // 只有左孩子 BSTNode* temp node-lchild; delete node; return temp; } else { // 有两个孩子用右子树最小节点替代 BSTNode* temp findMin(node-rchild); node-data temp-data; node-rchild remove(node-rchild, temp-data); } } return node; }三种情况可以总结为叶子节点直接删除。只有一个孩子用孩子顶替自己的位置。有两个孩子找到右子树中最小节点或左子树中最大节点用它的值覆盖当前节点再递归删除那个替身节点。建议删除有两个孩子的节点时一定要在草稿纸上画图模拟。比如删除根节点 50可以取右子树的最小节点 60 替换 50再把原来的 60 删除。7. 中序遍历与销毁中序遍历用于验证二叉排序树的有序性析构函数中需要递归释放整棵树避免内存泄漏。// 中序遍历验证有序性 void inOrder(BSTNode* node) { if (node) { inOrder(node-lchild); cout node-data ; inOrder(node-rchild); } } // 销毁整棵树 void destroy(BSTNode* node) { if (node) { destroy(node-lchild); destroy(node-rchild); delete node; } }后序遍历的思想也可以用于统计节点数量或计算树的高度。它们都属于“先处理子树再处理根节点”的典型递归结构。8. 对外接口类内部用递归实现具体逻辑对外提供简洁的公共接口。调用者不需要关心根指针和递归细节。public: BSTree() : root(nullptr) {} ~BSTree() { destroy(root); } void insert(int key) { root insert(root, key); } bool search(int key) { return search(root, key) ! nullptr; } void remove(int key) { root remove(root, key); } void inOrderTraverse() { cout 中序遍历; inOrder(root); cout endl; } };这样设计的好处是二叉排序树的递归逻辑集中在私有函数中公共接口只负责传入用户数据并更新根节点代码结构清晰也便于后续扩展为 AVL 树等平衡结构。9. 核心操作复杂度分析操作平均时间复杂度最坏时间复杂度说明查找O(log n)O(n)最坏情况下退化为链表插入O(log n)O(n)插入路径与查找路径一致删除O(log n)O(n)删除有两个孩子的节点时较复杂中序遍历O(n)O(n)一定能得到递增有序序列最坏情况通常发生在输入序列本身有序时。例如依次插入{10, 20, 30, 40, 50}二叉排序树会退化成一条链10 \ 20 \ 30 \ 40 \ 50此时查找、插入、删除的时间复杂度都会退化为 O(n)性能与普通链表相同。这也是后续必须学习 AVL 树、红黑树等平衡二叉树的根本原因。10. 完整测试代码下面给出完整的可运行程序覆盖插入、查找、删除和中序遍历。#include iostream #include queue using namespace std; struct BSTNode { int data; BSTNode *lchild, *rchild; BSTNode(int d) : data(d), lchild(nullptr), rchild(nullptr) {} }; class BSTree { private: BSTNode* root; BSTNode* insert(BSTNode* node, int key) { if (node nullptr) { return new BSTNode(key); } if (key node-data) { node-lchild insert(node-lchild, key); } else if (key node-data) { node-rchild insert(node-rchild, key); } return node; } BSTNode* search(BSTNode* node, int key) { if (node nullptr || node-data key) { return node; } if (key node-data) { return search(node-lchild, key); } else { return search(node-rchild, key); } } BSTNode* findMin(BSTNode* node) { while (node node-lchild) { node node-lchild; } return node; } BSTNode* remove(BSTNode* node, int key) { if (node nullptr) return nullptr; if (key node-data) { node-lchild remove(node-lchild, key); } else if (key node-data) { node-rchild remove(node-rchild, key); } else { if (node-lchild nullptr) { BSTNode* temp node-rchild; delete node; return temp; } else if (node-rchild nullptr) { BSTNode* temp node-lchild; delete node; return temp; } else { BSTNode* temp findMin(node-rchild); node-data temp-data; node-rchild remove(node-rchild, temp-data); } } return node; } void inOrder(BSTNode* node) { if (node) { inOrder(node-lchild); cout node-data ; inOrder(node-rchild); } } void destroy(BSTNode* node) { if (node) { destroy(node-lchild); destroy(node-rchild); delete node; } } public: BSTree() : root(nullptr) {} ~BSTree() { destroy(root); } void insert(int key) { root insert(root, key); } bool search(int key) { return search(root, key) ! nullptr; } void remove(int key) { root remove(root, key); } void inOrderTraverse() { cout 中序遍历; inOrder(root); cout endl; } }; int main() { BSTree tree; // 插入 int arr[] {50, 30, 70, 20, 40, 60, 80}; for (int x : arr) { tree.insert(x); } tree.inOrderTraverse(); // 应输出20 30 40 50 60 70 80 // 查找 cout 查找 40 (tree.search(40) ? 找到 : 未找到) endl; cout 查找 90 (tree.search(90) ? 找到 : 未找到) endl; // 删除 tree.remove(30); // 删除有两个孩子的节点 tree.inOrderTraverse(); // 20 40 50 60 70 80 tree.remove(50); // 删除根节点 tree.inOrderTraverse(); return 0; }程序运行结果如下中序遍历20 30 40 50 60 70 80 查找 40找到 查找 90未找到 中序遍历20 40 50 60 70 80 中序遍历20 40 60 70 80删除节点 30 后节点 40 顶替原 30 的位置删除根节点 50 后右子树中的最小节点 60 顶替根节点位置。最终中序遍历结果仍然保持递增有序。11. 删除操作的三种情况图解删除操作可以拆成三种典型情况建议对照代码逐一画图。11.1 删除叶子节点例如删除节点 20删除前 删除后 30 30 / \ / 20 40 40叶子节点没有孩子直接释放该节点并让父节点的对应指针置空。11.2 删除只有一个孩子的节点例如删除节点 30它只有一个右孩子 40删除前 删除后 30 40 \ 40此时只需用它的孩子顶替它自己的位置。11.3 删除有两个孩子的节点例如删除根节点 50删除前 删除后 50 60 / \ / \ 30 70 30 70 / \ / \ / \ \ 20 40 60 80 20 40 80找到右子树中的最小节点 60用 60 覆盖 50然后递归删除原 60。这样既能保持二叉排序树的有序性也避免直接调整大量节点的指针。12. 总结与思考二叉排序树把“查找”和“动态有序”很好地结合在一起平均性能优秀是实现动态查找表的经典结构。但它存在退化风险因此在工程实践中很少直接使用朴素 BST而是使用它的平衡版本如 AVL 树、红黑树、B 树等。结合《C Primer Plus》的思考递归实现插入、查找和删除充分练习了书中关于递归、指针和函数返回值传递的内容。删除时对节点三种情况的处理体现了细致的内存管理和指针维护能力。通过图例模拟树的形态变化有助于理解指针的挂接关系而不是只背代码。下一篇将按顺序继续第8章内容平衡二叉树AVL 树的旋转与实现重点解决朴素 BST 在有序插入时退化为链表的问题。

相关新闻

基于DeepSeek V4与LangChain构建低成本AI数据分析Agent实战

基于DeepSeek V4与LangChain构建低成本AI数据分析Agent实战

最近在尝试将国产大模型DeepSeek V4接入Codex平台，构建一个能够处理真实业务数据的AI数据分析系统时，发现网上资料要么过于零散，要么就是简单的API调用示例，对于如何设计一个完整的、可运行的Agent系统，特别是成本控制…

2026/9/24 17:41:04 阅读更多 →
Python开发工具全解析：从IDE选择到环境配置实战指南

Python开发工具全解析：从IDE选择到环境配置实战指南

1. 为什么Python开发者需要一个趁手的IDE？如果你刚开始学Python，可能觉得用记事本或者简单的文本编辑器写几行代码也能跑起来。但当你真正开始做一个项目，面对几十个文件、需要调试、需要管理依赖、需要版本控制的时候，一个强大的…

2026/9/23 22:51:15 阅读更多 →
一人公司如何用AgentOS构建自动化数字飞轮：架构设计与实战

一人公司如何用AgentOS构建自动化数字飞轮：架构设计与实战

1. 项目概述：一人公司的数字飞轮如何转动最近和几个独立开发者朋友聊天，大家普遍有个共鸣：一个人单打独斗做项目，精力太容易被琐事耗散。今天要处理服务器告警，明天要回复用户反馈，后天还得写更新日志。创意…

2026/9/23 15:20:40 阅读更多 →

最新新闻

Atlas 300V 24G推理卡部署YOLO指南：从环境搭建到调优

Atlas 300V 24G推理卡部署YOLO指南：从环境搭建到调优

Atlas 这个项目名字，说大不大，说小不小。如果你是因为“atlas部署yolo”和“atlas 300v 24g 是运算加速卡吗”这两个热搜摸进来的，那我估计你跟我当初一样，手里刚好拿到一张华为的 Atlas 300V 推理卡，或者正在选型阶段…

2026/9/25 5:49:36 阅读更多 →
Atlas 300V部署YOLO目标检测：从推理卡选型到性能调优全指南

Atlas 300V部署YOLO目标检测：从推理卡选型到性能调优全指南

最近项目里要在Atlas 300V 24G上跑YOLO目标检测，搜了一圈资料，发现很多人连这张卡是干嘛的都没搞清楚就上手买了。不少朋友看到“300V”和“24G”这两个数字，以为它就是张“高显存显卡”，结果拿到手发现既不能跑CUDA，也…

2026/9/25 5:49:36 阅读更多 →
Bottle 第三方插件生态指南：插件清单、安装管理与源码级机制解析

Bottle 第三方插件生态指南：插件清单、安装管理与源码级机制解析

后端Web框架 【免费下载链接】bottle bottle.py is a fast and simple micro-framework for python web-applications. 项目地址： https://gitcode.com/gh_mirrors/bo/bottle 点击查看 免费下载 Bottle 是一个快速、简洁的 Python 微框架，官方文档维护了…

2026/9/25 5:49:36 阅读更多 →
KL散度实战指南：从信息代价到CV/NLP模型诊断

KL散度实战指南：从信息代价到CV/NLP模型诊断

1. 这不是数学公式堆砌，而是你真正能用上的KL散度实战指南KL散度（Kullback-Leibler Divergence）这个词，在机器学习入门阶段几乎人人听过，但真正能说清“它到底在模型里干了什么”“为什么损失函数里突然冒出log p/q”“…

2026/9/25 5:49:36 阅读更多 →
React 360 多 Surface 与 3D 混合应用实战：MultiRoot 示例源码级解析

React 360 多 Surface 与 3D 混合应用实战：MultiRoot 示例源码级解析

前端3D渲染 【免费下载链接】react-360 Create amazing 360 and VR content using React 项目地址： https://gitcode.com/gh_mirrors/re/react-360 点击查看 免费下载 React 360 允许开发者在同一场景中挂载多个"根节点"（Root）&am…

2026/9/25 5:49:36 阅读更多 →
基于Simulink的倒立摆模糊控制：从建模到调参的完整实战指南

基于Simulink的倒立摆模糊控制：从建模到调参的完整实战指南

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/9/25 5:48:35 阅读更多 →

日新闻

AI元人文：从工具使用到思维重构的深度探索

AI元人文：从工具使用到思维重构的深度探索

最近半年我一直在琢磨一件事：AI元人文到底是什么？说白了，就是“用元视角重新审视人与AI的关系”，也在“探索AI如何反向逼着我们发现自己的思考边界”。标题里的“元探索”，在我看就是一层套一层的追问——当你用AI解决…

2026/9/25 0:00:41 阅读更多 →
Python+CNN车牌识别实战：从数据预处理到模型训练与部署

Python+CNN车牌识别实战：从数据预处理到模型训练与部署

简介：基于Python与卷积神经网络的车牌识别项目，面向计算机视觉初学者及智能交通开发者，目标是帮助用户掌握从数据预处理、模型构建到实际部署的完整流程。压缩包共25个文件，包含jpg/png图像样本、py训练脚本、md说明文档、dat数据…

2026/9/25 0:00:41 阅读更多 →
Vim基础操作全攻略：保存退出、模式切换与高频命令实战

Vim基础操作全攻略：保存退出、模式切换与高频命令实战

1. 项目概述1.1 核心需求解析今天聊聊Vim。写这个题目的原因是：几乎每个后端开发者、运维人员、数据工程师某天都会遇到一个场景——深夜加班，服务器登录界面只有黑底白字，编辑器只有vi/vim，你必须在五分钟内完成一次配置修改并保…

2026/9/25 0:00:41 阅读更多 →

周新闻

Flutter for OpenHarmony游戏卡片渐变背景实战：从原理到性能优化

Flutter for OpenHarmony游戏卡片渐变背景实战：从原理到性能优化

直接铺开项目本身吧。这几个月我一直在折腾一件事：用Flutter给OpenHarmony做一款游戏集合类的App，说白了就是把若干小游戏塞进一个壳里，用统一入口分发。这个方向本身不算新鲜，真正让我花了不少心思的，是首页那堆游戏卡…

2026/9/24 14:34:13 阅读更多 →
Word表格编号全攻略：从列表编号到题注交叉引用

Word表格编号全攻略：从列表编号到题注交叉引用

写Word文档，最让人头疼的往往是那些“看起来不起眼”的小问题。比如表格编号这事：今天在表后面多加了两个空白行，明天给客户交稿前发现整个章节的编号全部错位，光是挨个改序号就能耗掉大半个下午。我前阵子帮人整理一份上百页的技…

2026/9/24 9:10:42 阅读更多 →
从第一个站到第二个站：独立开发者的静态网站选型与落地实践

从第一个站到第二个站：独立开发者的静态网站选型与落地实践

1. 项目概述1.1 核心需求解析做独立开发者这几年，说实话，第一个网站上线的那天晚上我兴奋得没睡着。但等它跑了半年，流量惨淡、功能臃肿、代码自己都懒得看第二遍之后，我才慢慢琢磨明白一个道理：第一个网站是练手&…

2026/9/24 14:33:56 阅读更多 →

月新闻

持续集成 流水线自动化与 声明式交付 实践：原型怎样变成可用功能

持续集成 流水线自动化与 声明式交付 实践：原型怎样变成可用功能

持续集成 流水线自动化与 声明式交付 实践：原型怎样变成可用功能分类：[AI/大模型]细分主题：AI 增强型 CI/CD 流水线自动化与 GitOps 实践：Agent 工作流、工具调用与任务拆解：从原型到生产的验收清单很多团队在尝试用大…

2026/9/24 12:50:34 阅读更多 →
容器编排 生产环境运维与排障实战：复盘记录怎样真正派上用场

容器编排 生产环境运维与排障实战：复盘记录怎样真正派上用场

容器编排 生产环境运维与排障实战：复盘记录怎样真正派上用场分类：[工程技术]细分主题：Kubernetes 生产环境运维与排障实战：可复制的项目复盘模板与决策记录大部分团队的事故复盘报告，最后都变成了躺在 Confluence 或钉…

2026/9/24 14:33:48 阅读更多 →
容器 容器化技术与镜像安全管理：核心链路应该先拆哪一步

容器 容器化技术与镜像安全管理：核心链路应该先拆哪一步

容器 容器化技术与镜像安全管理：核心链路应该先拆哪一步分类：[工程技术]细分主题：Docker 容器化技术与镜像安全管理：核心链路的逐步实现与关键代码取舍面对一个积累了五六年历史包袱的单体架构应用（包含 Web 接口、后台…

2026/9/24 12:49:17 阅读更多 →