前言

前面我们对二叉搜索树进行了讲解，本节内容我们将对该树的应用进行讲解，对二叉搜素树进行进一步的了解。

 key搜索场景

key/value搜索场景

代码展示

代码其实跟二叉搜索树没有相差太多，节点的成员中多了一个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进行讲解。

最后感谢大家的支持！！!