二叉树搜索树（下）

二叉搜索树key和key/value使用场景

key搜索场景

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断 key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。

场景1：⼩区无⼈值守⻋库，⼩区⻋库买了⻋位的业主⻋才能进⼩区，那么物业会把买了⻋位的业主的⻋牌号录⼊后台系统，⻋辆进⼊时扫描⻋牌在不在系统中，在则抬杆，不在则提⽰⾮本⼩区⻋辆，⽆法进⼊。

场景2：检查⼀篇英⽂⽂章单词拼写是否正确，将词库中所有单词放⼊二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

可以通俗地说，只有key作为关键码，就是判断在不在的问题。

key/value搜索场景

每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字⾛二叉搜索树的规则进⾏⽐较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树⽀持修改，但是不⽀持修改key，修改key破坏搜索树结构了，可以修改value。

场景1：简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中⽂)，搜索时输⼊英⽂，则同时查找到了英⽂对应的中⽂。

场景2：商场⽆⼈值守⻋库，⼊⼝进场时扫描⻋牌，记录⻋牌和⼊场时间，出⼝离场时，扫描⻋牌，查找⼊场时间，⽤当前时间-⼊场时间计算出停⻋时⻓，计算出停⻋费⽤，缴费后抬杆，⻋辆离场。

场景3：统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。

我们可以用命名空间将我们之前写的只有key的搜索二叉树的代码进行隔离，再用另一个命名空间将接下来要写的key/value二叉搜索树的代码进行隔离。

参考代码：

namespace key
{//之前写的只有key的二叉搜索树结构和方法定义代码
}
namespace key_value
{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{using Node = BSTNode<K,V>;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 (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}elsereturn false;//避免冗余}//到这里说明cur已经找到空位置了，但是不知道是从右走的还是往左走的，得再比一次cur = new Node(key,value);if (key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;}void InOrder(){_InOrder(_root);cout << endl;}Node* Find(const K& key)//不再是返回布尔值{Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return cur;//返回结点指针，方便以后修改value}}return nullptr;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{if (cur->_left == nullptr){//父为空，也就是说要删的是头结点if (parent == nullptr){_root = cur->_right;}else{//要判断父节点的左还是右指针指向cur的孩子if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;return true;}//cur的右孩子为空，把cur的左孩子给父else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{//判断父节点的左还是右指针指向cur孩子if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else//现在是cur的左右孩子都不为空{//第一步，找R（这里采用cur的右子树的最小结点/也就是最左结点）Node* p = cur;//这里如果初始给空，后面如果不进循环，会造成对空指针的解引用Node* r = cur->_right;while (r->_left){p = r;r = r->_left;}//第二步，进行交换(但不用真的把cur的值再去给r）cur->_key = r->_key;//第三步，删除R——很容易考虑不全面！！删除R又要把删除的问题考虑全面,但这里不能用递归，会找不到//在删除R时要把R的右孩子（只可能是右孩子）给给父，但是父的左还是右指针不确定if (p->_right == r){p->_right = r->_right;}else{p->_left = r->_right;}delete r;return true;}}}return false;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}Node* _root = nullptr;};
}

词典

然后我们再通过一段程序来测试一下key_value版本二叉搜索树的代码是否有误：

key_value::BSTree<string, string> dict;
dict.Insert("abandon", "抛弃");
dict.Insert("mania", "狂热");
dict.Insert("disc", "唱片");
dict.Insert("vain", "徒劳");string str;
while (cin >> str)
{auto ret = dict.Find(str);if (ret){cout << "->" << ret->_value << endl;}else{cout << "无此单词，请重新输入" << endl;}
}

这段程序里，我们通过key_value版本的二叉搜索树创建除了一个词典，然后while(cin>>str)里，cin>>str的返回值是istream类型的，可以通过operator bool转化成布尔类型（大致如此）。

总之，效果是我们可以输入多个（个数不确定）string类型的数据，然后程序在这棵树（这本词典）里查找，如果找到了，就把它的value值也就是中文名打印出来，如果找不到会提示，想要退出就按ctrl+z（相当于给流设置了一个错误标志）。

统计次数

然后我们再来一段程序，来用key_value版本的二叉搜索树进行次数的统计：

string arr[] = {"apple","melon","apple","melon","apple","apple","melon","banana","apple","banana"};
key_value::BSTree<string, int> countTree;for (const auto& str : arr)//通过使用引用，减少赋值消耗
{//先查找水果在不在搜索树//1.不在，说明水果第一次出现，则插入<水果，1>//2.在，则查找到的结点中水果对应的次数++auto ret = countTree.Find(str);if (ret == __nullptr){countTree.Insert(str, 1);}else{//修改valueret->_value++;}
}
countTree.InOrder();

搜索二叉树的拷贝问题

key_value::BSTree<string, int> copy = countTree;
copy.InOrder();

可以看到，copy和countTree里面的_root地址是一样的，说明是浅拷贝，而浅拷贝析构时会出问题（崩溃），我们需要的是深拷贝。

搜索树的析构有很多种写法，可以用循环去层序遍历地析构，但比较麻烦（析构一层的时候还得保存它的孩子）。

递归析构会简单一些。

public:~BSTree(){Destroy(_root);_root = nullptr;//别忘了}private:void Destroy(Node* root){if (root == nullptr)return;//后序析构Destroy(root->_left);Destroy(root->_right);delete root;}

这样写完析构之后，我们可以看看，在这样浅拷贝的情况下，析构时会崩溃：

要实现深拷贝，这里借助拷贝构造不好搞。

老老实实使用前序进行拷贝。

一个个插入不行，如果使用中序遍历一个个插入，形状就变了。

BSTree(const BSTree& t)
{_root = Copy(t._root);
}Node* Copy(Node* root)
{if (root == nullptr)return nullptr;//前序Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;
}

这时我们还有一个报错：没有合适的默认构造可以用。因为默认构造生成的前提是我们没有写任何的构造，而现在我们写了拷贝构造。

C++11为我们提供了关键字default：

BSTree() = default;

然后是赋值重载，这我们就可以考虑用现代写法了：

BSTree& operator=(BSTree tmp)
{swap(_root, tmp._root);return *this;
}

这里我们将要赋的值传值传参给tmp，传值传参会调用拷贝构造，tmp就是我们要的，我们将其root与 *this的root直接交换，在这个函数结束后tmp会自动销毁，把tmp现在的root也就是 *this原本的root带走。最后我们选择返回引用类型，减少消耗。