前言
前面我们对二叉搜索树进行了讲解，本节内容我们将对该树的应用进行讲解，对二叉搜素树进行进一步的了解。
二叉搜索树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;
}
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) {
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;
else
return 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;
else
parent->_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;
else
parent->_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;
else
replaceParent->_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);
else
ret->_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;}
