《C++进阶之STL》【二叉搜索树】

【二叉搜索树】目录

• 前言：
• ------------概念介绍------------
  • 1. 什么是二叉搜索树?
  • 2. 二叉搜索树的性能怎么样？
• ------------基本操作------------
  • 一、查找操作
    • 思想
    • 步骤
    • 简述
  • 二、插入操作
    • 目标
    • 步骤
    • 简述
  • 三、删除操作
    • 目标
    • 步骤
    • 简述
• ------------代码实现------------
• 一、key形式的二叉搜索树
  • 头文件：BinarySearchTree.h
  • 测试文件：Test.cpp
  • 运行结果：
• 二、key_value形式的二叉搜索树
  • 头文件：BinarySearchTree.h
  • 测试文件：Test.cpp
  • 运行结果：

往期《C++初阶》回顾：

《C++初阶》目录导航

往期《C++进阶》回顾：
/------------ 继承多态 ------------/
【普通类/模板类的继承 + 父类&子类的转换 + 继承的作用域 + 子类的默认成员函数】
【final + 继承与友元 + 继承与静态成员 + 继承模型 + 继承和组合】
【多态：概念 + 实现 + 拓展 + 原理】

前言：

hi ~，小伙伴们大家好啊！( • ̀ω•́ )✧，等等先让我掏出手机看看今天是什么日子，哈哈今天啥也不是啊，嗯 ~ o(￣▽￣)o不过硬要说的话，其实今天是：中国医师节 + 世界人道主义日 + 世界摄影日 + 阿富汗独立日 （U•ェ•*U）

好啦，回归正题，今天我们要学习的是 【二叉搜索树】。这部分内容主要是为后面学习 AVL 树和红黑树打基础的，毕竟 “基础不牢，地动山摇”，这节课的内容和后面 4 - 5 章节的内容关联性很强，所以大家一定要好好学呀！✧(≖ ◡ ≖✿)
可能有更细心的小伙伴注意到了，这篇内容隶属于 《C++ 进阶之 STL》 系列，会感到困惑：这明明更像数据结构的内容，怎么放在 STL 里啦？(⊙ˍ⊙)？
哈哈，确实，这节内容不是直接介绍 STL，但它会直接影响我们对 STL 中 set 和 map 容器的学习，是进阶 STL 的基础中的基础，非常重要，所以就放在这里啦～(≧∇≦)ﾉ

------------概念介绍------------

1. 什么是二叉搜索树?

二叉搜索树（Binary Search Tree，BST）：也称为二叉排序树或二叉查找树，是一种特殊的二叉树。二叉搜索树是一种高效的 动态数据结构，用于存储有序数据，支持快速查找、插入和删除操作二叉搜索树的核心特性是：通过二叉树结构维护元素的排序关系

二叉搜索树具有以下特点和性质：

1. 节点值特性：对于二叉搜索树中的任意一个节点，设该节点的值为 key那么它的左子树中所有节点的值都小于 key根节点值为 5其左子树节点 3、2、4 的值都小于5其右子树节点 7、6、8 的值都大于5

2. 中序遍历特性：对二叉搜索树进行中序遍历（先左子树，再根节点，最后右子树），得到的节点序列是一个递增的有序序列比如：对上述二叉搜索树进行中序遍历，得到的序列为 2, 3, 4, 5, 6, 7, 8

它的右子树中所有节点的值都大于 key

//例如：下面这棵树就是一棵“二叉搜索树”5/ \ 37/ \ / \ 2468

2. 二叉搜索树的性能怎么样？

二叉搜索树的效率和形态强相关：最优情况：当二叉搜索树是 完全二叉树（或接近完全二叉树） 时，树的高度为 l o g 2 N log_2 N log2​N（ N N N 为节点总数 ）此时增、删、改、查操作的时间复杂度可达到 O ( log ⁡ 2 N ) O(\log_2 N) O(log2​N) ，效率接近二分查找。最差情况：若二叉搜索树退化为 单支树（或类似链表的形态 ） ，树的高度会退化为 N N N（节点总数 ）此时增、删、改、查操作的时间复杂度会劣化到 O ( N ) O(N) O(N) ，效率甚至不如普通遍历。

显然，单支树形态的效率无法满足实际需求， 因此后续会延伸讲解二叉搜索树的变形结构（平衡二叉搜索树 ）比如：AVL 树 和 红黑树 —— 这类结构通过自平衡机制，能稳定维持树的高度在 l o g 2 N log_2 N log2​N 级别，更适合内存中数据的存储与搜索场景。

对比二分查找的缺陷：

虽然二分查找也能实现 O ( log ⁡ 2 N ) O(\log_2 N) O(log2​N) 级别的查找效率，但它存在两大核心缺陷：存储结构限制：二分查找依赖支持下标随机访问的线性结构（如：数组 ），且要求数据有序插入删除低效：在支持下标随机访问的结构中（如：数组 ），插入/删除 操作需要挪动大量数据（为保持有序性 ），时间复杂度会劣化到 O ( N ) O(N) O(N) ，无法应对高频更新场景

相比之下，平衡二叉搜索树 既保留了二叉搜索树的有序性，又通过自平衡机制规避了单支树的低效问题，同时支持高效的插入、删除与查询，这正是其在工程实践中的核心价值。

所以：在学习的平衡二叉搜索树之前，让我们先来学习一下——二叉搜索树吧！

------------基本操作------------

一、查找操作

思想

查找操作的思想是：

查找操作利用二叉搜索树的特性：左子树的所有节点键值小于根节点，右子树的所有节点键值大于根节点，来进行不断地缩小搜索范围。正是这种 “分治” 思想使得二叉搜索树的查找操作无需遍历全树，大幅提高效率

步骤

查找操作的步骤：创建一个指向根节点的指针使用while循环进行查找键为key的节点情况1：当前遍历到的节点的键 < 目标键 —> “往右子树继续找”情况2：当前遍历到的节点的键 > 目标键 —> “往左子树继续找”情况3：当前遍历到的节点的键 = 目标键 —> ”找到了要查找的节点“情况4：遍历到空节点仍未找到键为key的节点 —> ”目标键值不存在“

简述

查找操作的简述：

从根节点开始寻找指定key的节点：若目标值小于当前节点值，则在左子树中继续搜索若目标值大于当前节点值，则在右子树中继续搜索若相等，则找到了目标节点

平均时间复杂度为 O ( l o g n ) O(log n) O(logn)，其中 n n n 是树中节点的数量

但在最坏情况下（如：树退化为链表 ），最坏时间复杂度会变为 O ( n ) O(n) O(n)

二、插入操作

目标

插入操作的核心目标是：

向已有二叉搜索树中添加新节点的同时，且要维持其 “左子树节点值 < 根节点值 < 右子树节点值”的特性。

步骤

插入操作的步骤：

1. 创建遍历的指针：创建一个进行遍历树的当前节点的指针创建指向当前遍历节点的父节点的指针

2. 寻找插入的位置：情况1：当前遍历到的节点的键 < 要插入的键 —> “往右子树继续找”情况2：当前遍历到的节点的键 > 要插入的键 —> “往左子树继续找”情况3：当前遍历到的节点的键 = 要插入的键 —> ”未找到要插入的位置“情况4：当遍历到空节点仍未找到键为key的节点 —> “找到了要插入的位置”

注意：这里的寻找过程和之前的查找操作的寻找不同：对于查找操作当出现=的情况说明查找成功了，而对于插入操作则是插入失败了。

3. 插入生成的节点：生成要插入的节点将新节点连接到二叉搜索树中 —> 注意并不能简单的进行插入要先判断：“新节点和父节点的键之间的大小关系，从而判断出新节点是应该插入到根节点的左子节点还是右子节点”情况1：新节点的键 < 父节点的键情况2：新节点的键 > 父节点的键

简述

插入操作的简述：

先从根节点开始搜索插入位置：若目标值小于当前节点值，则向当前节点的左子树移动若目标值大于当前节点值，则向当前节点的右子树移动当到达叶子节点时，根据目标值与叶子节点值的大小关系，将新节点作为叶子节点的左子节点或右子节点插入

平均时间复杂度为 O ( l o g n ) O(log n) O(logn)，最坏时间复杂度为 O ( n ) O(n) O(n)

三、删除操作

目标

删除节点时需处理三种情况：删除叶子节点（无左右子树）：直接删除删除单分支节点（只有左子树或右子树）：用子树替换该节点删除双分支节点（同时有左右子树）：无法直接删除该节点，需要找到替代节点

删除操作的核心目标是：

删除节点后需要确保剩余节点仍满足二叉搜索树的性质：

左子树所有节点键值 < 根节点 < 右子树所有节点键值

步骤

删除操作的步骤：

1. 创建遍历的指针：创建一个进行遍历树的当前节点的指针创建指向当前遍历节点的父节点的指针

2. 寻找要删的节点：

注意：和 插入操作一样，插入/删除 一个节点，并不是直接就可以进行 插入/删除 的，要先寻找 插入/删除 的 位置/节点，同样是寻找，但是这两操作的寻找还是有不同之处的：

对于插入操作当出现=的情况是“未找到插入位置”，而对于删除操作是“找到了要删除的节点“情况1：遍历到的节点的键 < 要删除的键 —> “往右子树继续找”情况2：当前遍历到的节点的键 > 要删除的键 —> “往左子树继续找”情况3：当前遍历到的节点的键 = 要插入的键 —> “找到了要删除的节点”

3. 删除要删的节点：

注意：在二叉搜索树中，找到要删除的节点后，除叶子节点外，其他节点不能直接删除。

原因：叶子节点没有左右子树，可直接删除；而其他节点至少有一个左子树或右子树，若直接删除会破坏树的结构（子树将失去连接）。

因此，需根据节点类型采用不同的删除策略：单分支节点（仅有左子树或右子树）：需用子树替代被删除节点，保持树的连通性。情况一：要删除节点的左子树为空 —> “将要删除节点的右子树托付给父节点”情况二：要删除节点的右子树为空 —> “将要删除节点的左子树托付给父节点”双分支节点（同时有左右子树）：需找到替代节点（如：后继节点），用其值替换被删除节点的值，再删除替代节点，确保树的有序性不被破坏。情况三：要删除节点的左右子树都不为空

情况一：要删除节点的左子树为空 —> “将要删除节点的右子树托付给父节点”

1.1：特殊情况：要删除的节点是根节点，无法进行托付如果要删除的节点是根节点 —> 直接“将要删除节点的右孩子设置为根节点”

1.1：正常情况：要删除的节点不是根节点，可以进行托付如果要删除的节点不是根节点 —> 进一步判断：“要删除的节点是父节点的左子节点还是右子节点”要删除的节点是父节点的“左子节点” —> “将要删除节点的右子树托付给父节点”的左子节点要删除的节点是父节点的“右子节点” —> “将要删除节点的右子树托付给父节点”的右子节点删除当前要删除的节点

情况二：要删除节点的右子树为空 —> “将要删除节点的左子树托付给父节点”

2.1：特殊情况：要删除的节点是根节点，无法进行托付如果要删除的节点的根节点 —> 直接“将要删除节点的左孩子设置为根节点”

2.2：正常情况：要删除的节点不是根节点，可以进行托付`如果要删除的节点不是根节点 —> 进一步判断：“要删除的节点是父节点的左子节点还是右子节点”要删除的节点是父节点的“左子节点” —> “将要删除节点的左子树托付给父节点”的左子节点要删除的节点是父节点的“右子节点” —> “将要删除节点的左子树托付给父节点”的右子节点删除当前要删除的节点

情况三：要删除节点的左右子树都不为空 —> “将要删除的后继节点的右子树托付给后继节点的父节点”第一步：找到用于替换要删除的节点的后继节点第二步：使用后继节点的值替换要删除节点的值第三步：删除后继节点之前要进一步判断：“后继节点是其父节点的左子节点还是右子节点”后继节点是其父节点的左孩子节点 —> 将后继节点的右子树托付给其父节点的左子节点后继节点是其父节点的右孩子节点 —> 将后继节点的右子树托付给其父节点的右子节点第四步：删除掉后继节点

简述

删除操作的简述：若要删除的节点是叶子节点，直接删除即可若节点只有一个子节点，将该节点的父节点与子节点直接连接，然后删除该节点若节点有两个子节点：通常的做法是找到该节点右子树中的最小节点（即：中序遍历下的后继节点）将其值赋给要删除的节点然后删除该后继节点（因为后继节点没有左子树，删除它可以简化操作 ）

平均时间复杂度为 O ( l o g n ) O(log n) O(logn)，最坏情况为 O ( n ) O(n) O(n)

------------代码实现------------

在二叉搜索树的应用场景中，根据数据存储与使用需求不同，存在两种常见的形式：

一、key 形式的二叉搜索树

这种形式的二叉搜索树，每个节点仅存储一个关键值（key）。它主要用于对单一关键值的元素进行组织、查找等操作。例如，当我们只需要对一系列整数进行排序和快速查找，而不需要关联其他额外信息时，就可以使用这种仅包含 key 的二叉搜索树。

二、key_value 形式的二叉搜索树

在很多实际场景中，我们不仅需要关键值（key），还需要将关键值与相应的数值（value）关联起来，这时候就会用到 key_value 形式的二叉搜索树。比如，要存储学生的学号（key）和对应的成绩（value），通过学号快速查找成绩，这种形式就能很好地满足需求。

一、key形式的二叉搜索树

头文件：BinarySearchTree.h

#pragmaonce//任务1：包含需要使用的头文件#include<iostream>usingnamespace std;//任务2：定义自定命名空间key//任务3：定义自定义命名空间key/value/*--------------------------------------------完成：“任务2”--------------------------------------------*//* 1.定义自定义命名空间key * 1.1：定义“二叉搜索树的节点”结构模板 * 1.2：定义“二叉搜索树”类模板 * 1.2.1：实现：“查找的操作” * 1.2.2：实现：“插入的操作” * 1.2.3：实现：“删除的操作” * 1.2.4：实现：“中序遍历的操作” */namespace key {/*---------------------定义“二叉搜索树的节点”结构模板---------------------*/template<classK>//注意：仅包含键：KstructBSTNode{/*----------节点的成员----------*///1.节点的键//2.指向左子节点的指针//3.指向右子节点的指针 K _key; BSTNode<K>* _left; BSTNode<K>* _right;/*----------节点的构造函数----------*/BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};/*---------------------定义“二叉搜索树”类模板---------------------*/template<classK>//注意：仅包含键：KclassBST{public:/*----------为类型起别名----------*///1.将二叉搜索树节点的类型“BSTNode<K>”---> 重命名为：“Node”using Node = BSTNode<K>;/*----------二叉搜索树的成员函数----------*///1.实现：“中序遍历操作”voidInOrder(){_InOrder(_root);//调用私有访问权限的下中序函数，完成遍历操作 cout << endl;}//2.实现：“查找操作” boolFind(const K& key){//1.创建一个指向根节点的指针 Node* curr = _root;//2.使用while循环进行查找键为key的节点while(curr){//情况1：当前遍历到的节点的键 < 目标键 ---> “继续寻找”if(curr->_key < key){ curr = curr->_right;//继续去右子树中寻找}//情况2：当前遍历到的节点的键 > 目标键 ---> “继续寻找”elseif(curr->_key > key){ curr = curr->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 目标键 ---> “找到了要查找的节点”else{returntrue;}}//情况4： ---> “整棵树中没有键为key的节点”returnfalse;}//3.实现：“插入操作”boolInsert(const K& key){//特殊情况：要插入的节点的树是“空树”if(_root ==nullptr){//1.直接创建一个节点为跟节点 _root =newNode(key);//2.返回true即可returntrue;}//正常情况：要插入的节点的树是“非空树”/*----------------第一阶段：准备阶段----------------*///1.创建一个遍历树的当前节点指针 Node* current = _root;//2.创建当前遍历节点的父节点的指针 Node* parent =nullptr;/*----------------第二阶段：查找阶段----------------*/while(current)//循环查找插入位置{//情况1：当前遍历到的节点的键 < 要插入的键 ---> “继续寻找”if(current->_key < key){//1.更新当前遍历节点的父节点  parent = current;//不同之处1：这里的需要更新parent指针的位置 //原因：下面我们要在curr指针指向的位置进行插入操作，所以我们需要记录当前遍历到节点的父节点//2.继续去右子树中寻找 current = current->_right;}//情况2：当前遍历到的节点的键 > 要插入的键 ---> “继续寻找”elseif(current->_key > key){ parent = current; current = current->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 要插入的键 ---> “键已存在”---> 能跳出while循环情况才是：“找到了要插入的位置”else{returnfalse;//不同之处2：这里放回的是false//原因：我们实现的二叉搜索树不支持存储“键相等的节点”}}/*----------------第三阶段：插入阶段----------------*///1.创建要插入的节点 current =newNode(key);//2.将新节点连接到二叉搜索树中 ---> 本质上就是：判断“新节点是父节点的左子节点还是右子节点”//情况1：新节点的键 < 父节点的键if(key < parent->_key){ parent->_left = current;}//情况2：新节点的键 > 父节点的键else//注意：这里使用else表面上看是：满足key >= parent->_key条件的情况都可以执行下面的代码{//但其实key = parent->_key这种情况在上面的第二阶段中已经被的return false排除掉了 parent->_right = current;}//3.程序执行到这里说明插入成功returntrue;}//4.实现：“删除操作”boolErase(const K& key){//特殊情况：二叉搜索树是“空树”if(_root ==nullptr){returnfalse;}//正常情况：二叉搜索树是“非空树”/*----------------第一阶段：准备阶段----------------*///1.创建用于遍历树的当前节点指针 Node* current = _root;//2.创建记录当前遍历节点的父节点的指针 Node* parent =nullptr;/*----------------第二阶段：删除阶段----------------*/while(current){//情况1：当前遍历到的节点的键 < 要删除的键 ---> “继续寻找”if(current->_key < key){//1.更新当前遍历节点的父节点  parent = current;//不同之处1：这里的需要更新parent指针的位置 //原因：下面我们要在current指针指向的位置进行插入操作，所以我们需要记录当前遍历到节点的父节点//2.继续去右子树中寻找 current = current->_right;}//情况2：当前遍历到的节点的键 > 要删除的键 ---> “继续寻找”elseif(current->_key > key){ parent = current; current = current->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 要插入的键 ---> “找到了删除的节点”else{//将当前节点从二叉搜索树中删除掉 ---> 本质上就是：判断“要删除节点的左子树还是右子树要托付给的父节点的左子树还是右子树”//情况一：要删除节点的左子树为空 ---> “将要删除节点的右子树托付给父节点”if(current->_left ==nullptr){//1.如果要删除的节点是根节点 ---> 直接“将要删除节点的右孩子设置为根节点”if(current == _root){ _root = current->_right;}//2.如果要删除的节点不是根节点 ---> 进一步判断：“要删除的节点是父节点的左子节点还是右子节点”else{//2.1：要删除的节点是父节点的“左子节点”---> “将要删除节点的右子树托付给父节点”的左子节点if(parent->_left == current){ parent->_left = current->_right;}//2.2：要删除的节点是父节点的“右子节点”---> “将要删除节点的右子树托付给父节点”的右子节点else{ parent->_right = current->_right;}}//3.删除掉当前节点delete current;}//情况二：要删除节点的右子树为空 ---> “将要删除节点的左子树托付给父节点”elseif(current->_right ==nullptr){//1.如果要删除的节点的根节点 ---> 直接“将要删除节点的左孩子设置为根节点”if(current == _root){ _root = current->_left;}//2.如果要删除的节点不是根节点 ---> 进一步判断：“要删除的节点是父节点的左子节点还是右子节点”else{//2.1：要删除的节点是父节点的“左子节点”---> “将要删除节点的左子树托付给父节点”的左子节点if(parent->_left == current){ parent->_left = current->_left;}//2.2：要删除的节点是父节点的“右子节点”---> “将要删除节点的左子树托付给父节点”的右子节点else{ parent->_right = current->_left;}}//3.删除当前要删除的节点delete current;}//情况三：要删除节点的左右子树都不为空else{/*-----------第一步：找到用于替换要删除的节点的后继节点-----------*///寻找右子树中最左的节点：即后继节点， (当然也可查找左子树的最右的节点)//1.创建用于指向替换要删除的节点的指针 Node* replace = current->_right;//2.创建指向要删除节点父节点的指针 Node* replaceParent = current;//3.使用while循环查找这个节点while(replace->_left){//1.更新当前节点的父节点 replaceParent = replace;//2.不断的向左子树去寻找 replace = replace->_left;}/*-----------第二步：用后继节点的值替换要删除节点的值-----------*/ current->_key = replace->_key;/*-----------第三步：处理后继节点的“父节点”和“子节点”的关系-----------*///本质上是：确定后继节点是其父节点的左孩子还是右孩子节点//1.后继节点是其父节点的左孩子节点 ---> 将后继节点的右子树托付给其父节点的左子节点if(replace == replaceParent->_left){ replaceParent->_left = replace->_right;}//2.后继节点是其父节点的右孩子节点 ---> 将后继节点的右子树托付给其父节点的右子节点else{ replaceParent->_right = replace->_right;}/*-----------第四步：删除掉后继节点-----------*/delete replace;}/*----------------第三阶段：返回阶段----------------*///经过上面的“找到要删除的节点 + 三种不同的节点删除情况”，程序执行这里说明已经成功的完成了删除的任务returntrue;/* 上面的删除的三种情况分别是： * * 1.要删除节点的左子树为空 * 2.要删除节点的右子树为空 * 3.要删除节点的左右子树都不为空 * * 大家可能已经发现了一件事情就是：上面的这三种情况并不全面，还缺少一种情况 * 4.要删除节点的左右子树都为空 * …… */}}//跳出了while训话并未在二叉树中找到要键为key的节点returnfalse;}private:/*----------二叉搜索树的成员变量----------*/ Node* _root =nullptr;//根节点的指针（并给上默认值为nullptr）/*----------二叉搜索树的成员函数----------*///1.实现：“中序遍历操作”void_InOrder(Node* root){//1.递归终止条件：当遍历的节点的为空节点的时候，停止递归if(root ==nullptr){return;}//1.首先遍历左子树_InOrder(root->_left);//2.然后输出当前节点的键信息 cout << root->_key <<" ";//3.最后遍历右子树_InOrder(root->_right);}};}

测试文件：Test.cpp

#define_CRT_SECURE_NO_WARNINGS1#include"BinarySearchTree.h"#include<iostream>usingnamespace std;voidTest01(){ cout <<"===== 测试基本功能 ====="<< endl;//1.创建一个二叉搜搜树 key::BST<int> bst;//2.测试插入功能int arr[]={50,30,70,20,40,60,80}; cout <<"插入数据: ";for(int i =0; i <sizeof(arr)/sizeof(arr[0]); i++){ cout << arr[i]<<" "; bst.Insert(arr[i]);} cout << endl;//3.测试中序遍历功能 cout <<"中序遍历结果(应有序): "; bst.InOrder();//4.测试查找功能 cout <<"查找存在的元素50: "<<(bst.Find(50)?"存在":"不存在")<< endl; cout <<"查找不存在的元素90: "<<(bst.Find(90)?"存在":"不存在")<< endl;}voidTest02(){ cout <<"\n===== 测试删除操作 ====="<< endl;/*---------------创建一个二叉搜索树---------------*/ key::BST<int> bst;int arr[]={50,30,70,20,40,60,80};for(int val : arr){ bst.Insert(val);} cout <<"原始树中序遍历: "; bst.InOrder();/*---------------测试删除功能---------------*/// 情况1: 删除叶子节点(20) cout <<"删除叶子节点20后: "; bst.Erase(20); bst.InOrder();// 情况2: 删除只有右子树的节点(30) cout <<"删除只有右子树的节点30后: "; bst.Erase(30); bst.InOrder();// 情况3: 删除只有左子树的节点(70) bst.Insert(70);// 重新插入70 cout <<"删除只有左子树的节点70后: "; bst.Erase(70); bst.InOrder();// 情况4: 删除有左右子树的节点(50) cout <<"删除有左右子树的节点50后: "; bst.Erase(50); bst.InOrder();// 情况5: 删除根节点(40) cout <<"删除根节点40后: "; bst.Erase(40); bst.InOrder();}voidTest03(){ cout <<"\n===== 测试特殊情况 ====="<< endl;//1.重复插入测试 cout <<"---重复插入测试---"<< endl; key::BST<int> bst1; bst1.Insert(10); cout <<"插入10: "<<(bst1.Find(10)?"成功":"失败")<< endl;bool result = bst1.Insert(10); cout <<"再次插入10: "<<(result ?"成功":"失败")<< endl;// 应失败//2.单节点树测试 cout <<"---单节点树测试---"<< endl; key::BST<char> bst2; bst2.Insert('A'); cout <<"单节点树中序遍历: "; bst2.InOrder(); bst2.Erase('A'); cout <<"删除单节点后查找: "<<(bst2.Find('A')?"存在":"不存在")<< endl;}voidTest04(){ cout <<"\n===== 测试连续删除 ====="<< endl;//1.创建一棵二叉搜索树 key::BST<int> t;int a[]={8,3,1,10,1,6,4,7,14,13};for(auto e : a){ t.Insert(e);}//2.逐个删除所有节点，验证删除逻辑和内存释放 cout <<"逐个删除节点的中序遍历过程："<< endl;for(auto e : a){ t.Erase(e); t.InOrder();}}intmain(){Test01();Test02();Test03();Test04();return0;}

运行结果：

二、key_value形式的二叉搜索树

头文件：BinarySearchTree.h

#pragmaonce//任务1：包含需要使用头文件#include<iostream>usingnamespace std;//任务2：定义自定命名空间key/value/*--------------------------------------------完成：“任务2”--------------------------------------------*//* 1.定义自定义命名空间key_value * 1.1：定义“二叉搜索树的节点”结构模板（双模板参数） * 1.2：定义“二叉搜索树”类模板（双模板参数） * 1.2.1：实现：“强制默认构造函数” * 1.2.2：实现：“拷贝构造函数” * 1.2.3：实现：“赋值运算符重载函数” * 1.2.4：实现：“析构函数” * * 1.2.5：实现：“查找的操作” * 1.2.6：实现：“插入的操作” * 1.2.7：实现：“删除的操作” * 1.2.8：实现：“中序遍历的操作” */namespace key_value {/*---------------------定义“二叉搜索树的节点”结构模板---------------------*/template<classK,classV>//注意：既包含键key，也包含值valuestructBSTNode{/*----------节点的成员----------*///1.节点的键//2.节点的值//3.指向左子节点的指针//4.指向右子节点的指针 K _key; V _value; BSTNode<K, V>* _left; BSTNode<K, V>* _right;/*----------节点的构造函数----------*/BSTNode(const K& key,const V& value):_key(key),_value(value),_left(nullptr),_right(nullptr){}};/*---------------------定义“二叉搜索树”类模板---------------------*/template<classK,classV>classBST{public:/*----------为类型起别名----------*///1.将二叉搜索树节点的类型“BSTNode<K, V>”---> 重命名为：“Node”using Node = BSTNode<K, V>;/*----------二叉搜索树的成员函数----------*///1.实现：“强制默认构造函数”BST()=default;//下面将会实现拷贝构造函数，所以我们需要强制编译器生成默认构造函数//2.实现：“拷贝构造函数”BST(const BST& t){ _root =Copy(t._root);//注意：调用 Copy 函数递归拷贝节点，构建新的树}//3.实现：“赋值运算符重载函数” BST&operator=(BST tmp)//注意：形参列表的中内容不能写成：const BST& tmp{//注意：不能加上const，因为这会导致无法调用拷贝构造函数（因为tmp是常量）swap(_root, tmp._root);return*this;}//4.实现：“析构函数”~BST(){Destroy(_root);//注意：调用 Destroy 函数递归销毁所有节点 _root =nullptr;}//5.实现：“查找操作”  Node*Find(const K& key)/*不同点1：bool Find(const K& key) ---> Node * Find(const K & key)*/{//注意：根据键 key 查找对应的节点，返回节点指针//1.创建一个指向根节点的指针 Node* curr = _root;//2.使用while循环进行查找键为key的节点while(curr){//情况1：当前遍历到的节点的键 < 目标键 ---> “继续寻找”if(curr->_key < key){ curr = curr->_right;//继续去右子树中寻找}//情况2：当前遍历到的节点的键 > 目标键 ---> “继续寻找”elseif(curr->_key > key){ curr = curr->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 目标键 ---> “找到了要查找的节点”else{return curr;/*不同点2：return true; ---> returncurr curr;*/}//注意：这里不再返回bool类型的变量了，而是返回当前遍历到节点的指针}//情况4： ---> “整棵树中没有键为key的节点”returnnullptr;/*不同点3：return false; ---> return nullptr;*///注意：这里返回的也是指针}//6.实现：“插入操作”boolInsert(const K& key,const V& value)/*不同点1：bool Insert(const K& key) ---> bool Insert(const K& key, const V& value)*/{//特殊情况：要插入的节点的树是“空树”if(_root ==nullptr){//1.直接创建一个节点为跟节点 _root =newNode(key, value);/*不同点2：_root = new Node(key); ---> _root = new Node(key, value);*///2.返回true即可returntrue;}//正常情况：要插入的节点的树是“非空树”/*----------------第一阶段：准备阶段----------------*///1.创建一个遍历树的当前节点指针 Node* current = _root;//2.创建当前遍历节点的父节点的指针 Node* parent =nullptr;/*----------------第二阶段：查找阶段----------------*/while(current)//循环查找插入位置{//情况1：当前遍历到的节点的键 < 要插入的键 ---> “继续寻找”if(current->_key < key){//1.更新当前遍历节点的父节点  parent = current;//不同之处1：这里的需要更新parent指针的位置 //原因：下面我们要在curr指针指向的位置进行插入操作，所以我们需要记录当前遍历到节点的父节点//2.继续去右子树中寻找 current = current->_right;}//情况2：当前遍历到的节点的键 > 要插入的键 ---> “继续寻找”elseif(current->_key > key){ parent = current; current = current->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 要插入的键 ---> “键已存在”---> 能跳出while循环情况才是：“找到了要插入的位置”else{returnfalse;//不同之处2：这里放回的是false//原因：我们实现的二叉搜索树不支持存储“键相等的节点”}}/*----------------第三阶段：插入阶段----------------*///1.创建要插入的节点 current =newNode(key, value);/*不同点3：current = new Node(key); ---> current = new Node(key, value);*///2.将新节点连接到二叉搜索树中 ---> 注意并不能简单的进行插入操作要先判断：// “新节点和父节点的键之间的大小关系，从而判断出新节点是应该插入到根节点的左子节点还是右子节点”//情况1：新节点的键 < 父节点的键if(key < parent->_key){ parent->_left = current;}//情况2：新节点的键 > 父节点的键else//注意：这里使用else表面上看是：满足key >= parent->_key条件的情况都可以执行下面的代码{//但其实key = parent->_key这种情况在上面的第二阶段中已经被的return false排除掉了 parent->_right = current;}//3.程序执行到这里说明插入成功returntrue;}//7.实现：“删除操作”boolErase(const K& key){//特殊情况：二叉搜索树是“空树”if(_root ==nullptr){returnfalse;}//正常情况：二叉搜索树是“非空树”/*----------------第一阶段：准备阶段----------------*///1.创建用于遍历树的当前节点指针 Node* current = _root;//2.创建记录当前遍历节点的父节点的指针 Node* parent =nullptr;/*----------------第二阶段：删除阶段----------------*/while(current){//情况1：当前遍历到的节点的键 < 要删除的键 ---> “继续寻找”if(current->_key < key){//1.更新当前遍历节点的父节点  parent = current;//不同之处1：这里的需要更新parent指针的位置 //原因：下面我们要在current指针指向的位置进行插入操作，所以我们需要记录当前遍历到节点的父节点//2.继续去右子树中寻找 current = current->_right;}//情况2：当前遍历到的节点的键 > 要删除的键 ---> “继续寻找”elseif(current->_key > key){ parent = current; current = current->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 要插入的键 ---> “找到了删除的节点”else{//将当前节点从二叉搜索树中删除掉 ---> 本质上就是：判断“要删除节点的左子树还是右子树要托付给的父节点的左子树还是右子树”//情况一：要删除节点的左子树为空 ---> “将要删除节点的右子树托付给父节点”if(current->_left ==nullptr){//1.如果要删除的节点是根节点 ---> 直接“将要删除节点的右孩子设置为根节点”if(current == _root){ _root = current->_right;}//2.如果要删除的节点不是根节点 ---> 进一步判断：“要删除的节点是父节点的左子节点还是右子节点”else{//2.1：要删除的节点是父节点的“左子节点”---> “将要删除节点的右子树托付给父节点”的左子节点if(parent->_left == current){ parent->_left = current->_right;}//2.2：要删除的节点是父节点的“右子节点”---> “将要删除节点的右子树托付给父节点”的右子节点else{ parent->_right = current->_right;}}//3.删除掉当前节点delete current;}//情况二：要删除节点的右子树为空 ---> “将要删除节点的左子树托付给父节点”elseif(current->_right ==nullptr){//1.如果要删除的节点的根节点 ---> 直接“将要删除节点的左孩子设置为根节点”if(current == _root){ _root = current->_left;}//2.如果要删除的节点不是根节点 ---> 进一步判断：“要删除的节点是父节点的左子节点还是右子节点”else{//2.1：要删除的节点是父节点的“左子节点”---> “将要删除节点的左子树托付给父节点”的左子节点if(parent->_left == current){ parent->_left = current->_left;}//2.2：要删除的节点是父节点的“右子节点”---> “将要删除节点的左子树托付给父节点”的右子节点else{ parent->_right = current->_left;}}//3.删除当前要删除的节点delete current;}//情况三：要删除节点的左右子树都不为空else{/*-----------第一步：找到用于替换要删除的节点的后继节点-----------*///寻找右子树中最左的节点：即后继节点， (当然也可查找左子树的最右的节点)//1.创建用于指向替换要删除的节点的指针 Node* replace = current->_right;//2.创建指向要删除节点父节点的指针 Node* replaceParent = current;//3.使用while循环查找这个节点while(replace->_left){//1.更新当前节点的父节点 replaceParent = replace;//2.不断的向左子树去寻找 replace = replace->_left;}/*-----------第二步：使用后继节点的值替换要删除节点的值-----------*/ current->_key = replace->_key;/*-----------第三步：处理后继节点的“父节点”和“子节点”的关系-----------*///本质上是：确定后继节点是其父节点的左孩子还是右孩子节点//1.后继节点是其父节点的左孩子节点 ---> 将后继节点的右子树托付给其父节点的左子节点if(replace == replaceParent->_left){ replaceParent->_left = replace->_right;}//2.后继节点是其父节点的右孩子节点 ---> 将后继节点的右子树托付给其父节点的右子节点else{ replaceParent->_right = replace->_right;}/*-----------第四步：删除掉后继节点-----------*/delete replace;}/*----------------第三阶段：返回阶段----------------*///经过上面的“找到要删除的节点 + 三种不同的节点删除情况”，程序执行这里说明已经成功的完成了删除的任务returntrue;/* 上面的删除的三种情况分别是： * * 1.要删除节点的左子树为空 * 2.要删除节点的右子树为空 * 3.要删除节点的左右子树都不为空 * * 大家可能已经发现了一件事情就是：上面的这三种情况并不全面，还缺少一种情况 * 4.要删除节点的左右子树都为空 * * 当左右子树均为空时（即：叶子节点），属于情况 1（左子树为空）或情况 2（右子树为空）的特例，可被这两种情况兼容处理 * 因此，无需单独列为第四种情况 */}}//跳出了while训话并未在二叉树中找到要键为key的节点returnfalse;}//8.实现：“中序遍历的操作”voidInOrder(){_InOrder(_root);//调用私有访问权限的下中序函数，完成遍历操作 cout << endl;}private:/*----------二叉搜索树的成员变量----------*/ Node* _root =nullptr;//根节点的指针（并给上默认值为nullptr）/*----------二叉搜索树的成员函数----------*///1.实现：“中序遍历操作”void_InOrder(Node* root){//1.递归终止条件：当遍历的节点的为空节点的时候，停止递归if(root ==nullptr){return;}//1.首先遍历左子树_InOrder(root->_left);//2.然后输出当前节点的键信息 cout << root->_key <<":"<< root->_value << endl;/*不同点1：cout << root->_key << " "; ---> cout << root->_key << ":" << root->_value << endl; *///3.最后遍历右子树_InOrder(root->_right);}//2.实现：“拷贝二叉搜索树节点”的操作 Node*Copy(const Node* root){//1.递归终止条件：当前节点为空if(root ==nullptr){returnnullptr;}//2.创建新节点，拷贝当前节点的键值 Node* newRoot =newNode(root->_key, root->_value);//3.递归拷贝左子树 newRoot->_left =Copy(root->_left);//注意：要将递归拷贝的结果赋值给新节点的左右子树指针，不然的话这会导致拷贝的树结构不正确//4.递归拷贝右子树 newRoot->_right =Copy(root->_right);//注意：如果未进行赋值，那么拷贝后的树只有根节点，左右子树均为 nullptr//5.返回根节点return newRoot;}//3.实现：“销毁二叉搜索树节点”的操作voidDestroy(Node* root){//1.递归终止条件：当前节点为空if(root ==nullptr){return;}//1.先销毁左子树Destroy(root->_left);//2.再销毁右子树Destroy(root->_right);//3.释放当前节点内存delete root;}};}

测试文件：Test.cpp

#define_CRT_SECURE_NO_WARNINGS1#include"BinarySearchTree.h"voidTest01(){ cout <<"========= 测试基本功能 ========="<< endl;//1.创建一个二叉搜索树 key_value::BST<string, string> dict;//2.测试插入功能 dict.Insert("apple","苹果"); dict.Insert("banana","香蕉"); dict.Insert("cherry","樱桃"); dict.Insert("date","枣"); cout <<"插入后的中序遍历（按键排序）："<< endl; dict.InOrder();// 应按字母顺序输出键值对//3.测试查找功能auto node = dict.Find("banana");if(node) cout <<"查找 'banana' 成功，值为："<< node->_value << endl;else cout <<"查找 'banana' 失败"<< endl; node = dict.Find("grape");if(node) cout <<"查找 'grape' 成功，值为："<< node->_value << endl;else cout <<"查找 'grape' 失败（预期结果）"<< endl;}voidTest02(){ cout <<"\n========= 测试删除操作 ========="<< endl;/*-----------------创建一个二叉搜索树-----------------*/ key_value::BST<int, string> bst; bst.Insert(50,"五十"); bst.Insert(30,"三十"); bst.Insert(70,"七十"); bst.Insert(20,"二十"); bst.Insert(40,"四十"); bst.Insert(60,"六十"); bst.Insert(80,"八十"); cout <<"原始树中序遍历："<< endl; bst.InOrder();/*-----------------测试删除节点的功能-----------------*/// 情况1：删除叶子节点(20) cout <<"删除叶子节点20后："<< endl; bst.Erase(20); bst.InOrder();// 情况2：删除只有右子树的节点(30) cout <<"删除只有右子树的节点30后："<< endl; bst.Erase(30); bst.InOrder();// 情况3：删除只有左子树的节点(70) bst.Insert(70,"七十");// 重新插入70 cout <<"删除只有左子树的节点70后："<< endl; bst.Erase(70); bst.InOrder();// 情况4：删除有左右子树的节点(50) cout <<"删除有左右子树的节点50后："<< endl; bst.Erase(50); bst.InOrder();// 情况5：删除根节点(40) cout <<"删除根节点40后："<< endl; bst.Erase(40); bst.InOrder();}voidTest03(){ cout <<"\n========= 测试拷贝构造和赋值运算符 ========="<< endl;/*-----------------创建一个二叉搜索树-----------------*/ key_value::BST<string,int> original; original.Insert("张三",18); original.Insert("李四",20); original.Insert("王五",22); original.Insert("赵六",24); cout <<"原始树中序遍历："<< endl; original.InOrder();/*-----------------测试拷贝构造和赋值运算符-----------------*///1.测试拷贝构造 cout <<"\n--------测试拷贝构造--------"<< endl; key_value::BST<string,int>copy1(original); cout <<"拷贝构造后的树中序遍历："<< endl; copy1.InOrder();//2.测试赋值运算符 cout <<"\n--------测试赋值运算符--------"<< endl; key_value::BST<string,int> copy2; copy2 = original; cout <<"赋值运算符后的树中序遍历："<< endl; copy2.InOrder();//3.修改原树，验证深拷贝 cout <<"\n--------修改原树，验证深拷贝--------"<< endl; original.Insert("钱七",26); cout <<"修改原树后，原树中序遍历："<< endl; original.InOrder(); cout <<"拷贝树中序遍历（应不受影响）："<< endl; copy1.InOrder();}voidTest04(){ cout <<"\n===== 测试应用场景：单词字典 ====="<< endl;//1.创建键为string（单词）、值为string（释义）的二叉搜索树 key_value::BST<string, string> dict; dict.Insert("left","左边"); dict.Insert("right","右边"); dict.Insert("insert","插入"); dict.Insert("string","字符串");//2.循环从键盘读取用户输入的单词，并在二叉搜索树中查找单词 string str; cout <<"请输入单词查询释义（输入任意非单词可退出）："<< endl;while(cin >> str){auto ret = dict.Find(str);if(ret) cout <<"->"<< ret->_value << endl;else cout <<"无此单词，请重新输入"<< endl;}}voidTest05(){ cout <<"\n===== 测试应用场景：统计水果出现次数 ====="<< endl;//1.定义水果数组，包含重复元素 string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"};//2.创建键为水果名称（string）、值为出现次数（int）的二叉搜索树 key_value::BST<string,int> countTree;//3.遍历水果数组，统计每种水果的出现次数for(constauto& str : arr){auto ret = countTree.Find(str);//1.当前水果不存在：插入新节点，次数初始化为1if(ret ==nullptr){ countTree.Insert(str,1);}//2.当前水果存在：对应次数加1else{ ret->_value++;}}//4.输出水果出现次数统计结果 cout <<"水果出现次数统计结果（中序遍历，按键升序排列）："<< endl; countTree.InOrder();//5.测试修改二叉搜索树的节点键值对的值auto node = countTree.Find("苹果");if(node){ node->_value =100;// 模拟修改次数 cout <<"修改'苹果'次数为100后："<< endl; countTree.InOrder();}}intmain(){Test01();Test02();Test03();Test04();Test05();return0;}

运行结果：