递归
递归的函数都要带头结点，也就是说又要去调用子函数的方式来调用对应的递归函数。
查找：
bool FindR(Node* root, const K& key)//记得传头结点 { if (root == nullptr) return false; if (root->_key < key) { return FindR(root->right, key); } else if (root->_key > key) { return FindR(root->left, key); } else return true; }
递归这里有些地方很巧妙：
插入：
bool InsertR(Node*& root, const K& key)//这里的root用了引用 { if (_root == nullptr) { _root = new Node(key); return true; } if (_root->_key < key) InsertR(_root->right, key); else if (_root->_key > key) InsertR(_root->left, key); else return false; }
为什么这里的头结点用了引用呢？是因为解决链接问题的：
假设这里插入了一个6，应该是在5的右孩子那里，当我们找到位置的时候，上一层传递的是5的右指针，用了引用就是5的右指针的别名，开辟空间之后直接让5的右指针就能指向这块空间。
删除：
bool EraseR(Node*& root, const K& key) { if (root == nullptr) return false; if (root->_key > key) return EraseR(root->left, key); else if (root->_key < key) return EraseR(root->right, key); else { Node* cur = root; if (root->right == nullptr)//只有左孩子 { root = root->left;//这里不仅仅找到的是key，也是父节点指向该节点的指针别名 } else if (root->left == nullptr)//只有右孩子 { root = root->right;//这里也不用担心删除的是根，直接就将_root指向了下一个结点 } else//有两个孩子，这里的引用root就不管用了，因为引用不能改指向，在这里往下找右树最小值是行不通的 { Node* parent = root->right;//去该节点的右子树查找最小值 while (parent->left) { parent = parent->left; } swap(parent->_key, root->_key);//交换两个值 return EraseR(root->right, key);//再次去找该节点最小值，也就是被交换的值，然后进行删除 } delete cur; return true; } return false; }
析构
void Destroy(Node* root) { if (root == nullptr) return; Destroy(root->left); Destroy(root->right); delete root; }
拷贝
拷贝函数不能去一个一个插入：
所以说，这里只要去前序遍历，然后遇到一个结点拷贝一个结点就可以了。
Node* Copy(Node* root) { if (root == nullptr) return nullptr; Node* cur = new Node(root->_key); cur->left = Copy(root->left); cur->right = Copy(root->right); return cur;//这里将新开辟的结点返回给上一层，让上一层的指针指向这里，就能连接起来 }
KV模型
KV模型前身还有一个K（key）模型，就是上面的搜索二叉树，比如说要检查一个英语单词写的对不对，就要创建一个词库（搜索二叉树）里面找。
KV（key/value）模型是我们去查找一个英语单词的汉译，不可能在庞大的库中一个一个寻找词汇，而是通过搜索二叉树的形式寻找，那么一个单词相对应一个汉译，这个模型叫做KV模型。
其实本质就是一个结点有两个值而已。
这里的查找就很有用了，举个例子，一个学生来图书馆借书，借了多少本书需要知道，这本书归还没有也需要知道，所以这里查找也顺便进行修改。
#include<iostream> #include<vector> #include<string> using namespace std; template<class K, class V> struct BSTNode//树结点 { BSTNode(const K& key, const V& value) :_key(key) ,_value(value) , left(nullptr) , right(nullptr) {} K _key; V _value; BSTNode<K, V>* left;//左子树 BSTNode<K, V>* right;//右子树 }; template<class K, class V> class BSTree//树 { typedef BSTNode<K, V> Node; public: BSTree() :_root(nullptr) {} ~BSTree() { Destroy(_root); _root = nullptr; } bool Insert(const K& key, const V& value)//插入数据 { if (_root == nullptr) { _root = new Node(key, value); return true; } Node* cur = _root; Node* parent = cur; 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->left = cur; else parent->right = cur; return true; } Node* Find(const K& key)//查找 { Node* cur = _root; if (cur == nullptr) { return nullptr; } 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)//删除数据 { if (_root == nullptr) { return false; } Node* cur = _root; Node* parent = cur; 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;//释放结点 } 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;//释放结点 } else//有两个孩子 { Node* minright = cur->right; parent = cur; while (minright->left)//找到右子树最小值 { parent = minright; minright = minright->left; } //赋值 cur->_key = minright->_key; //链接 if (parent->left == minright) parent->left = minright->right; else parent->right = minright->right; delete minright; } return true; } } } void _InOrder()//因为不想让外界访问道内部的_root，所以只能通过成员函数内部访问 { InOrder(_root); cout << endl; } bool _FindR(const K& key) { return FindR(_root, key); } private: void Destroy(Node* root) { if (root == nullptr) return; Destroy(root->left); Destroy(root->right); delete root; } void InOrder(Node* root)//中序遍历 { if (root == nullptr) { return; } InOrder(root->left); cout << root->_key << ' '; cout << root->_value << ' '; InOrder(root->right); } Node* _root;//树的根结点 }; void test() { BSTree<string, string> tree; tree.Insert("1", "one"); tree.Insert("2", "two"); tree.Insert("3", "three"); tree.Insert("4", "four"); tree.Insert("5", "five"); BSTNode<string, string>* ret;//储存返回查找到结点的值 string str; while (cin >> str) { ret = tree.Find(str); if (ret) cout << ret->_value << endl; else cout << "没有此结果" << endl; } }
