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

embedded/2025/1/16 23:29:49/

🥇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/embedded/154503.html

相关文章

【Linux 之一 】Linux常用命令汇总

Linux常用命令 ./catcd 命令chmodclearcphistoryhtoplnmkdirmvpwdrmtailunamewcwhoami 我从2021年4月份开始才开始真正意义上接触Linux&#xff0c;最初学习时是一脸蒙圈&#xff0c;啥也不会&#xff0c;啥也不懂&#xff0c;做了很多乱七八糟&#xff0c;没有条理的笔记。不知…

计算机网络八股文学习笔记

总结来自于javaguide,本文章仅供个人学习复习 javaguide计算机网络八股 文章目录 计算机网络基础网络分层模型OSI七层模型TCP/IP四层模型 HTTP从输入URL到页面展示到底发生了什么?(非常重要)HTTP状态码HTTP Header中常见的字段有哪些?HTTP和HTTPS有什么区别?(重要)HTTP/1.0和…

Node.js、Vue 和 React 的关系和区别

Node.js、Vue 和 React 是前端和后端开发中常用的技术&#xff0c;它们各自有不同的作用&#xff0c;但可以协同工作来构建现代化的 Web 应用。为了通俗易懂地理解它们的关系&#xff0c;我们可以用一个餐厅的比喻来说明。 1. Node.js&#xff1a;厨房的后台 Node.js 是一个基…

【kubernetes】K8S节点状态的维护

1 节点状态 节点是K8S集群中的一类重要资源&#xff0c;节点的状态通常可以作为判断集群异常的重要手段。 为了展示节点在各方面的健康程度&#xff0c;在kubectl describe node k8s-master的输出结果中的Conditions部分可以查看k8s-master节点的一些状态数据&#xff1a; N…

设计一个流程来生成测试模型安全性的问题以及验证模型是否安全

要使用 Ollama 运行 llama3.3:70b 模型&#xff0c;并设计一个流程来生成测试模型安全性的问题以及验证模型是否安全&#xff0c;可以按照以下步骤进行设计和实现。整个过程包括环境配置、设计安全测试提示词、执行测试以及分析结果。以下是详细的步骤和指导&#xff1a; 1. 环…

uni-app h5修改浏览器导航栏的 title以及icon

1.title 在pages.json文件中修改:"navigationBarTitleText":"uni-app" 2.icon的修改 2.1 在static中新建一个index.html文件作为模板文件&#xff0c;并且将你的icon图片也放在static文件夹下 2.2 在index.html文件中加入如下代码&#xff08;记得icon文件…

linux解压命令(可整理到CSDN)

1. tar -xvf ffmpeg-7.0.2.tar.xz x&#xff1a;表示解压文件。 v&#xff1a;表示在解压过程中显示文件&#xff08;verbose模式&#xff09;。这个选项是可选的&#xff0c;加上它可以让你看到正在解压的文件列表&#xff0c;但如果不加也不会影响解压过程。 f&#xff1a;…

网络安全的几种攻击方法

攻击方法 挂马: 就是在别人的网站文件里面放入网页木马或者是将代码潜入到对方正常的网页文件里&#xff0c;以使浏览者中马。 挖洞: 指漏洞挖掘。 加壳: 就是利用特殊的算法&#xff0c;将EXE可执行程序或者DLL动态连接库文件的编码进行改变&#xff08;比如实现压缩、加密&a…