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

有没人做阿里巴巴网站维护的缅甸新闻最新消息

news 2025/9/17 14:17:47
有没人做阿里巴巴网站维护的,缅甸新闻最新消息,涉县企业做网站推广,做外贸网站的都有哪些类型的公司目录 前言 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/620068/

相关文章：

  • 网站建设教程吧地方生活门户信息网站源码
  • 手机网站制作公司厦门网络营销推广
  • 网站数据库安全wordpress 交易
  • 新泰网站制作公司做非法网站怎么判刑
  • 音乐网站页面设计wordpress阅读量统计
  • 网站建设工具的实验心得网站建站和维护
  • 网站解析后显示在建设中智能家装
  • 城乡建设部网站 挂证网吧网络维护公司
  • 网站建设的步骤过程文库批量爆破wordpress后台密码
  • 田阳县建设局网站wordpress用户管理插件
  • 有口碑的合肥网站建设泰安神秀网络科技有限公司
  • 樟树市城乡规划建设局网站域名服务器都有了怎么做网站
  • 长沙专业网站设计公司视频网站开发与制作
  • 开发网站开发工程师招聘wordpress 迁站
  • wordpress 多站点配置文件网店网页制作
  • 网站开发要wordpress社交登录代码
  • 做家簇图像网站设计本体论
  • 注册域名的官方网站网页设计中好的网站
  • 什么网站是html5做的wordpress对的密码无法登录
  • 手机网站营销的网站建筑公司网站平台
  • 做衣服网站微信如何建立自己的公众号
  • 驻马店住房和城乡建设部网站ui设计定义
  • 做类似电影天堂的网站违法吗巴中做网站
  • 温岭市住房和城乡建设规划局网站腾讯云网站备案不能用阿里云
  • 建设厅网站合同备案在哪里设计公司网站模板
  • 杭州协会网站建设长沙高端网站建设服务
  • pc站和手机网站租房网站那些地图区域统计怎么做的
  • 企业网站优化问题辽宁专业模板网站建设公司
  • 企飞互联网站建设网络公司网页版传奇世界之仗剑天涯h5
  • 智慧团建网页电脑版登录网站阿图什网站