当前位置： 首页 > news >正文

楚雄市网站建设公司郑州app网站公司

news 2025/9/16 15:59:16
楚雄市网站建设公司,郑州app网站公司,网站安全检测官网,win没有wordpress目录 前言 1. 二叉搜索树的概念 2. 二叉搜索树的实现 2.1 二叉树的结构 2.2 二叉树查找 2.3 二叉树的插入和中序遍历 2.4 二叉树的删除 3. 二叉搜索树的应用 3.1 KV模型实现 3.2 应用 4. 二叉搜索树分析 总结 前言 本文将深入探讨二叉搜索树这一重要的数据结构。二…

目录

前言

1. 二叉搜索树的概念

2. 二叉搜索树的实现

2.1 二叉树的结构

2.2 二叉树查找

2.3 二叉树的插入和中序遍历

2.4 二叉树的删除

3. 二叉搜索树的应用

3.1 KV模型实现

3.2 应用

4. 二叉搜索树分析

总结

前言

本文将深入探讨二叉搜索树这一重要的数据结构。二叉搜索树不仅是一个功能强大的数据结构，而且在实际应用中展现出了极高的实用性。它以其独特的组织方式，使得查找、插入和删除操作都能在平均对数到线性时间内完成，从而大大提高了数据处理的效率。为了更好地理解二叉搜索树的工作原理，我们使用C++语言实现了一个简单的二叉搜索树。

1. 二叉搜索树的概念

二叉搜索树（Binary Search Tree），也称二叉排序树，是一种特殊的二叉树。二叉搜索树可以为空树。如果不为空树，有以下的性质：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 左子树和右子树也都是二叉搜索树。

2. 二叉搜索树的实现

2.1 二叉树的结构

先自定义一个二叉树结点的类，该类将使用模版。一般来说，有两种类型的二叉搜索树。

  • K模型：K模型即只有key作为关键码，自定义结点类型中只需要存储Key即可。
  • KV模型：每一个关键码key，都有与之对应的值Value，即<Key，Value>键值对。

下面的代码是两种模型自定义类的实现，把下面的代码放到BSTree.h文件下。分别封装到key和keyValue的命名空间中。我们先实现K模型的二叉树成员函数。再如法炮制实现第二种模型的成员函数。

  1. #pragma once
#include <iostream>
using namespace std;namespace key
{template<class K>struct BSTNode{BSTNode(const K& key = K()):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTNode<K>* _left;BSTNode<K>* _right;};template<class K>class BSTree{typedef BSTNode<K> Node;//...private:Node* root;}
}namespace keyValue
{template<class K, class V>struct BSTNode{BSTNode(const K& key = K(), const V& value = V()):_key(key),_value(value), _left(nullptr), _right(nullptr){}K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;};template<class K, class V>class BSTree{typedef BSTNode<K, V> Node;//...private:Node* root;}
}

2.2 二叉树查找

二叉搜索树的查找操作比较简单。

  • 函数的返回值是个布尔值。查找成功返回true，失败返回false。
  • 从根开始比较关键码，进行查找。如果关键码比根的大往右边查找，比根的小就往左边查找。
  • 最多会查找这颗二叉树的高度次，如果走到空，说明这个值不存在。
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.3 二叉树的插入和中序遍历

int arr[] = {11, 7, 18, 9, 14, 4, 23, 8, 16, 10};

二叉树的插入操作其实步骤根查找类似，插入具体过程如下：

  • 函数的返回值也是布尔值。插入成功返回true，插入失败返回false。
  • 如果树为空，直接使用new创建新结点，赋值给root指针。
  • 如果树不为空，使用while循环查找新结点的位置，如果找到某个节点存储的值，与插入的值相同，就不需要插入，返回false。此外，还要新定义一个二叉树结点类值，此值用来存储当前结点的父亲结点。因为需要判断新增结点是他的父亲结点左节点还是右节点。
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);}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;
}

二叉搜索树可以通过中序遍历得到有序的数据。在类中，定义一个中序遍历的子函数，再传入这棵树的根，进行遍历打印即可。

class BSTree
{//...
public://...void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;
};

我们写一个测试函数，测试一下插入函数。

#include "BSTree.h"void Test1()
{int arr[] = { 11, 7, 18, 9, 14, 4, 23, 8, 16, 10 };key::BSTree<int> tree;for (auto& e : arr){tree.Insert(e);}tree.InOrder();tree.Insert(2);tree.Insert(13);tree.InOrder();
}

运行结果如下：

 

2.4 二叉树的删除

二叉树的删除操作就有些麻烦。需要分几种情况：

  • 待删除结点没有孩子结点。
  • 待删除结点有一个孩子结点。
  • 待删除结点有左右孩子结点。

待删除结点没有孩子结点，可以直接释放该节点，使其父亲结点指向空即可。

待删除结点只有一个孩子结点。如下图，14结点有一个右孩子，左孩子为空。先释放14结点，再将其父亲结点的左指针指向16结点即可。如果待删除结点有一个左孩子，操作也是类似。

 不过这个有极端情况，如下面的第二张图，如果要删除的是根节点，并且根节点只有左孩子或者右孩子。此时，因为根结点没有父亲结点，所以直接释放根结点，让root指针指向他的孩子结点。

 

待删除结点有两个孩子结点的情况，就比较麻烦。如下图，思路是找到可以替换的结点，待删除结点的key值替换成该节点的key值，然后再释放这个替换结点，处理结点之间的连接关系。

  • 第一步需要查找待删除结点，如果没有找到，返回false。找到待删除结点，进行删除操作。
  • 待删除结点的左子树中的最右结点，是左子树中最大的结点，待删除结点的右子树中的最左结点是右子树中最小的结点。我们使用右子树中最左结点来替换待删除结点。
  • 我们先定义一个rightMin结点指针变量，用来找右子树中最小的结点，定义一个rightMinP来记录rightMin指向结点的父亲结点。
  • 其中rightMin一开始指向待删除结点的右孩子。rightMinP需要指向待删除节点，看第二张图片，如果右子树的最小结点就是待删除结点的右孩子，rightMInP不指向待删除节点，而是指向空，那么我们使用rightMinP这个空指针进行操作会有问题。

bool Erase(const K& key)
{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//删除操作{    // 0-1孩子if (cur->_left == nullptr){if (parent == nullptr)//删除根节点的情况{_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr)//删除根节点的情况{_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{//两个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;//不可为空，特殊情况会访问空指针Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;//需要判断右子树最小节点是父亲结点的左孩子还是右孩子if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;
}

我们写一个测试函数，测试一些删除函数的功能：

void Test2()
{int arr[] = { 11, 7, 18, 9, 14, 4, 23, 8, 16, 10 };key::BSTree<int> tree;for (auto& e : arr){tree.Insert(e);}tree.InOrder();for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("第%-2d次:", i + 1);tree.Erase(arr[i]);tree.InOrder();}
}

运行结果如下：

3. 二叉搜索树的应用

3.1 KV模型实现

上文有提到二叉搜索树有两种模型，其中在现实生活中比较常用的是KV模型。每个关键码key，都有对应的的值Value，即<Key，Value>键值对。

下面是KV模型的代码实现：

namespace keyValue
{template<class K, class V>struct BSTNode{BSTNode(const K& key = K(), const V& value = V()):_key(key),_value(value), _left(nullptr), _right(nullptr){}K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;};template<class K, class V>class BSTree{typedef BSTNode<K, V> Node;public:BSTree() = default;BSTree(const BSTree<K, V>& t){_root = Copy(t._root);}~BSTree(){Destroy(_root);_root = nullptr;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);}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;}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 Erase(const K& key){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{// 0-1孩子if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{// 两个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;cur->_value = rightMin->_value;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << " ";_InOrder(root->_right);}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);}private:Node* _root = nullptr;};
};

3.2 应用

二叉搜索树KV模型的应用有许多

  • 最经典的就是双语词典，英汉词典中，每个英文都有对应的中文，构成<word, chinese>键值对。
  • 中国公民每个人都有对象的身份证号码，即<中国人，身份证号码>键值对。
  • 还可以用来统计词语出现的次数，词语和其出现的次数就构成<word，count>键值对。

void TestBsTree3()
{keyValue::BSTree<string, string> dict;dict.Insert("left", "左边");dict.Insert("right", "右边");dict.Insert("apple", "苹果");dict.Insert("sort", "排序");dict.Insert("love", "爱");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << "->" << ret->_value << endl;}else{cout << "重新输入" << endl;}}
}

运行结果如下：

这是统计词语出现次数

void TestBSTree4()
{// 统计物品出现的次数string arr[] = { "书本", "笔", "书本", "笔", "书本", "书本", "笔", "书本", "橡皮", "书本", "橡皮" };keyValue::BSTree<string, int> countTree;for (const auto& str : arr){// 先查找物品在不在搜索树中// 1、不在，说明物品第一次出现，则插入<物品, 1>// 2、在，则查找到的节点中水果对应的次数++auto ret = countTree.Find(str);if (ret == NULL)countTree.Insert(str, 1);elseret->_value++;}countTree.InOrder();
}

运行结果如下：

4. 二叉搜索树分析

二叉搜索树的插入和删除操作，都需要先进行查找。查找操作一般最多查找这颗树的高度次，如果二叉搜索树是一个满二叉树或者完全二叉树，效率很高。可当二叉树退化成下图中右边这颗二叉树，基本上像链表的形态，那么查找的速度比原来慢了很多。

  • 最好的情况，二叉搜索树是接近一颗满二叉树，查找的时间复杂度是O(logN)。
  • 最坏的情况，二叉搜索树退化成只有单链，像链表的形态，查找的时间复杂度是O(N)。

因此，在二叉搜索树的基础上，又出现了平衡二叉搜索树，如AVL树和红黑树，会调整二叉树成为接近满二叉树的形态。

总结

通过本文的阐述，相信你应该对二叉搜索树的基本概念、特性以及操作方法已经有了一定的了解。不过想要掌握这个数据结构，还需要亲自上手编写一个二叉搜索树的代码。通过编码实践，才能更深刻体会到内部的工作机制。

创作不易，希望这篇文章能给你带来启发和帮助，如果喜欢这篇文章，请留下你的三连，你的支持的我最大的动力！！！

ee192b61bd234c87be9d198fb540140e.png

http://www.yayakq.cn/news/278194/

相关文章：

  • 静态网站怎么做留言板上海公司注册网上申请
  • 电脑上怎么做网站广州响应网站建设
  • 徐东网站建设公司在自己电脑上建设网站
  • 工商网站查询个人信息培训网站建设课程
  • 南阳做网站公司电话wordpress侧边栏缩略图
  • 惠州网站制作公司免费手机做网站
  • 网站建设整体设计思路临淄哪里做网站
  • 张店网站制作设计公司南宁做网店
  • 广州网站建设与网页设计可以免费学编程的网站
  • 益阳建站网站制作网站变成灰色
  • 网页制作代码淄博网站制作定制优化
  • 西安网站制作一般多少钱网站等保需要几年一做
  • 网站一个页面多少钱蜜蜂vp加速器七天试用
  • 找网站做外链是什么意思财务管理培训
  • 中国网站域名备案管理系统邯郸网站建设品牌加盟
  • 做文员的网站知乎织梦网站中的对话框怎摸做
  • 手机网站建设网怎么做一网站首页
  • 网站建设合同附加协议包括搜索引擎排名、网页标签优化、相关链接交换、网络广告投放等
  • 河南省住房和城乡建设厅网站确认书哪里有做网站推广
  • 东营建设信息网站wordpress识图搜索代码6
  • 丰泰建设集团有限公司网站微信网站建设信息
  • 做出网站迅雷2t免费空间活动
  • 中国建设银行招聘官网站wordpress后台怎么登陆
  • 外贸网店有哪些seo优化是什么
  • 网站建设预算明细百度登录个人中心
  • 免费的网站登录模板网站的页面结构
  • 做化工的 有那些网站网站建设业务范围
  • 广州企业网站制作哪家好百度域名怎么注册
  • dw做网站地图微信代运营的公司网站
  • 北京有哪些网站公司做健康食品的网站