前言
前面我们对二叉搜索树进行了讲解，本节内容我们将对该树的应用进行讲解，对二叉搜素树进行进一步的了解。
二叉搜索树key和key/value使用场景
key搜索场景
只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断 key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结
构了。
场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的 车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单 词，查找是否在二叉搜索树中，不在则波浪线标红提示。
key/value搜索场景
每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树结构了，可以修改value。
场景1：简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文。
场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，（单词，1），单词存在，则++单词对应的次数。
代码展示
代码其实跟二叉搜索树没有相差太多，节点的成员中多了一个value值，函数把value加进去就行，函数我们增加了析构还有赋值重载以及树的拷贝，在赋值重载的实现思路与以前是一样的，进行指针地址交换。
树的拷贝和析构，我们都写了其中的子函数结构，并且都采取了递归的思想，一个一个节点的处理，在正式的拷贝构造和析构直接传入根节点调用子函数即可。
#include <iostream>
using namespace std;
namespace key_value {template<class K,class V>struct Node {K _key;V _value;Node<K,V>* _left;Node<K,V>* _right;Node(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};template<class K,class V>class BSTree {//typedef Node<K> Node;using Node = Node<K,V>;public:BSTree() = default;BSTree(const BSTree<K,V>&t) {_root = Copy(t._root);}~BSTree() {Destory(_root);_root = nullptr;}BSTree<K,V>&operator=(const BSTree<K,V>t) {swap(_root, t._root);return *this;}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;}elsereturn false;}cur = new Node(key,value);if (parent->_key < key)parent->_right = cur;elseparent->_left = cur;return true;}Node* Find(const K& key) {if (_root == nullptr)return nullptr;Node* cur = _root;while (cur) {if (cur->_key > key)cur = cur->_left;else if (cur->_key < key)cur = cur->_right;elsereturn cur;}return nullptr;}bool Erase(const K& key) {Node* cur = _root;Node* parent = nullptr;while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;}else if (cur->_key > key) {parent = cur;cur = cur->_left;}else//进行删除操作{ //节点左孩子为空if (cur->_left == nullptr) {if (cur == _root)_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 (cur == _root)_root = cur->_left;else {if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}//节点左右孩子均不为空else {//我们采用右子树最小(最左)Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left) {replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;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<<endl;_InOrder(root->_right);}Node* Copy(Node* root) {if (root == nullptr)return nullptr;Node* newnode = new Node(root->_key,root->_value);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;}void Destory(Node* root) {if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;}private:Node* _root = nullptr;};
}
int main() {string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };key_value::BSTree<string, int>countTree;for (auto& e : arr) {key_value::Node<string, int>* ret = countTree.Find(e);//auto ret= countTree.Find(e);if (ret == nullptr)countTree.Insert(e, 1);elseret->_value++;//countTree.Insert(e, ret->_value++);}countTree.InOrder();return 0;
}
//int main() {
//
// key_value::BSTree<string, string> dict;
//
// dict.Insert("left", "左边");
// dict.Insert("right", "右边");
// dict.Insert("insert", "插入");
// dict.Insert("string", "字符串");
// key_value::BSTree<string, string> copy = dict;
// string str;
// while (cin >> str)
// {
// auto ret = dict.Find(str);
// if (ret)
// {
// cout << "->" << ret->_value << endl;
// }
// else
// {
// if (str == "0")
// break;
// else
// cout << "没有此单词，请重新输入" << endl;
// }
//
//
// }
//
// return 0;}结束语
对于二叉搜索树的学习就告别一个段落了，下节我们将对_map和_set进行讲解。
最后感谢大家的支持！！!