前言
二叉搜索树的在现实世界的应用很广泛，比如Key模型，Key-Value模型就是常见的两种的模型
一、Key模型
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。即就是判断key在不在就可以了。
比如：门禁系统，小区车辆出入系统等等
给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
我们前面文章中所完成的二叉搜索树就是key模型的二叉搜身树
二、Key/Value模型
Key/Value每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如商场的车辆出入系统（计时付费），高铁实名制车票系统等
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对
现在就让我们来实现一个key-value模型的二叉搜索树。
#pragma once template<class K, class V> struct BSTreeNode { BSTreeNode(const K& key = K(), const V& val = V()) :_key(key) ,_val(val) ,_left(nullptr) ,_right(nullptr) {} K _key; V _val; BSTreeNode<K,V>* _left; BSTreeNode<K,V>* _right; }; template<class K, class V> class BSTree { typedef BSTreeNode<K,V> Node; public: BSTree() :_root(nullptr) {} BSTree(const BSTree<K,V>& t) { _root = Copy(t._root); } ~BSTree() { _Destory(_root); } BSTree<K,V>& operator=(BSTree<K,V> t) { std::swap(_root, t._root); return *this; } bool Insert(const K& key,const V& val) { if (_root == nullptr) { _root = new Node(key,val); return true; } else { Node* parent = _root; Node* cur = _root; while (cur != nullptr) { if (cur->_key == key) { return false; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { parent = cur; cur = cur->_right; } } cur = new Node(key,val); if (parent->_key > key) { parent->_left = cur; } else if (parent->_key < key) { parent->_right = cur; } return true; } } void InOrder() { _InOrder(_root); } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key == key) { return cur; } else if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } } return nullptr; } bool Erase1(const K& key) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { if (parent == nullptr) { if (cur->_left == nullptr) { _root = cur->_right; delete cur; return true; } else if (cur->_right == nullptr) { _root = cur->_left; delete cur; return true; } else { Node* leftMaxParent = cur; Node* leftMax = cur->_left; if (leftMax->_right == nullptr) { leftMax->_right = cur->_right; delete cur; _root = leftMax; return true; } while (leftMax->_right) { leftMaxParent = leftMax; leftMax = leftMax->_right; } std::swap(leftMax->_key, cur->_key); std::swap(leftMax->_val, cur->_val); leftMaxParent->_right = leftMax->_left; delete leftMax; leftMax = nullptr; return true; } } if (parent->_left == cur) { if (cur->_left == nullptr) { parent->_left = cur->_right; delete cur; return true; } else if (cur->_right == nullptr) { parent->_left = cur->_left; delete cur; return true; } else { Node* leftMaxParent = cur; Node* leftMax = cur->_left; if (leftMax->_right == nullptr) { leftMax->_right = cur->_right; delete cur; parent->_left = leftMax; return true; } while (leftMax->_right) { leftMaxParent = leftMax; leftMax = leftMax->_right; } std::swap(leftMax->_key, cur->_key); std::swap(leftMax->_val, cur->_val); leftMaxParent->_right = leftMax->_left; delete leftMax; leftMax = nullptr; return true; } } else { if (cur->_left == nullptr) { parent->_right = cur->_right; delete cur; return true; } else if (cur->_right == nullptr) { parent->_right = cur->_left; delete cur; return true; } else { Node* leftMaxParent = cur; Node* leftMax = cur->_left; if (leftMax->_right == nullptr) { leftMax->_right = cur->_right; delete cur; parent->_right = leftMax; return true; } while (leftMax->_right) { leftMaxParent = leftMax; leftMax = leftMax->_right; } std::swap(leftMax->_key, cur->_key); std::swap(leftMax->_val, cur->_val); leftMaxParent->_right = leftMax->_left; delete leftMax; leftMax = nullptr; return true; } } } } return false; } bool Erase2(const K& key) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { if (cur->_left == nullptr) { if (parent == nullptr) { _root = cur->_right; } else if (parent->_left == cur) { parent->_left = cur->_right; } else if (parent->_right == cur) { parent->_right = cur->_right; } } else if (cur->_right == nullptr) { if (parent == nullptr) { _root = cur->_left; } else if (parent->_left == cur) { parent->_left = cur->_left; } else if (parent->_right = cur) { parent->_right = cur->_left; } } else { Node* leftMax = cur->_left; Node* leftMaxParent = cur; while (leftMax->_right) { leftMaxParent = leftMax; leftMax = leftMax->_right; } std::swap(cur->_key, leftMax->_key); std::swap(cur->_val, leftMax->_val); if (leftMaxParent->_left == leftMax) { leftMaxParent->_left = leftMax->_left; } else { leftMaxParent->_right = leftMax->_left; } cur = leftMax; } delete cur; return true; } } } Node* FindR(const K& key) { return _FindR(_root, key); } bool InsertR(const K& key,const V& val) { return _InsertR(_root, key, val); } bool EraseR(const K& key) { return _EraseR(_root, key); } private: Node* Copy(Node* root) { if (root == nullptr) { return nullptr; } Node* Copyroot = new Node(root->_key, root->val); Copyroot->_left = Copy(root->_left); Copyroot->_right = Copy(root->_right); return Copyroot; } void _Destory(Node*& root) { if (root == nullptr) { return; } _Destory(root->_left); _Destory(root->_right); delete root; root == nullptr; } bool _EraseR(Node*& root, const K& key) { if (root == nullptr) { return false; } if (root->_key < key) { return _EraseR(root->_right, key); } else if (root->_key > key) { return _EraseR(root->_left, key); } else { Node* del = root; if (root->_left == nullptr) { root = root->_right; } else if (root->_right == nullptr) { root = root->_left; } else { Node* leftMax = root->_left; while (leftMax->_right) { leftMax = leftMax->_right; } std::swap(leftMax->_key, root->_key); std::swap(leftMax->_val, root->_val); return _EraseR(root->_left, key); } delete del; return true; } } bool _InsertR(Node*& root, const K& key, const V& val) { if (root == nullptr) { root = new Node(key, val); return true; } if (root->_key < key) { return _InsertR(root->_right, key, val); } else if (root->_key > key) { return _InsertR(root->_left, key, val); } else { return false; } } Node* _FindR(Node* root, const K& key) { if (root == nullptr) { return nullptr; } if (root->_key == key) { return root; } else if (root->_key > key) { return _FindR(root->_left, key); } else { return _FindR(root->_right, key); } } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " :" << root->_val << endl; _InOrder(root->_right); } private: Node* _root; };
如上就是我们的KV模型的二叉搜索树。我们可以使用如下的两个模型，就是我们的这棵树的应用
void test1() { BSTree<string, string> dic; dic.Insert("review", "复习"); dic.Insert("product", "产品，产物"); dic.Insert("education", "教育"); dic.Insert("interfere", "干涉"); cout << "请输入单词" << endl; string str; while (cin >> str) { BSTreeNode<string, string>* ret = dic.Find(str); if (ret) { cout << ret->_val << endl; } else { cout << "无此单词" << endl; cout << "请你添加单词的意思：" << endl; string str_val; cin >> str_val; dic.Insert(str, str_val); } cout << "请输入单词" << endl; } }
如上就是一个查找单词的模型，可以帮我们快速找出单词的意思，如果没有，可以自行添加意思
如下所示是一个水果计数的应用
void test2() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" }; BSTree<string, int> FruitCount; for (auto& e : arr) { BSTreeNode<string, int>* ret = FruitCount.Find(e); if (ret == nullptr) { FruitCount.Insert(e, 1); } else { ret->_val++; } } FruitCount.InOrder(); }
总结
本节主要讨论了二叉搜索树的两种应用。希望能对大家带来帮助
