模板网站建设公司电话,网站后台添加关键词,网页图片不显示,鲁中网站文章目录 1.内容安排说明2. 二叉搜索树2.1二叉搜索树的概念2.2二叉搜索树的实现2.3二叉树的性能#xff1a; 搜索二叉树的应用k 模型kv模型 1.内容安排说明
二叉树在前面c数据结构阶段#xff1b;已经讲过了#xff1b;本节取名二叉树进阶的原因是#xff1a; 1.map和set特… 文章目录 1.内容安排说明2. 二叉搜索树2.1二叉搜索树的概念2.2二叉搜索树的实现2.3二叉树的性能 搜索二叉树的应用k 模型kv模型 1.内容安排说明
二叉树在前面c数据结构阶段已经讲过了本节取名二叉树进阶的原因是 1.map和set特性需要先铺垫二叉搜索树 而二叉搜索树也是一种树形结构 2. 二叉搜索树的特性了解有助于更好的理解map和set的特性 3. 二叉树中部分面试题稍微有点难度在前面讲解大家不容易接受且时间长容易忘 4. 有些OJ题使用C语言方式实现比较麻烦比如有些地方要返回动态开辟的二维数组非常麻烦。
因此本节借二叉树搜索树对二叉树部分进行收尾总结。
2. 二叉搜索树
2.1二叉搜索树的概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 1.若它的左子树不为空则左子树上所有节点的值都小于根节点的值 2.若它的右子树不为空则右子树上所有节点的值都大于根节点的值 3.它的左右子树也分别为二叉搜索树
2.2二叉搜索树的实现
#pragma once
#include iostream
using namespace std;
template class K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};
template class K
class BSTree
{typedef BSTreeNodeK Node;
public:void Swap(Node* a, Node* b){Node s *a;*a *b;*b s;}//出先两个函数的原因是这里使用了递归递归需要使用递归类控制循环次数所以使用类get函数进行调用bool Find(const K key){return _Find(_root, key);}void InOrder(){_InOrder(_root);cout endl;}bool Insert(const K key){return _Insert(_root, key);}bool Erase(const K key){return _Erase(_root, key);}~BSTree(){Destroy(_root);}BSTree(){}BSTree(const BSTreeK t ){_root Copy(t._root);}BSTreeK operator (const BSTreeK t){swap(_root,t._root);return *this;}private:Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}bool _Find(Node* root, const K key){if (root nullptr){return false;}else{if (key root-_key){_Find(root-_right, key);}else if (key root-_key){_Find(root-_left, key);}else{return true;}}}bool _Insert(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (key root-_key){_Insert(root-_right, key);}else if (key root-_key){_Insert(root-_left, key);}else{return false;}}bool _Erase(Node* root, const K key){if (root nullptr){return false;}else{if (key root-_key){return _Erase(root-_right, key);}else if (key root-_key){return _Erase(root-_left, key);}else{if (root-_right nullptr){Node* n root;root root-_left;delete n;return true;}else if (root-_left nullptr){Node* n root;root root-_right;delete n;return true;}else{Node* cur root-_left;while (cur-_right){cur cur-_right;}swap(cur-_key, root-_key);return _Erase(_root-_right, key);}}}}void Destroy(Node* root){if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}private:Node* _root nullptr;
};2.3二叉树的性能
二叉树的时间复杂度这里的是时间复杂度测量的是查找的时间复杂度原因删除和添加都修要使用查找哦来进行 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为 l o g 2 N log_2 N log2N 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为 N 2 \frac{N}{2} 2N
搜索二叉树的应用
k 模型
定义K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。 例子 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 kv模型
定义每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。 // 改造二叉搜索树为KV结构
templateclass K, class V
struct BSTNode{BSTNode(const K key K(), const V value V()): _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value){}BSTNodeT* _pLeft;BSTNodeT* _pRight;K _key;V _value};
templateclass K, class V
class BSTree{typedef BSTNodeK, V Node;typedef Node* PNode;
public:BSTree(): _pRoot(nullptr){}PNode Find(const K key);bool Insert(const K key, const V value)bool Erase(const K key)
private:PNode _pRoot;
比特就业课
2.5 二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。};
void TestBSTree3()
{// 输入单词查找单词对应的中文翻译BSTreestring, string dict;dict.Insert(string, 字符串);dict.Insert(tree, 树);dict.Insert(left, 左边、剩余);dict.Insert(right, 右边);dict.Insert(sort, 排序);// 插入词库中所有单词string str;while (cinstr){BSTreeNodestring, string* ret dict.Find(str);if (ret nullptr){cout 单词拼写错误词库中没有这个单词: str endl;}else{cout str 中文翻译: ret-_value endl;}}
}
void TestBSTree4()
{// 统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 香蕉 };BSTreestring, int countTree;for (const auto str : arr){// 先查找水果在不在搜索树中// 1、不在说明水果第一次出现则插入水果, 1// 2、在则查找到的节点中水果对应的次数//BSTreeNodestring, int* ret countTree.Find(str);auto ret countTree.Find(str);if (ret NULL){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();
}搜索二叉树的实现和应用源码
