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

发布时间：2026/10/17 2:35:15

《大话数据结构》第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/10/15 8:37:21 阅读更多 →
Python开发工具全解析：从IDE选择到环境配置实战指南

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

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

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

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

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

2026/10/16 10:45:23 阅读更多 →

最新新闻

UGUI撞上DOTS：Canvas性能黑洞与ECS渲染管线重构

UGUI撞上DOTS：Canvas性能黑洞与ECS渲染管线重构

简介：UGUIDots 是一套面向数据技术栈（DOTS）的 UI 解决方案，专为希望在 Unity 中兼顾 UGUI 工作流与 ECS 性能的开发者设计。它并非替代 Unity 原生 UI，而是在其基础上扩充，让 UI 设计流程基本保持不变&…

2026/10/17 2:34:37 阅读更多 →
科捷智能职位分析：售后服务工程师

科捷智能职位分析：售后服务工程师

本文基于科捷智能官方最新工作职责、任职资格撰写，精准聚焦新能源事业部锂电配套智能仓储物流设备售后场景，针对性拆解岗位定位、必备专业知识、核心实操技能、岗位职责、简历优化方案、高频面试真题及应答技巧，完全贴合企业用人标准与现场工…

2026/10/17 2:34:37 阅读更多 →
科捷智能职位分析：电气工程师（新能源事业部）

科捷智能职位分析：电气工程师（新能源事业部）

本文基于科捷智能官方工作职责与任职资格撰写，精准聚焦新能源事业部锂电赛道，主打锂电化成分容、原材料库、集片库、新能源仓储物流自动化电气设计与调试岗位。全面拆解岗位定位、专业知识、核心技能、工作权责、简历优化、高频面试题与应答技巧&#xf…

2026/10/17 2:34:37 阅读更多 →
动力电池膨胀深度拆解(01)：物理化学本质 - 嵌锂膨胀与产气膨胀的力学逻辑与判定阈值

动力电池膨胀深度拆解(01)：物理化学本质 - 嵌锂膨胀与产气膨胀的力学逻辑与判定阈值

LFP电芯的体积变化由两条本质不同的主线叠加而成：可逆的嵌锂膨胀（石墨~10%/LFP~6.5%） 与 不可逆的产气膨胀。前者是正常"呼吸"，后者是故障信号。二者的区别不在体积数字，而在可逆性、应力分布和时间尺度。17…

2026/10/17 2:34:37 阅读更多 →
科捷智能职位分析：数据架构师

科捷智能职位分析：数据架构师

本文严格依据科捷智能官方工作职责、任职资格，结合智能制造、装备制造、项目制交付企业业务特性，对标DAMA、华为数据之道两大权威体系，系统性拆解数据架构师岗位定位、必备专业知识、核心软硬技能、岗位职责、简历优化策略、高频面试真题及标…

2026/10/17 2:34:37 阅读更多 →
PDMS-AVEVA-E3D二次开发教程（18）：批量化作业与无人值守——任务清单、幂等、日志与失败隔离

PDMS-AVEVA-E3D二次开发教程（18）：批量化作业与无人值守——任务清单、幂等、日志与失败隔离

版本声明 本篇基线为 AVEVA E3D Design 3.1，涉及前代 AVEVA PDMS 处显式标注。PML Add-in 机制的小节标题（Defining a PML Add-in、PML Application Control Object、Create a PLOBJ Control File、Create a UIC File、How to Add a PML Add-in to the P…

2026/10/17 2:33:37 阅读更多 →

日新闻

DeepSeek选型与部署：V3/R1、Ollama、API全攻略

DeepSeek选型与部署：V3/R1、Ollama、API全攻略

简介：《DeepSeek使用方法.pdf》是一份面向DeepSeek入门及进阶用户的完整使用指南，重点围绕V3与R1两款模型的能力差异与适用场景展开，帮助读者根据任务类型与成本选择合适的模型。资源共1个PDF文件，压缩包大小约311KB，篇…

2026/10/17 0:00:25 阅读更多 →
200+Deepseek润色指令拆解：从底层原理到场景落地的完整指南

200+Deepseek润色指令拆解：从底层原理到场景落地的完整指南

简介：这是一份聚焦DeepSeek提示词优化的《200Deepseek润色指令》PDF文档，共收录两百余条可直接套用的润色指令，涵盖语法修正、风格统一、逻辑梳理、表达精炼等维度，并针对商务写作、学术论文、广告文案等场景给出差异化建议。文档…

2026/10/17 0:00:25 阅读更多 →
OpenCV轮廓法物体计数系统：轻量、可控、可落地的工业级实现

OpenCV轮廓法物体计数系统：轻量、可控、可落地的工业级实现

简介：本资源是一份基于OpenCV的本科课程设计完整报告，面向计算机视觉初学者、图像处理学习者及高校通信/信息类专业学生，解决物体智能计数与检测结果结构化记录的实际问题。项目覆盖图像预处理、轮廓检测、边界框绘制、轨迹栏交互式参数调节、…

2026/10/17 0:00:25 阅读更多 →

周新闻

流感时间序列预测实战：ARIMA/LSTM全流程拆解与避坑指南

流感时间序列预测实战：ARIMA/LSTM全流程拆解与避坑指南

简介：基于 ARIMA、LSTM、Transformer 等模型的流感时间序列预测 Python 源码，面向计算机相关专业课程设计与期末大作业学生，以及项目实战学习者。内容覆盖预处理、平稳性检验、定阶、残差分析、多模型对比预测的完整时序建模流程，…

2026/10/16 21:35:51 阅读更多 →
影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别

影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别

影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别 做影刀RPA自动化，十个新手有八个栽在"往输入框里填东西"这件事上：要么填不进去，要么填了一半，要么直接把原来内容追加在后面。这背后的根因&…

2026/10/17 1:44:59 阅读更多 →
影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容

影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容

影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容 1. 认识影刀：什么场景该用RPA采小说数据 起点中文网的页面结构相对稳定——分类榜单、书籍详情、章节内容三块独立页面，跳转链路清晰。这种场景非常适合影刀自动化&#x…

2026/10/16 15:04:24 阅读更多 →

月新闻

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

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

2026/10/16 21:54:38 阅读更多 →
Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

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

2026/10/16 3:49:43 阅读更多 →
黑夜航拍船只数据集训练YOLOV5模型全流程解析

黑夜航拍船只数据集训练YOLOV5模型全流程解析

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

2026/10/16 14:23:36 阅读更多 →