湖北建设网站信息查询中心,手机派网站,采购软件,新手学做网站需要注意的几点阅读导航 前言一、搜索二叉树简介1. 概念2. 基本操作⭕搜索操作#x1f36a;搜索操作基本代码#xff08;非递归#xff09; ⭕插入操作#x1f36a;插入操作基本代码#xff08;非递归#xff09; ⭕删除操作#x1f36a;删除操作基本代码#xff08;非递归#xff0… 阅读导航 前言一、搜索二叉树简介1. 概念2. 基本操作⭕搜索操作搜索操作基本代码非递归 ⭕插入操作插入操作基本代码非递归 ⭕删除操作删除操作基本代码非递归 二、搜索二叉树的实现1. 非递归实现2. 递归实现 三、搜索二叉树的应用1. K模型2. KV模型 四、搜索二叉树的性能分析总结温馨提示 前言
前面我们讲了C语言的基础知识也了解了一些初阶数据结构并且讲了有关C的命名空间的一些知识点以及关于C的缺省参数、函数重载引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ 也了解了C中的模版以及学习了几个STL的结构也相信大家都掌握的不错接下来博主将会带领大家继续学习有关C比较重要的知识点——搜索二叉树二叉树进阶 。下面话不多说坐稳扶好咱们要开车了
一、搜索二叉树简介
1. 概念
搜索二叉树也称为二叉搜索树Binary Search TreeBST是一种二叉树的特殊形式。它满足以下条件
有序性对于任意节点其左子树中的所有节点的值都小于该节点的值右子树中的所有节点的值都大于该节点的值。唯一性每个节点的值唯一不存在相同值的节点。递归结构整个树的结构由左子树、右子树和根节点组成其中左子树和右子树也是搜索二叉树。 2. 基本操作
⭕搜索操作 从根开始比较查找比根大则往右边走查找比根小则往左边走查找。最多查找高度次走到到空还没找到这个值不存在。 在搜索二叉树中查找一个特定值的操作很简单。从根节点开始如果目标值等于当前节点的值则找到了目标节点如果目标值小于当前节点的值则在左子树中继续搜索如果目标值大于当前节点的值则在右子树中继续搜索。通过递归或循环可以在树中进行有效的搜索。
搜索操作基本代码非递归
bool Find(const K key)
{Node* ret _root;// 循环查找节点直到找到与 key 匹配的节点或遍历完整个树while (ret){// 如果当前节点的键值大于 key继续在左子树中查找if (ret-_key key){ret ret-_left;}// 如果当前节点的键值小于 key继续在右子树中查找else if (ret-_key key){ret ret-_right;}// 如果当前节点的键值等于 key找到匹配节点返回 trueelse{return true;}}// 遍历完整个树仍未找到匹配节点返回 falsereturn false;
}该函数接收一个键值 key表示需要查找的值。函数首先将根节点指针 _root 赋值给临时指针变量 ret。然后通过循环遍历树进行查找直到找到与 key 匹配的节点或遍历完整个树。
在循环中根据当前节点的键值与 key 的比较结果决定下一步的查找方向
如果当前节点的键值大于 key继续在左子树中查找如果当前节点的键值小于 key继续在右子树中查找如果当前节点的键值等于 key找到匹配节点返回 true。
当遍历完整个树仍未找到匹配节点时返回 false 表示未找到。
⭕插入操作 树为空则直接新增节点赋值给root指针树不空按二叉搜索树性质查找插入位置插入新节点 要向搜索二叉树中插入新节点需要找到合适的位置。从根节点开始与当前节点的值比较根据值的大小决定是在左子树还是右子树中进行插入。重复这个过程直到找到一个空的位置然后将新节点插入其中。
插入操作基本代码非递归
bool Insert(const K key)
{// 如果根节点为空直接将 key 作为根节点创建if (_root nullptr){_root new Node(key);return true;}Node* ret _root;Node* parent nullptr;// 找到 key 应该插入的位置while (ret){// 如果 key 小于当前节点的键值继续在左子树查找if (key ret-_key){parent ret;ret ret-_left;}// 如果 key 大于当前节点的键值继续在右子树查找else if (key ret-_key){parent ret;ret ret-_right;}// 如果 key 已经存在于树中返回 falseelse{return false;}}// 创建新节点将其插入正确的位置Node* cur new Node(key);if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;
}该函数接收一个键值 key表示需要插入的值。函数首先判断根节点是否为空如果为空则直接将 key 作为根节点插入并返回 true。否则使用循环找到 key 需要插入的位置
如果 key 小于当前节点的键值继续在左子树查找如果 key 大于当前节点的键值继续在右子树查找如果 key 等于当前节点的键值则说明值已经存在于树中返回 false。
当找到正确的位置时创建一个新的节点 cur并将其插入到树中。具体实现如下
如果 key 小于父亲节点的键值将 cur 插入父节点的左子树中如果 key 大于父亲节点的键值将 cur 插入父节点的右子树中。
插入完成后返回 true 表示插入成功。
⭕删除操作
删除节点的过程相对复杂需要考虑不同的情况主要分为以下三种情况处理 删除节点没有子节点叶子节点直接将该节点删除即可将其父节点指向它的指针置为 NULL。 删除节点有一个子节点将该节点的子节点替代该节点的位置将该节点的父节点指向它的指针直接指向子节点。 删除节点有两个子节点这是最复杂的情况。需要找到该节点的后继节点或者前驱节点来替代该节点的位置。后继节点是指比当前节点大的最小节点前驱节点是指比当前节点小的最大节点。 找到后继节点的方法是在当前节点的右子树中找到值最小的节点即右子树中最左边的节点然后将其值复制到待删除节点的位置再删除后继节点。 找到前驱节点的方法是在当前节点的左子树中找到值最大的节点即左子树中最右边的节点然后将其值复制到待删除节点的位置再删除前驱节点。
删除操作基本代码非递归
bool Erase(const K key)
{Node* ret _root;Node* parent nullptr;// 循环查找节点直到找到匹配的节点或遍历完整个树while (ret){// 如果 key 小于当前节点的键值继续在左子树查找if (key ret-_key){parent ret;ret ret-_left;}// 如果 key 大于当前节点的键值继续在右子树查找else if (key ret-_key){parent ret;ret ret-_right;}// 如果找到匹配的节点else{// 删除节点// 1. 如果当前节点的左子树为空if (ret-_left nullptr){// 如果是根节点if (_root-_key key){Node* tmp _root;_root _root-_right;delete tmp;return true;}else{// 如果是父节点的左子节点if (parent-_left ret){parent-_left ret-_right;}// 如果是父节点的右子节点else{parent-_right ret-_right;}delete ret;}}// 2. 如果当前节点的右子树为空else if (ret-_right nullptr){// 如果是根节点if (_root-_key key){Node* tmp _root;_root _root-_left;delete tmp;return true;}else{// 如果是父节点的左子节点if (parent-_left ret){parent-_left ret-_left;}// 如果是父节点的右子节点else{parent-_right ret-_left;}delete ret;}}// 3. 如果当前节点的左右子树都不为空else{// 找到右子树中最小的节点用来替代当前节点Node* pminRight ret;Node* minRight ret-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}// 将右子树中最小节点的值赋给当前节点并删除最小节点ret-_key minRight-_key;if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;}return true;}}// 遍历完整个树仍未找到匹配节点返回 falsereturn false;
}该函数接收一个键值 key表示需要删除的值。函数首先将根节点指针 _root 赋值给临时指针变量 ret并初始化父节点指针 parent 为 nullptr。然后通过循环遍历树进行查找直到找到与 key 匹配的节点或遍历完整个树。
在循环中根据待删除节点的键值与 key 的比较结果决定下一步的查找方向
如果 key 小于当前节点的键值继续在左子树中查找如果 key 大于当前节点的键值继续在右子树中查找如果当前节点的键值等于 key找到匹配节点并执行删除操作。
删除操作分为以下三种情况
如果当前节点的左子树为空将当前节点的右子树链接到父节点的对应位置并删除当前节点。如果当前节点的右子树为空将当前节点的左子树链接到父节点的对应位置并删除当前节点。如果当前节点的左右子树都不为空需要找到当前节点右子树中最小的节点即右子树的最左下角节点将该节点的值赋给当前节点然后删除最小节点。
在执行删除操作时可能存在以下两种特殊情况
如果当前节点是根节点需要更新 _root 指针让其指向新的根节点。如果当前节点是某个节点的左子节点或右子节点需要将该节点的父节点链接到删除节点的子节点与该节点相邻的子树会被删除然后释放删除节点的内存。
最后如果遍历整个树仍未找到匹配节点说明该节点不存在函数返回 false。
二、搜索二叉树的实现
1. 非递归实现
namespace yws
{
templateclass Kstruct BSTreeNode{// 二叉搜索树节点的定义BSTreeNode(const K key): _left(nullptr), _right(nullptr), _key(key){}BSTreeNodeK* _left; // 左子节点指针BSTreeNodeK* _right; // 右子节点指针K _key; // 节点存储的键值};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public://构造BSTree():_root(nullptr){}//拷贝构造BSTree(const BSTreeK t){_root Copy(t._root);}//赋值构造BSTreeK operator(BSTreeK t){std::swap(_root, t._root);return *this;}//析构~BSTree(){Destory(_root);}bool Insert(const K key){// 如果根节点为空直接将 key 作为根节点创建if (_root nullptr){_root new Node(key);return true;}Node* ret _root;Node* parent nullptr;// 找到 key 应该插入的位置while (ret){// 如果 key 小于当前节点的键值继续在左子树查找if (key ret-_key){parent ret;ret ret-_left;}// 如果 key 大于当前节点的键值继续在右子树查找else if (key ret-_key){parent ret;ret ret-_right;}// 如果 key 已经存在于树中返回 falseelse{return false;}}// 创建新节点将其插入正确的位置Node* cur new Node(key);if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;}bool Find(const K key){Node* ret _root;// 循环查找节点直到找到与 key 匹配的节点或遍历完整个树while (ret){// 如果当前节点的键值大于 key继续在左子树中查找if (ret-_key key){ret ret-_left;}// 如果当前节点的键值小于 key继续在右子树中查找else if (ret-_key key){ret ret-_right;}// 如果当前节点的键值等于 key找到匹配节点返回 trueelse{return true;}}// 遍历完整个树仍未找到匹配节点返回 falsereturn false;}bool Erase(const K key){Node* ret _root;Node* parent nullptr;// 循环查找节点直到找到匹配的节点或遍历完整个树while (ret){// 如果 key 小于当前节点的键值继续在左子树查找if (key ret-_key){parent ret;ret ret-_left;}// 如果 key 大于当前节点的键值继续在右子树查找else if (key ret-_key){parent ret;ret ret-_right;}// 如果找到匹配的节点else{// 删除节点// 1. 如果当前节点的左子树为空if (ret-_left nullptr){// 如果是根节点if (_root-_key key){Node* tmp _root;_root _root-_right;delete tmp;return true;}else{// 如果是父节点的左子节点if (parent-_left ret){parent-_left ret-_right;}// 如果是父节点的右子节点else{parent-_right ret-_right;}delete ret;}}// 2. 如果当前节点的右子树为空else if (ret-_right nullptr){// 如果是根节点if (_root-_key key){Node* tmp _root;_root _root-_left;delete tmp;return true;}else{// 如果是父节点的左子节点if (parent-_left ret){parent-_left ret-_left;}// 如果是父节点的右子节点else{parent-_right ret-_left;}delete ret;}}// 3. 如果当前节点的左右子树都不为空else{// 找到右子树中最小的节点用来替代当前节点Node* pminRight ret;Node* minRight ret-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}// 将右子树中最小节点的值赋给当前节点并删除最小节点ret-_key minRight-_key;if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;}return true;}}// 遍历完整个树仍未找到匹配节点返回 falsereturn false;}protected:Node* Copy(Node* root){if (root nullptr){return nullptr;}Node newnode new Node(root-_key);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;}void Destory(Node* root){if (root nullptr)return;Destory(root-_right);Destory(root-_left);delete root;root nullptr;}}private:Node* _root nullptr;};
}2. 递归实现
namespace yws
{templateclass Kstruct BSTreeNode{BSTreeNode(const K key): _left(nullptr), _right(nullptr), _key(key){}BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public://构造BSTree():_root(nullptr){}//拷贝构造BSTree(const BSTreeK t){_root Copy(t._root);}//赋值构造BSTreeK operator(BSTreeK t){std::swap(_root, t._root);return *this;}//析构~BSTree(){Destory(_root);}void Inorder() // 中序遍历{_Inorder(_root);cout endl;}//递归版本实现bool FindR(const K key){return _FindR(_root, key);}bool InsertR(const K key){return _InsertR(_root, key);}bool EraseR(const K key){return _EraseR(_root, key);}protected:Node* Copy(Node* root){if (root nullptr){return nullptr;}Node newnode new Node(root-_key);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;}void Destory(Node* root){if (root nullptr)return;Destory(root-_right);Destory(root-_left);delete root;root nullptr;}void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_key ;_Inorder(root-_right);}bool _FindR(Node* root, const K key){if (root nullptr){return false;}if (key root-_key){_FindR(root-_left, key);}else if (key root-_key){_FindR(root-_right, key);}else{return true;}}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (key root-_key){_InsertR(root-_left, key);}else if (key root-_key){_InsertR(root-_right, key);}else{return false;}}bool _EraseR(Node* root, const K key){if (root nullptr){return false;}if (key root-_key){return _EraseR(root-_right, key);}else if (key root-_key){return _EraseR(root-_left, key);}else{//开始删除Node* del root;//1.左节点为空if (root-_left nullptr){root root-_right;}//2.右节点为空else if (root-_right nullptr){root root-_left;}//3.左右节点都不为空else{//找右树的最小节点代替Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}root-_key minRight-_key;return _EraseR(root-_right, root-_key);}delete del;return true;}}private:Node* _root nullptr;};
}
三、搜索二叉树的应用
1. K模型
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。因此K模型对于不需要复杂数据处理功能的应用来说是一种轻量级的数据管理方案。
比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树。在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
2. KV模型
KV模型每一个关键码key都有与之对应的值Value即 Key, Value 的键值对。该种方式在现实生活中非常常见
假设有一个存储学生信息的系统每个学生信息仅包括学生的唯一ID和学生的姓名。这种情况下我们可以使用K模型进行存储其中学生的ID作为key学生姓名作为value。
如下所示是几个学生的数据
学生ID学生姓名1001张三1002李四1003王五
使用KV模型存储这些数据时只需要记录学生ID作为key对应的学生姓名作为value。例如使用搜索二叉树来存储学生信息可以根据学生ID快速查找到对应的学生姓名。这个例子展示了如何将KV模型与搜索二叉树结合实现数据存储和检索的需求。
当需要查询某个学生的姓名时只需要在二叉树中查找对应的学生ID然后返回该学生的姓名即可。
四、搜索二叉树的性能分析
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为 l o g 2 N log_2 N log2N 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为 N 2 \frac{N}{2} 2N
如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优那么我们后面的AVL树和红黑树就可以完美解决上面的问题了。
总结
搜索二叉树是一种常用的数据结构用于存储和检索数据。搜索二叉树的应用包括K模型和KV模型。K模型指的是只存储键而不存储关联值的数据模型。KV模型则是使用键值对来存储和访问数据的一种模型可以用搜索二叉树实现。
最后搜索二叉树的性能取决于树的平衡程度理想情况下的时间复杂度为O(log n)但如果树不平衡性能会下降至O(n)。为了保持树的平衡可以采用平衡二叉树的变种如红黑树或AVL树。
综上所述搜索二叉树是一种重要的数据结构具有广泛的应用。了解搜索二叉树的基本操作、实现方法和性能分析对于合理选择和使用数据结构提高数据操作效率具有重要意义。
温馨提示
感谢您对博主文章的关注与支持另外我计划在未来的更新中持续探讨与本文相关的内容会为您带来更多关于C以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新不要错过任何精彩内容
再次感谢您的支持和关注。期待与您建立更紧密的互动共同探索C、算法和编程的奥秘。祝您生活愉快排便顺畅
