进阶数据结构： 二叉搜索树

article/2025/8/15 3:21:06

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记  闲言碎语小记坊 题山采玉 领略算法真谛

目录

二叉搜索树的特性：

搜索二叉树的实现

Insert

Find：

Erase

析构函数：

拷贝函数和赋值运算符重载

key_value

二叉搜索树的特性：

之前我们学习过了二叉树，但实现二叉树是没有意义的，我们针对二叉树进行一定的限制就出现了二叉搜索树：它的每个节点满足根节点上的左子树上的节点小于它的父节点，右子树上的节点大于根节点。

这就是一棵二叉搜索树：

二叉搜索树可以支持插入相等的值，也可以不支持插入相等的值，我们今天就实现不能插入相同的值吧！

那我们的二叉搜索树有什么特性呢？

我们对这一棵树进行中序遍历我们发现打印出来就成了升序。因为这种特性我们也叫二叉搜索树为二叉排序树，因为这种特性我们进行查找某一个元素也很高效。

我们要进行搜索操作时，我们需要的时间复杂度最差的情况是h，那⼆叉搜索树增删查改时间复杂度是什么呢？有人说是log N，这是理想的情况下，如果我们的树是这样的呢？

这样显然的时间复杂度为O(N)。

搜索二叉树的实现

我们得定义树节点，和二叉树两种结构：

#pragma once
template<class K>
struct BSTreeNode
{BSTreeNode<K>* _right;BSTreeNode<K>* _left;K _key;BSTreeNode(const K& key): _right(nullptr), _left(nullptr), _key(key){ }
};
template<class K>
class BSTree
{
public:typedef BSTreeNode<K> Node;
private:Node* _root = nullptr;
};

我们先来实现一下插入操作：

Insert

插入操作就很简单，如果插入的值小于该节点，就向它的左子树走，否则就向右子树走，如果要走的子树为空就插入在这个位置，我们实现的Insert返回类型应该是bool类型来判断是否插入成功，我们由于要找到上一个节点的位置才能插入，所以可以多定义一个指针。

//只能插入不同的Key节点
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else return false;}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

实现了插入，我们来实现一下中序遍历来打印一下吧：

//中序遍历
void _InOrder(Node* root)
{if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);
}

但如果我们在外部调用这个函数时我们访问不了私有变量_root，我们该怎么实现呢？函数体类实现返回_root函数，这样还是太麻烦了，不如这样实现：

	void InOrder(){_InOrder(_root);cout << endl;}
private://中序遍历void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

我们可以随便实现一下查找，思路是一样的

Find：

bool Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else return true;}return false;
}

接下来就来实现比较复制的删除操作了

如果我们删除1节点或者13节点就很简单，让他们的根节点指向空就可以了。

现在如果删除有一个节点的比如先删6，我们怎么处理呢？我们需要将6的父节点指向6的孩子节点，14节点也是一样的思路，但我们得知道它是父节点的左孩子还是右孩子，它唯一的孩子是左孩子还是右孩子，这就得分类讨论了，其实第一种情况可以合并在这一起。

这里还有一种特殊情况当我们要删除的节点只有一个孩子并且它是根节点

此时我们只需要将根节点变成唯一的孩子处。简单来实现一下：

	bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//删除操作//左孩子为空if (cur->_left == nullptr){if (cur == _root){_root = _root->_right;delete cur;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}delete cur;}}//右孩子为空else if (cur->_right == nullptr){if (cur == _root){_root = _root->_left;delete cur;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}delete cur;}}//有两个孩子else{//....}    return true;}}//找不到return false;}

到了最麻烦的情况了如果有两个孩子：

此时我们就不能直接删除那么简单了，我们需要将该节点替换之后再删，我们可以找右孩子中最小的替换，或者找左孩子中最大的替换后依然还是一棵平衡二叉树。

比如我们以删除3号节点为例找右孩子中最小的：

我们就可以来实现一下咯：

Erase

bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//删除操作//左孩子为空if (cur->_left == nullptr){if (cur == _root){_root = _root->_right;delete cur;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}delete cur;}}//右孩子为空else if (cur->_right == nullptr){if (cur == _root){_root = _root->_left;delete cur;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}delete cur;}}//有两个孩子else{Node* pMinRight = cur;Node* minRight = cur->_right;while (minRight->_left){pMinRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pMinRight->_left == minRight){pMinRight->_left = minRight->_right;}else{pMinRight->_right = minRight->_right;}delete minRight;}return true;}}//找不到return false;
}

 剩下的操作就是很简单的了。

析构函数：

我们先来实现一下Destory，因为析构函数不能调用参数，而我们析构要知道_root还是和之前的中序遍历一样的思路：

~BSTree()
{Destory(_root);_root = nullptr;
}
//销毁
void Destory(Node* root)
{if (root == nullptr) return;Destory(_root->_left);Destory(_root->_right);delete _root;
}

接着实现拷贝函数和赋值运算符重载

拷贝函数和赋值运算符重载

BSTree() = default;BSTree(const BSTree<K>& t)
{_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{swap(t._root, _root);return *this;
}
Node* Copy(Node* root)
{if (root == nullptr) return nullptr;Node* copy = new Node(root->_key);copy->_left = Copy(root->_left);copy->_right = Copy(root->_right);return copy;
}

注意我们实现了拷贝函数，就不会实现默认构造，所以我们得实现一下默认构造函数。

完整代码：


#pragma once
template<class K>
struct BSTreeNode
{BSTreeNode<K>* _right;BSTreeNode<K>* _left;K _key;BSTreeNode(const K& key): _right(nullptr), _left(nullptr), _key(key){ }
};
template<class K>
class BSTree
{
public:typedef BSTreeNode<K> Node;BSTree() = default;BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(t._root, _root);return *this;}~BSTree(){Destory(_root);_root = nullptr;}//只能插入不同的Key节点bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else return true;}return false;}bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else return false;}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//删除操作//左孩子为空if (cur->_left == nullptr){if (cur == _root){_root = _root->_right;delete cur;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}delete cur;}}//右孩子为空else if (cur->_right == nullptr){if (cur == _root){_root = _root->_left;delete cur;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}delete cur;}}//有两个孩子else{Node* pMinRight = cur;Node* minRight = cur->_right;while (minRight->_left){pMinRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pMinRight->_left == minRight){pMinRight->_left = minRight->_right;}else{pMinRight->_right = minRight->_right;}delete minRight;}return true;}}//找不到return false;}void InOrder(){_InOrder(_root);cout << endl;}
private://销毁void Destory(Node* root){if (root == nullptr) return;Destory(root->_left);Destory(root->_right);delete root;}//中序遍历void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* Copy(Node* root){if (root == nullptr) return nullptr;Node* copy = new Node(root->_key);copy->_left = Copy(root->_left);copy->_right = Copy(root->_right);return copy;}
private://缺省值初始化Node* _root = nullptr;
};

 我们也可以实现，key_value类型的搜索二叉树：

key_value

#pragma once
namespace key_value
{template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _right;BSTreeNode<K, V>* _left;K _key;V _value;BSTreeNode(const K& key, const V& value): _right(nullptr), _left(nullptr), _key(key), _value(value){}};template<class K, class V>class BSTree{public:typedef BSTreeNode<K, V> Node;BSTree() = default;BSTree(const BSTree<K, V>& t){_root = Copy(t._root);}BSTree<K, V>& operator=(BSTree<K, V> t){swap(t._root, _root);return *this;}~BSTree(){Destory(_root);_root = nullptr;}//只能插入不同的Key节点bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else return true;}return false;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else return false;}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//删除操作//左孩子为空if (cur->_left == nullptr){if (cur == _root){_root = _root->_right;delete cur;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}delete cur;}}//右孩子为空else if (cur->_right == nullptr){if (cur == _root){_root = _root->_left;delete cur;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}delete cur;}}//有两个孩子else{Node* pMinRight = cur;Node* minRight = cur->_right;while (minRight->_left){pMinRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pMinRight->_left == minRight){pMinRight->_left = minRight->_right;}else{pMinRight->_right = minRight->_right;}delete minRight;}return true;}}//找不到return false;}void InOrder(){_InOrder(_root);cout << endl;}private://销毁void Destory(Node* root){if (root == nullptr) return;Destory(root->_left);Destory(root->_right);delete root;}//中序遍历void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* Copy(Node* root){if (root == nullptr) return nullptr;Node* copy = new Node(root->_key, root->_value);copy->_left = Copy(root->_left);copy->_right = Copy(root->_right);return copy;}private://缺省值初始化Node* _root = nullptr;};}


http://www.hkcw.cn/article/KATBgpltFc.shtml

相关文章

DOA估计算法从原理到仿真——CBF、Capon、MUSIC算法

DOA估计算法从原理到仿真——CBF、Capon、MUSIC算法

本人第一篇CSDN博客~欢迎关注&#xff01; DOA是指Direction Of Arrival&#xff0c;是利用电磁波信号来获取目标或信源相对天线阵列的角度信息的方式&#xff0c;也称测向、空间谱估计。主要应用于雷达、通信、电子对抗和侦察等领域。 一、阵列信号模型 如上图所示&#xff0…
阅读更多...
算法效率的钥匙：从大O看复杂度计算

算法效率的钥匙：从大O看复杂度计算

目录 1.数据结构与算法 1.1数据结构介绍 1.2算法介绍 2.算法效率 2.1复杂度 2.1.1时间复杂度 2.1.1.1时间复杂度计算示例1 2.1.1.2时间复杂度计算示例2 2.1.1.3时间复杂度计算示例3 2.1.1.4时间复杂度计算示例4 2.1.1.5时间复杂度计算示例5 2.1.1.6时间复杂度计算示例6…
阅读更多...
A*算法详解【附算法代码与运行结果】

A*算法详解【附算法代码与运行结果】

算法背景 A*算法是一种在图形平面上&#xff0c;有多个路径中寻找一条从起始点到目标点的最短遍历路径的算法。它属于启发式搜索算法&#xff08;Heuristic Search Algorithm&#xff09;&#xff0c;因为它使用启发式方法来计算图中的节点&#xff0c;从而减少实际计算的节点…
阅读更多...
【leetcode】逐层探索：BFS求解最短路的原理与实践

【leetcode】逐层探索：BFS求解最短路的原理与实践

前言 &#x1f31f;&#x1f31f;本期讲解关于力扣的几篇题解的详细介绍~~~ &#x1f308;感兴趣的小伙伴看一看小编主页&#xff1a;GGBondlctrl-CSDN博客 &#x1f525; 你的点赞就是小编不断更新的最大动力 &#x1f386;那么废话不…
阅读更多...
七大排序算法深度解析：从原理到代码实现

七大排序算法深度解析：从原理到代码实现

1.排序 排序算法是计算机科学中最基础的技能之一&#xff0c;无论你是编程新手还是经验丰富的开发者&#xff0c;理解这些算法都能显著提升代码效率。本文将用最简单的方式&#xff0c;带你快速掌握七大经典排序算法的核心原理与实现。 1.1排序概念及其运用 排序是指将一组数据…
阅读更多...
Python的情感词典情感分析和情绪计算

Python的情感词典情感分析和情绪计算

一.大连理工中文情感词典 情感分析 (Sentiment Analysis)和情绪分类 (Emotion Classification&#xff09;都是非常重要的文本挖掘手段。情感分析的基本流程如下图所示&#xff0c;通常包括&#xff1a; 自定义爬虫抓取文本信息&#xff1b;使用Jieba工具进行中文分词、词性标…
阅读更多...
C++之vector类（超详细）

C++之vector类（超详细）

这节我们来学习一下&#xff0c;C中一个重要的工具——STL&#xff0c;这是C中自带的一个标准库&#xff0c;我们可以直接调用这个库中的函数或者容器&#xff0c;可以使效率大大提升。这节我们介绍STL中的vector。 文章目录 前言 一、标准库类型vector 二、vector的使用 2.…
阅读更多...
C++ 面试题常用总结 详解（满足c++ 岗位必备，不定时更新）

C++ 面试题常用总结 详解（满足c++ 岗位必备，不定时更新）

&#x1f4da; 本文主要总结了一些常见的C面试题&#xff0c;主要涉及到语法基础、STL标准库、内存相关、类相关和其他辅助技能&#xff0c;掌握这些内容&#xff0c;基本上就满足C的岗位技能&#xff08;红色标记为重点内容&#xff09;&#xff0c;欢迎大家前来学习指正&…
阅读更多...
『C++成长记』string模拟实现

『C++成长记』string模拟实现

🔥博客主页：小王又困了 📚系列专栏：C++ 🌟人之为学，不日近则日退 ❤️感谢大家点赞👍收藏⭐评论✍️ ​ 目录 一、存储结构 二、默认成员函数 📒2.1构造函数 📒2.2析构函数 📒2.3拷贝构造 📒2.4赋值重载 三、容量操作 📒3.1获取有效字符长度…
阅读更多...
多态的使用和原理（c++详解）

多态的使用和原理（c++详解）

一、多态的概念 多态顾名思义就是多种形态&#xff0c;它分为编译时的多态&#xff08;静态多态&#xff09;和运行时的多态&#xff08;动态多态&#xff09;&#xff0c;编译时多态&#xff08;静态多态&#xff09;就是函数重载&#xff0c;模板等&#xff0c;通过不同的参数…
阅读更多...
C++ 底层实现细节隐藏全攻略：从简单到复杂的五种模式

C++ 底层实现细节隐藏全攻略：从简单到复杂的五种模式

目录标题 1 引言&#xff1a;为什么要“隐藏实现”1.1 头文件暴露带来的三大痛点1.2 ABI 稳定 vs API 兼容&#xff1a;先分清概念1.3 选型三问法——评估你到底要不要隐藏 2 模式一&#xff1a;直接按值成员 —— “裸奔”也能跑2.1 典型写法与最小示例2.2 何时按值最合适&…
阅读更多...
使用国内镜像网站在线下载安装Qt（解决官网慢的问题）——Qt

使用国内镜像网站在线下载安装Qt（解决官网慢的问题）——Qt

国内镜像网站 中国科学技术大学&#xff1a;http://mirrors.ustc.edu.cn/qtproject/清华大学&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/qt/北京理工大学&#xff1a;http://mirror.bit.edu.cn/qtproject/ 南京大学&#xff1a;https://mirror.nju.edu.cn/qt腾讯镜像&…
阅读更多...
超全超详细！JDK 安装及环境配置（Java SE 8 保姆级教程）

超全超详细！JDK 安装及环境配置（Java SE 8 保姆级教程）

一、JDK 简介 JDK&#xff08;Java Development Kit&#xff09;是用于开发 Java 程序的工具包&#xff0c;包括编译器 javac、Java 运行环境&#xff08;JRE&#xff09;以及各种开发工具。安装和配置 JDK 是学习和使用 Java 编程的第一步&#xff0c;以下是 Java 和 JDK 的具…
阅读更多...
Java 大视界 -- 基于 Java 的大数据分布式数据库在社交网络数据存储与查询中的架构设计与性能优化（225）

Java 大视界 -- 基于 Java 的大数据分布式数据库在社交网络数据存储与查询中的架构设计与性能优化（225）

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…
阅读更多...
C++协程从入门到精通

C++协程从入门到精通

文章目录 一、C协程入门知识&#xff08;一&#xff09;基本概念&#xff08;二&#xff09;特点&#xff08;三&#xff09;应用场景 二、C协程精通知识&#xff08;一&#xff09;高级特性&#xff08;二&#xff09;优化技巧&#xff08;三&#xff09;错误处理机制&#xf…
阅读更多...
蓝桥杯第十六届c组c++题目及个人理解

蓝桥杯第十六届c组c++题目及个人理解

本篇文章只是部分题目的理解&#xff0c;代码和思路仅供参考&#xff0c;切勿当成正确答案&#xff0c;欢迎各位小伙伴在评论区与博主交流&#xff01; 目录 题目&#xff1a;2025 题目解析 核心提取 代码展示 题目&#xff1a;数位倍数 题目解析 核心提取 代码展示 …
阅读更多...
C++日新月异的未来代码：C++11（上）

C++日新月异的未来代码：C++11（上）

文章目录 1.统一的列表初始化1.1 普通{ }初始化1.2 initializer_list 2.声明2.1 auto、nullptr2.2 decltype 3.左值右值3.1 概念3.2 左值引用与右值引用比较3.3 左值引用与右值引用的应用3.4 完美转发 希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力&#xf…
阅读更多...
C++从入门到实战（十二）详细讲解C++如何实现内存管理

C++从入门到实战（十二）详细讲解C++如何实现内存管理

C从入门到实战&#xff08;十二&#xff09;详细讲解C如何实现内存管理 前言一、C内存管理方式1. new/delete操作内置类型2. 异常与内存管理的联系&#xff08;简单了解&#xff09;3. new和delete操作自定义类型 二、 operator new与operator delete函数&#xff08;重点&…
阅读更多...
【2025年最新版】Java JDK安装、环境配置教程 （图文非常详细）

【2025年最新版】Java JDK安装、环境配置教程 （图文非常详细）

文章目录 【2025年最新版】Java JDK安装、环境配置教程 &#xff08;图文非常详细&#xff09;1. JDK介绍2. 下载 JDK3. 安装 JDK4. 配置环境变量5. 验证安装6. 创建并测试简单的 Java 程序6.1 创建 Java 程序&#xff1a;6.2 编译和运行程序&#xff1a;6.3 在显示或更改文件的…
阅读更多...
【Linux系统】从 C 语言文件操作到系统调用的核心原理

【Linux系统】从 C 语言文件操作到系统调用的核心原理

文章目录 前言lesson 15_基础IO一、共识原理二、回顾C语言接口2.1 文件的打开操作2.2 文件的读取与写入操作2.3 三个标准输入输出流 三、过渡到系统&#xff0c;认识文件系统调用3.1 open 系统调用1. 比特位标志位示例 3.2 write 系统调用1. 模拟实现 w 选项2. 模拟实现 a 选项…
阅读更多...
推荐文章

Copyright @ 2022~2023