数据结构9——二叉搜索树

server/2025/1/16 15:58:19/

🥇1.二叉搜索树的概念

二叉搜索树(Binary Search Tree,BST)又称二叉排序树或二叉查找树，其要么是一棵空树，要么具有以下性质：

①：左子树上所有节点的值都小于根节点；

②：右子树上所有节点的值都大于根节点；

③：它的左右子树也都是二叉搜索树。

（于是我们发现：二叉搜索树的中序遍历是一个递增序列。 ）

举例：

（易混淆的点：二叉搜索树是要满足左子树中所有节点的值都要小于根，而不是根的直接子节点小于根即可，即：根的左孩子节点，左子树的孙子节点，重孙节点......都要小于根，右子树也是同样的道理。） 

🥇2. 二叉搜索树的实现

使用泛型编程构造出节点和类：

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

🥈2.1 二叉搜索树的查找

根据二叉搜索树的定义，二叉搜索树的查找无非就是拿待查找节点与根节点比较，比根大从右边找，比根小从左边找，最多查找树的高度次；

当找到空还未找到，则这个值在此二叉搜索树中不存在。

具体实现如下：

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;}

🥈2.2 二叉搜索树的插入

二叉搜索树的插入要注意两种情况：

①树本来就是空树，此时可以直接插入；

②树不为空，先查找到要插入的位置，再插入节点。

具体代码如下：

//插入bool Insert(const K& key){//①树本来就是空树，直接新增节点if (_root == nullptr){_root = new Node(key);return true;}//②树不为空，先查找到要插入的位置，再插入节点Node* parent = nullptr;Node* cur = _root;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;}

🥈2.3 二叉搜索树的删除

二叉搜索树的删除较为复杂，需要分情况讨论：

情况①：要删除的节点没有孩子

情况②：要删除的节点只有左孩子；

情况③：要删除的节点只有右孩子；

情况④：要删除的节点有两个孩子

实际操作中，可以将①②和①③合并，所以代码实现就只有三种情况：

情况①：要删除的节点没有左孩子（此节点只有右孩子或没有孩子）；

情况②：要删除的节点没有右孩子（此节点只有左孩子或没有孩子）；

①和②可以直接删除目标节点，然后将目标节点的孩子托付给爷爷；

情况③：要删除的节点有两个孩子；

③由于存在两个孩子，所以此时就不能再用“托孤”的方法了，我们可以采用替换法删除：找到一个合适的值换掉要删除的值，然后再删除这个“合适的值”，最后再“托孤”。那么这个所谓“合适的值”该如何寻找呢？到底多合适才算合适呢？

我们知道，二叉搜索树都满足左节点比根小，右节点比根大，换一种说法，根就是这组数据的“中位数”，当删除这个“中位数”时，我们只需再找一个中位数左右两边的值作为新的“中位数”就行了呀！

我们知道二叉搜索树的中序遍历就是一个递增序列，所以：

根左边的值是根的左子树的最右节点（以下图为例，8的左子树的最右节点就是7）；

根右边的值是根的右子树的最左节点（以下图为例，8的右子树的最左节点就是10）。

（我们以寻找根的右子树的最左节点作为替换值进行代码实现）

具体代码如下：

//删除bool Erase(const K& key){//1.先查找要删除的节点Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}//2.查找到要删除的节点else{//①要删除的节点没有左孩子（此节点只有右孩子或没有孩子）if (cur->_left == nullptr){if (cur == _root)//根节点单独处理{_root = cur->_right;}else//只有右孩子，将右孩子托付给爷爷（如上图的节点10）“托孤”{if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置{parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}//②要删除的节点没有右孩子（此节点只有左孩子或没有孩子）else if (cur->_right == nullptr){if (cur == _root)//根节点单独处理{_root = cur->_left;}else//只有左孩子，将左孩子托付给爷爷（如上图的节点14）“托孤”{if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置{parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}//③要删除的节点有两个孩子（如上图的节点3、6、8）else{// 替换法// 寻找右子树的最左值作为替换值Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}//已找到替换值，开始替换cur->_key = rightMin->_key;//“托孤”过程if (rightMin == rightMinParent->_left)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;}//遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);}

🥈测试

int main()
{BSTree<int> t;int a[] = { 3,6,9,1,4,2,7,5,8,10 };for (auto e : a){t.Insert(e);}t.InOrder();t.Erase(9);t.InOrder();t.Insert(52);t.InOrder();return 0;
}

结果如图：

 

🥇3.二叉搜索树的应用

学了二叉搜索树，可是二叉搜索树到底有什么实际的用途呢？接下来就介绍二叉搜索树的两个模型：K模型和KV模型。

🥈3.1 K 模型

K模型：只有Key作为关键码，结构中只需要存储Key，关键码即为需要搜索到的值。

比如：学校的门禁通过扫脸分辨此人是否为校内人员，具体方式如下：

以每个学生的脸部特征作为Key，构建一棵二叉搜索树；

在二叉搜索树中检索该学生是否存在，存在则开门禁，不存在则不开门禁。

具体实现如下：（为方便演示，这里以学生姓名设置Key，K模型的代码与2中二叉搜索树的实现相似，不同的是需要修改Find函数的返回值和返回类型）

template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://查找Node* 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 cur;}}return nullptr;}private:Node* _root = nullptr;
};int main()
{BSTree<string> Stu;Stu.Insert("张三");Stu.Insert("李四");Stu.Insert("王五");Stu.Insert("赵六");Stu.Insert("田七");string str;while (cin >> str){auto ret = Stu.Find(str);if (ret){cout << "开门" << endl;}else{cout << "保持关闭" << endl;}}return 0;
}

结果如图：

🥈3.2 KV模型

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。

KV模型相较于K模型更常见，比如：查找英汉词典中英文与中文的对应关系<English,Chinese>；查找学生姓名与性别的对应关系<Name,Sex>。

还以后者为例进行代码实现：

//KV模型
namespace Key_Value
{template<class K,class V>struct BSTreeNode{typedef BSTreeNode<K, V> Node;Node* _left;Node* _right;K _key;V _value;BSTreeNode(const K& key,const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};template<class K,class V>class BSTree{typedef BSTreeNode<K, V> Node;public://查找Node* 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 cur;}}return nullptr;}//插入bool Insert(const K& key,const V& value){//①树本来就是空树，直接新增节点if (_root == nullptr){_root = new Node(key, value);return true;}//②树不为空，先查找到要插入的位置，再插入节点Node* parent = nullptr;Node* cur = _root;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){//1.先查找要删除的节点Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}//2.查找到要删除的节点else{//①要删除的节点没有左孩子（此节点只有右孩子或没有孩子）if (cur->_left == nullptr){if (cur == _root)//根节点单独处理{_root = cur->_right;}else//只有右孩子，将右孩子托付给爷爷（如上图的节点10）“托孤”{if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置{parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}//②要删除的节点没有右孩子（此节点只有左孩子或没有孩子）else if (cur->_right == nullptr){if (cur == _root)//根节点单独处理{_root = cur->_left;}else//只有左孩子，将左孩子托付给爷爷（如上图的节点14）“托孤”{if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置{parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}//③要删除的节点有两个孩子（如上图的节点3、6、8）else{// 替换法// 寻找右子树的最左值作为替换值Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}//已找到替换值，开始替换cur->_key = rightMin->_key;//“托孤”过程if (rightMin == rightMinParent->_left)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;}//遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);std::cout << std::endl;}private:Node* _root = nullptr;};
}int main()
{Key_Value::BSTree<string, string> Stu;Stu.Insert("张三", "男");Stu.Insert("李四", "女");Stu.Insert("王五", "男");Stu.Insert("赵六", "女");Stu.Insert("田七", "女");string str;while (cin >> str){auto ret = Stu.Find(str);if (ret){cout << ret->_value << endl;}else{cout << "查无此人" << endl;}}return 0;
}

结果如图：


http://www.ppmy.cn/server/158852.html

相关文章

JavaSwing游戏开发之Camera原理

JavaSwing游戏开发之Camera原理

package org.timer;import javax.swing.*; import java.awt.*; import java.awt.event.*; import java.util.ArrayList; import java.util.List; import java.util.Random;public class GameCameraWithObjects extends JPanel implements KeyListener {// 游戏世界大小private …
阅读更多...
接口测试总结（http与rpc）

接口测试总结（http与rpc）

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 接口测试是测试系统组件间接口的一种测试。接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点。测试的重点是要检查数据的交换&#xff0c;传…
阅读更多...
【行空板K10】上传温湿度信息到EasyIoT平台

【行空板K10】上传温湿度信息到EasyIoT平台

目录 引言 EasyIoT平台 程序编写 测试结果 结语 引言 今天测试一下使用行空板K10上传数据到EasyIoT平台。这个平台是DFRobot自由的物联网云平台&#xff0c;也是Mind支持的4个MQTT平台之一。 EasyIoT平台 EasyIoT平台的优点是非常简单&#xff0c;没有阿里云、华为云那…
阅读更多...
FPGA EDA软件的位流验证

FPGA EDA软件的位流验证

位流验证&#xff0c;对于芯片研发是一个非常重要的测试手段&#xff0c;对于纯软件开发人员&#xff0c;最难理解的就是位流验证。在FPGA芯片研发中&#xff0c;位流验证是在做什么&#xff0c;在哪些阶段需要做位流验证&#xff0c;如何做&#xff1f;都是问题。 我们先整体的…
阅读更多...
浅谈云计算02 | 云计算模式的演进

浅谈云计算02 | 云计算模式的演进

云计算计算模式的演进 一、云计算计算模式的起源追溯1.2 个人计算机与桌面计算 二、云计算计算模式的发展阶段2.1 效用计算的出现2.2 客户机/服务器模式2.3 集群计算2.4 服务计算2.5 分布式计算2.6 网格计算 三、云计算计算模式的成熟与多元化3.1 主流云计算服务模式的确立3.1.…
阅读更多...
特制一个自己的UI库，只用CSS、图标、emoji图 第二版

特制一个自己的UI库，只用CSS、图标、emoji图 第二版

图&#xff1a; 代码&#xff1a; index.html <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>M…
阅读更多...
【STM32-学习笔记-1-】GPIO

【STM32-学习笔记-1-】GPIO

文章目录 GPIOⅠ、GPIO函数Ⅱ、GPIO_InitTypeDef结构体参数①、GPIO_Mode②、GPIO_Pin③、GPIO_Speed GPIO Ⅰ、GPIO函数 // 将指定的GPIO端口寄存器重置为默认值 void GPIO_DeInit(GPIO_TypeDef* GPIOx);// 将GPIO的备用功能寄存器重置为默认值 void GPIO_AFIODeInit(void);…
阅读更多...
stack_queue的底层,模拟实现,deque和priority_queue详解

stack_queue的底层,模拟实现,deque和priority_queue详解

文章目录 适配器Stack的模拟实现Queue的模拟实现vector和list的对比dequedeque的框架deque的底层 priority_queuepriority_queue的使用priority_queue的底层仿函数的使用仿函数的作用priority_queue模拟实现 适配器 适配器是一种模式&#xff0c;这种模式将类的接口转化为用户希…
阅读更多...
最新文章

Copyright @ 2022~2023