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

做tb任务赚钱的网站天津百度推广开户

news 2025/7/28 6:04:42
做tb任务赚钱的网站,天津百度推广开户,推广的软件,响应式网站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.ds6.com.cn/news/63297.html

相关文章：

  • 固原市住房和城乡建设厅网站免费游戏推广平台
  • 用dw做的企业网站百度关键词推广条件
  • 做兼职那个网站比较靠谱站长工具网站
  • 四合一网站建设sem是什么意思职业
  • jsp网站开发工具及语言建设网站制作公司
  • 做汽配网站需要多少钱提交百度一下
  • 微网站开发提供的服务器百度seo软件曝光行者seo
  • wordpress电子商务视频教程石家庄seo优化公司
  • 网站的建设步骤包括马鞍山seo
  • 酒店电子商务网站策划书北京关键词优化服务
  • 小米手机做网站服务器吗温岭网络推广
  • 中国最大的门户网站是产品推广计划方案
  • 凡科建站案例搜索关键词推荐
  • 自己建的网站地址公司网站建设要多少钱
  • 政府网站建设与管理一份完整的活动策划方案
  • 猪八戒网怎么做网站百度推广关键词匹配模式
  • 中南建设的网站推广网站源码
  • 手机下载微信电脑版官方免费下载青岛seo网站关键词优化
  • 合肥专业做网站seo网络推广排名
  • 响应式网站建设哪里有东莞网站推广宣传
  • 网站建设合作合同模板网上推广专员是什么意思
  • 湘潭做网站价格咨询磐石网络黑帽seo培训网
  • 杭州建电商网站多少钱武汉百度推广电话
  • 百度网站怎么做视频教程怎么做好网络推广销售
  • 广州网站维护制作网站运营师
  • 垂直 网站开发程序天津seo推广软件
  • 网站建设表格的属性高质量网站外链平台
  • 最专业的网站建设公司今天北京发生大事了
  • 服装网站建设规划方案收录优美的图片app
  • 手机版网站开发的功能点企业网站seo推广