您的位置：首页 > 财经 > 金融 > 企业融资方式有哪些_域名代备案平台_成都纯手工seo_永久不收费的软件app

企业融资方式有哪些_域名代备案平台_成都纯手工seo_永久不收费的软件app

2024/11/17 15:30:32 来源：https://blog.csdn.net/wrf228/article/details/142830191  浏览:  次   关键词：企业融资方式有哪些_域名代备案平台_成都纯手工seo_永久不收费的软件app
企业融资方式有哪些_域名代备案平台_成都纯手工seo_永久不收费的软件app

目录

1.二叉搜索树概念

2.二叉搜索树实现

2.1二叉搜索树的查找

2.2二叉搜索树的插入

2.3二叉搜索树的删除

​​​​​​2.4整体代码

3.二叉搜索树应用

4.二叉搜索树性能分析

1.二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

2.二叉搜索树实现

// 结点结构
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};template<class K>
class BSTree
{typedef BSTNode<K> Node;private:Node* _root = nullptr;};
}

2.1二叉搜索树的查找

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

最多查找高度次，走到到空，还没找到，这个值不存在。

2.2二叉搜索树的插入

插入的具体过程：

  1. 树为空，则直接新增节点，赋值给root指针
  2. 树不空，按二叉搜索树性质查找插入位置，插入新节点

2.3二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面几种情况：

  • 要删除的结点无孩子结点

删除节点4，让父亲节点6的左指针指向节点4的左孩子或者右孩子（4的左右孩子都为空）

  • 要删除的结点只有左孩子结点或要删除的结点只有右孩子结点

删除节点14，让父亲节点10的右指针指向节点14的左孩子

删除节点6，让父亲节点3的右指针指向结点6的右孩子

删除节点6，让父亲节点3的右指针指向结点6的左孩子

删除节点14，让父亲节点10的右指针指向节点14的右孩子

  • 要删除的结点有左、右孩子结点

要删除节点3，找左子树中最右的那个结点2替换3结点再将2结点删除 或者 找右子树最左的结点4​替换节点3再删除节点4——替换删除，让操作变成上面两种情况

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个孩子可以合在一起处理// 对于0个孩子的parent随便指向cur的左或右孩子// 对于1个孩子的，parent只能指向cur的左孩子或者右孩子if (cur->_left == nullptr) // （左孩子为空，右孩子不为空）（左孩子和右孩子都为空）进入{if (parent == nullptr) // 要删除的结点为根结点 cur==_root{_root = cur->_right;}else{// 判断cur在parent的左还是右if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur; // 删除return true;}else if (cur->_right == nullptr)// （左孩子不为空，右孩子不为空）进入{if (parent == nullptr) // 要删除的结点为根结点 cur==_root{_root = cur->_left;}else{// 判断cur在parent的左还是右if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{// 2个孩子// 这里找右子树中最小的key替换Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}// 找到进行替换cur->_key = rightMin->_key;// 判断rightMin在rightMinP的左还是右if (rightMinP->_left == rightMin){// rightMin左孩子不可能有，右孩子有或没有rightMinP->_left = rightMin->_right; }else{rightMinP->_right = rightMin->_right;}delete rightMin; return true;}}}return false;}

​​​​​​2.4整体代码

namespace key // 命名空间域
{template<class K>struct BSTNode{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};template<class K>class BSTree{typedef BSTNode<K> Node;public:bool insert(const K& key){if (_root == nullptr) // 空树{_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur) // 树不为空找结点插入的位置{if (cur->_key < key){parent = cur; // 让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; // 插入成功}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;}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个孩子可以合在一起处理// 对于0个孩子的parent随便指向cur的左或右孩子// 对于1个孩子的，parent只能指向cur的左孩子或者右孩子if (cur->_left == nullptr) // （左孩子为空，右孩子不为空）（左孩子和右孩子都为空）进入{if (parent == nullptr) // 要删除的结点为根结点 cur==_root{_root = cur->_right;}else{// 判断cur在parent的左还是右if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur; // 删除return true;}else if (cur->_right == nullptr)// （左孩子不为空，右孩子不为空）进入{if (parent == nullptr) // 要删除的结点为根结点 cur==_root{_root = cur->_left;}else{// 判断cur在parent的左还是右if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{// 2个孩子// 这里找右子树中最小的key替换Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}// 找到进行替换cur->_key = rightMin->_key;// 判断rightMin在rightMinP的左还是右if (rightMinP->_left == rightMin){// rightMin左孩子不可能有，右孩子有或没有rightMinP->_left = rightMin->_right; }else{rightMinP->_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 << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};
}

3.二叉搜索树应用

  • K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

  • KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。
namespace keyValue
{template<class K, class V> // 增加一个参数struct BSTNode{K _key;V _value;BSTNode<K,V>* _left;BSTNode<K,V>* _right;BSTNode(const K& key,const V& value):_key(key),_value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree{typedef BSTNode<K,V> Node;public:bool insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}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;}else{parent->_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;}else{parent->_right = cur->_left;}}delete cur;return true;}else{// 2个孩子// 找右孩子中最小的key替换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 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);}private:Node* _root = nullptr;};
}

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对<word,chinese>;

 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

4.二叉搜索树性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

  • 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：\log _{2}N
  • 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N

如果退化成单支树，二叉搜索树的性能就失去了。改进得学习AVL树和红黑树。

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

linux之sed 科技评价 科技查新去哪儿？ 淘宝商品详情获取：技术与合规并行 平板电视从入门到精通 《计算机基础与程序设计》第九周 从零开始的 LLM: nanoGPT 学习笔记（1/2）

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989