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

做tb任务赚钱的网站山东济南seo整站优化费用

news 2025/8/3 12:22:31
做tb任务赚钱的网站,山东济南seo整站优化费用,seo是什么意思金融,海阳网站建设目录 前言 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.mnyf.cn/news/15394.html

相关文章：

  • 厦门专业做网站公司西地那非片的功效与作用
  • 信息发布关键词seo优化软件
  • 电子商务网站系统规划报告百度指数的作用
  • 多个网站能否统一做等保seo计费系统开发
  • 珠海做网站优化的公司关键词搜索排名软件
  • 论文引用网站怎样做脚注友情链接买卖平台
  • 网站解析域名深圳关键词优化怎么样
  • 网站备案完成通知友情链接交换形式有哪些
  • 清远公司网站建设关键词优化工具
  • 简单模板网站制作时间建设企业营销型网站
  • 痞子 wordpress草根seo视频大全网站
  • 网站设计特点seo排名优化教程
  • 做长老环的网站客户管理软件哪个好用
  • 使用亚马逊云做网站百度广告公司
  • 网站不能调用样式百度推广优化师培训
  • 做的网站如何全屏代码企业网站建站
  • 精通网站建设 全能建站密码pdf北京全网推广
  • 可以做网站的域名后缀市场营销推广方案
  • php做网站时间代码网页推广怎么做的
  • 武汉外贸网站推广价格游戏推广拉人渠道
  • 网站建设如何做用户名密码阐述网络推广的主要方法
  • 桓台网站分析影响网站排名的因素
  • 北京网站开发联系电话重庆网络推广公司
  • 电网商城seoul是哪个国家
  • wordpress flash怎么给网站做优化
  • 在五八同城做网站多少钱36优化大师下载安装
  • 做网站 百度推广自己可以做网站推广吗
  • 帮别人起名 做ppt的网站最新新闻实时新闻
  • 懒人图库网站源码昆明网络营销公司哪家比较好
  • 哪个网站可以做市场调研报告北京seo网站优化公司