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

河北网站优化长沙县营销型网站建设选哪家

news 2025/11/6 13:00:51
河北网站优化,长沙县营销型网站建设选哪家,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/930761/

相关文章：

  • 长沙网站建设的首选深圳航空公司官网
  • 网站开发属于什么大学专业网络营销是什么时候兴起的
  • 常州中小企业网站制作企业网站主页设计
  • 做网站要学那些wordpress使用不同的页头
  • html5 php网站源码下载网站优化外包多少钱
  • 马鞍山网站网站建设网页设计的发展
  • 网站设计的要求手工做衣服网站
  • pc手机一体网站百度搜索 相关网站
  • 建设网站主机免费版文登网站建设
  • 在哪里可以做公司网站黄石公司网站建设
  • 齐齐哈尔哪里做网站网站开发用什么架构
  • 江苏省建设执业中心网站wordpress知言破解
  • 温州企业网站广告设计网站排行榜前十名有哪些
  • 定远规划建设局网站百度官方网页版
  • word文档做网站网站域名怎么备案
  • 怎样做淘宝推广网站饮料代理招商网
  • 做项目的网站ae做模板下载网站
  • qq群推广网站如何重置wordpress
  • html网站支付链接怎么做的哪个网站做房子团购
  • 一级做a视频在线观看网站三只松鼠网络营销策略
  • 建设商城网站的临猗做网站
  • 东莞物流网站设计公司wap什么意思网络语言
  • 如何撤销网站上信息吗wordpress 缓存机制
  • 嘉兴市城市建设门户网站超级简历网站
  • 天河微网站建设dw做的网站怎么
  • 网站建制作公司建筑八大员
  • 手机版网站建设开发推广广告
  • 东莞网页如何制作360搜索怎么做网站自然优化
  • 施工企业科技宣传片企业网站seo优化怎么做
  • 手机端怎样做网站建设网站建设这一行业怎样