一、二叉搜索树的实现
1.struct TreeNode{}
1.
搜索树的结点的定义也比较简单，每个结点都有左右子树和自身存储的_key值，_key就是利用搜索树进行搜索时的数据。
template <class K> struct TreeNode { TreeNode(const K& val) :_key(val) , _left(nullptr) , _right(nullptr) {} K _key; TreeNode<K>* _left; TreeNode<K>* _right; };
2.迭代版本
2.1 Insert()插入结点（解决链接的问题）
1.
在插入结点时要保证，大于根节点的结点插入到右子树，小于的插入到左子树，这样才满足二叉搜索树的定义，当根节点为空的时候，我们要单独处理这种情况，new一个树结点，当前这个树节点就是根。
2.
在cur向下迭代寻找插入位置的过程中，只要遇到了nullptr，则当前cur所指向的结点即为要插入的结点位置，但如果你直接new一个结点将结点地址给到cur指针，这是一点用都没有的，因为你仅仅将结点地址给了一个局部变量，外面树的结点的链接关系并没有发生变化，插入结点必须让cur的父节点和cur进行链接，这才算在树里面插入了结点，所以我们需要一个parent指针，用于指向cur所指结点的父节点，等到cur到达插入位置时，我们让parent的左或右指针指向新new出来的也就是要插入的结点。
那到底是parent的左还是右呢？这个时候需要比较一下parent的key和插入结点val的大小，val大那就插入到parent的右指针，val小那就插入到parent的左指针。
3.
普通的二叉搜素树不允许树中有两个相同的值出现，所以如果插入的值和树中的值相同时，此时我们认为插入失败，返回false
bool Insert(const K& val) { if (_root == nullptr) { _root = new Node(val); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (val > cur->_key) { parent = cur; cur = cur->_right; } else if (val < cur->_key) { parent = cur; cur = cur->_left; } else return false; } // cur = new Node(val);//让局部指针cur指向新开辟结点有什么用？对搜索树一点影响都没有，你需要改变搜索树的链接关系。 if (val > parent->_key) parent->_right = new Node(val); else parent->_left = new Node(val); return true; }
2.2 Find()查找结点
1.
想要在二叉搜索树里面查找一个结点那简直太简单了，我们只要依次比较根节点和val的大小就可以，val大去右子树查找，val小去左子树查找，直到val和_key值相等时查找成功，返回true；如果cur都已经查找到nullptr了，那么说明这棵树中没有val值的结点，返回false；
能如此轻松查找到对应的结点，本质还是因为二叉搜索树结构的优势所在，他的结构天生就是为搜索海量的数据而生。
bool Find(const K& val) { Node* cur = _root; while (cur) { if (val > cur->_key) { cur = cur->_right; } else if (val < cur->_key) { cur = cur->_left; } else return true; } return false; }
2.3 Erase()删除结点
1.
如果我们要删除搜索树的结点时，如果细分可分为下面三种情况，但12两种情况在删除时其实可以算作一种，这样的结点删除的方法我们称之为托孤行为，指的是如果删除结点的左右孩子个数为0或1时，我们可以让其父结点指向删除结点的非空结点，也就是将删除结点的孩子托付给父节点，这样的结点我们直接删除即可。
2.
对于左右均不为空的结点删除时，我们采用交换法进行删除，即去根结点的右子树找最小结点或者去左子树找最大结点进行和根结点值的交换，只有这样替换后，排除被交换结点外，其余结点还能继续满足二叉搜索树，调用Erase()删除接口后，树依旧可以是二叉搜索树。
而交换之后，我们只需要删除被交换的结点就好了，此时还需要一个被交换结点的parent指针，让parent指向被交换结点的非空子节点，如果子结点均为空，则随便指向一个就好，我们通过if else语句就可以实现。
3.
上面所说的都是思路，下面来看看用代码究竟该如何实现，对于直接删除法，普通结点直接托孤即可，先判断普通结点是父亲的左还是右，判断之后让父亲的左或右指向普通结点的非空子节点即可。但对于根节点删除时，情况有些特殊，因为托孤的时候parent用nullptr初始化，若此时访问parent的左或右则会发生空指针访问，所以此时我们不再选择托孤，直接将根节点挪动到其非空子节点即可。
4.
对于交换法删除就比较麻烦了，我们要先去找cur的右子树的最小结点，然后将minRight和cur的值进行交换，最后直接删除minRight即可，直接删除肯定也是需要minParent的，但在定义minParent时也是有讲究的，如果用nullptr初始化minParent的话，上面这种情况不会发生问题，因为minParent会被迭代到一个不为空的结点位置，但如果是下面这种情况，minRight恰好是cur的右子树根，如果此时直接托孤，就会发生空指针的访问，所以在初始化minParent时，我们用cur来初始化。
在链接的时候，也需要分情况来看待，如果minRight恰好是cur的right，那么直接让minParent的右链接到minRight的右，也就是第二种情况。如果minRight不是cur的right，那么我们直接让minParent的左指向minRight的右即可，因为最左结点minRight的左一定为空，但右不一定为空，所以托孤时要让minParent的左指向minRight的右。也就是第一种情况。
bool Erase(const K& val) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (val > cur->_key) { parent = cur; cur = cur->_right; } else if (val < cur->_key) { parent = cur; cur = cur->_left; } else//找到要删除的结点了 { if (cur->_left == nullptr) { if (cur == _root)//删除结点是根节点 { _root = cur->_right; } else if (cur == parent->_left) parent->_left = cur->_right; else parent->_right = cur->_right; delete cur; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else if (cur == parent->_left) parent->_left = cur->_left; else parent->_right = cur->_left; delete cur; } else { Node* minParent = cur;//minParent如果是nullptr，则当cur->_right是最小结点时，会发生空指针访问 Node* minRight = cur->_right;//找右子树最小结点 或者 左子树最大结点 while (minRight->_left) { minParent = minRight; minRight = minRight->_left; } swap(cur->_key, minRight->_key); if (minRight == cur->_right) minParent->_right = minRight->_right;//右子树最小结点的左节点一定为空，让父节点链接其右结点即可。 else minParent->_left = minRight->_right; delete minRight; } return true; } } return false; }
3.递归版本
3.1 InOrder()中序遍历
1.
递归版本的中序遍历那都是老熟人了，只要先去遍历左树，到nullptr的时候返回，然后输出root的值，最后再去遍历一下右树即可。也就是暴力法递归，将整棵树的每一个结点按照中序遍历一遍。
2.
但这里有一个关于类和对象知识的小技巧，在遍历的时候我们肯定需要根节点_root，但如果直接暴露根节点到class BSTree{}外面，就破坏了类的封装性，因为外面想要传参_root，就必须提供公有的访问根节点的函数，类封装自然就被破坏了，所以我们将_InOrder搞成私有，外面的公有InOrder调用私有_InOrder，在公有函数中完成根节点的传参。
很多需要传根节点的公有函数都是这样做的，即把核心接口封装成私有，在公有接口中传根节点_root
void InOrder() { return _InOrder(_root); } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } Node* _root = nullptr;
3.2 Insert()插入结点（解决链接的问题）
1.
无论是递归插入结点还是非递归，我们都需要处理结点和父节点链接的问题，所以有一个比较好的思路就是，在递归查找插入位置的过程中，我们并不是找到那个位置，让父节点去链接那个位置，而是判断遍历到的结点的左或右是否为空，如果为空并且满足插入结点的位置，那么直接链接即可。这个思路不再像上面思路中让parent链接插入结点位置，而是先不着急处理链接，先判断root的右或左是否为插入结点的位置，如果是那就插入，如果不是，那就继续递归向下寻找。
但这种思路有一个问题无法处理，那就是空树的情况，有人说，空树还不好处理吗？你直接new一个结点，将这个结点的地址给到形参root不就可以了吗？道理确实是这样的，但无法做到，因为root是一个形参变量，你将new出来的结点的地址给一个形参变量，函数外面的_root成员变量还是无法改变的，所以如果形参是普通的指针，则无法处理空树的情况。（这个道理其实就是上面判断root的左或右的问题，因为我们无法直接处理形参root当前指向的结点，因为root是形参，外面搜索树的实际结点无法被操纵，但我们可以处理root的左或者右，这个左或者右指向的就是外面搜索树的结点的左或者右）
2.
所以上面的思路再好，再清奇，也无法处理空树的情况，本质还是因为形参变量无法处理当前结点，树外面的当前结点始终不受影响。
但如果我们不用普通形参呢？我们用指针的引用呢？这就非常的牛了，我们可以直接操纵函数外面的二叉搜索树本身，这个时候递归插入结点就非常非常简单了，只要找到插入的位置，也就是root=nullptr的时候，我们直接new结点，将结点地址给到root，这样就完成结点插入了，因为此时是引用，无论改变哪个结点的地址，外面的搜索树都会被影响，如果root没到nullptr，那就递归向下查找即可，注意此时也不是暴力递归查找，还是通过key和val的大小来递归向下查找，这样的效率更高。
bool InsertR(const K& val) { return _InsertR(_root, val); } private: bool _InsertR(Node*& root, const K& val)//你如果不用引用，那这里就是临时的形参，栈帧外面什么都影响不了 { if (root == nullptr) { root = new Node(val); return true; } if (val > root->_key) return _InsertR(root->_right, val); else if (val < root->_key) return _InsertR(root->_left, val); else return false; } /*bool _InsertR(Node* root, const K& val)//一个比较不错的思路，但是对于空树不太实用 { if (root == nullptr) { } if (root->_key == val) return false; if (val > root->_key) { if (root->_right == nullptr) { root->_right = new Node(val); return true; } else { _InsertR(root->_right, val); } } else { if (root->_left == nullptr) { root->_left = new Node(val); return true; } else { _InsertR(root->_left, val); } } }*/
3.3 Find()查找结点
1.
递归查找子节点那也是非常简单的，和插入结点的递归道理相同，我们不采用暴力递归的方式，而是用搜索树的结构特征进行查找，val大去右面递归查找，val小去左面递归查找，直到key和val相等的时候我们返回true表示查找成功，如果查找到nullptr，则表示查找失败，返回false即可
bool FindR(const K& val) { return _FindR(_root, val); } private: bool _FindR(Node* root, const K& val) { if (root == nullptr) return false; if (root->_key == val) return true; else if (root->_key < val) return _FindR(root->_right, val); else return _FindR(root->_left, val); //return _FindR(root->_left, val) || _FindR(root->_right, val);//暴力查找就完事了 }
3.4 Erase()删除结点（交换后整体不是搜索树，但结点的右子树是搜索树呀！）
1.
递归删除结点的实现，我们采用引用结构体指针作为形参，引用总是能带来很多的好处，直接操纵搜索树的结点何乐而不为呢？
思路不变，利用搜索树的结构先进行删除结点的递归查找，等递归找到删除结点后，还是老套路需要分情况进行删除，对于直接删除的情况，这回只需要让他的非空子节点地址覆盖掉当前删除结点地址就够了，这样就完成了托孤行为，这正是引用带来的好处。但覆盖之后不要忘记释放删除结点的空间，所以我们用一个临时指针记录一下删除结点的地址，在非空子节点地址覆盖掉删除结点地址之后，我们在delete临时指针指向的空间。
利用引用对于根节点的删除情况也可以适用，因为我们不再需要parent，直接用非空子节点覆盖删除结点的地址就可以，所以即使对于删除根节点的情况，引用的方式依旧可以适用。
2.
而对于交换法删除的情景来说，我们可以利用递归将问题进行转换，虽然交换之后整体不再满足搜索树，但删除结点的右子树依旧满足搜索树，所以我们只要递归删除其右子树就可以，将交换法删除的问题通过递归右子树再次转换为直接删除的问题，完美进行代码复用。
bool EraseR(const K& val) { return _EraseR(_root, val); } private: bool _EraseR(Node*& root, const K& val) { if (root == nullptr) return false; if (val > root->_key) { return _EraseR(root->_right, val); } else if (val < root->_key) { return _EraseR(root->_left, val); } else { if (root->_left == nullptr)//用引用删除单链的根节点时，不用去找父亲，直接修改当前结点就可以 { Node* tmp = root; root = root->_right; delete tmp; } else if (root->_right == nullptr) { Node* tmp = root; root = root->_left; delete tmp; } else { //这里的解决方法有两种，一种是直接cv上面的解决方式，一种是通过递归将问题转换为直接删除。 Node* minRight = root->_right;//找右子树最小结点 或者 左子树最大结点 while (minRight->_left) { minRight = minRight->_left; } swap(root->_key, minRight->_key); _EraseR(root->_right, val);//虽然整体不是搜索树了，但是root的右子树在交换之后还是搜索树，可以用直接删除。 } return true; } }
4.二叉搜索树的成员函数
4.1 构造函数（拷贝构造被编译器认为是构造函数）
1.
搜索树的构造函数实际并不用写，利用C++11提供的缺省值和编译器默认生成的构造函数就可以完成搜索树的初始化，但如果我们写了树的拷贝构造函数，那就不得不写出构造函数了，因为拷贝构造也是构造，但拷贝构造需要传参，我们在初始化树的时候不会提供任何参数，所以此时就会报错没有合适的默认构造可用。
因为在我们写了拷贝构造之后，编译器不会生成默认的拷贝构造了，所以这个时候就必须我们自己来写无参的默认构造。
2.
如果要写也非常简单，只要将指向根节点的指针初始化为nullptr就好了，在Insert()插入结点构造搜索树的时候我们会处理根为nullptr的情况。
template <class K> class BSTree { typedef TreeNode<K> Node; public: BSTree() :_root(nullptr) {} //BSTree(const BSTree<K>& t)//树的拷贝构造，类型是自定义类型 //{ //可以层序遍历，然后将遍历到的数Insert构建一棵新的树。 //_root = Copy(t._root); //} private: Node* _root = nullptr; };
4.2 析构函数
1.
搜索树的析构函数我们可以采用后序遍历的方式将结点进行释放，因为一旦析构根节点，他的左右孩子我们就找不到了，所以按照左右根的顺序来释放结点，遇到空结点就返回，因为空结点指针指向的是空，并未分配堆的有效空间，所以无须操作空结点指针，等待栈帧销毁时自动清理这些局部变量即可。
~BSTree() { Destroy(_root); _root = nullptr; } void Destroy(Node* root) { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; }
4.3 拷贝构造
1.
写完拷贝构造再写赋值重载就简单的多了，我们利用形参的临时拷贝，然后进行根节点的交换，即可完成搜索树的赋值重载，由于形参在离开函数栈帧时会被自动销毁，对于自定义类型会自动调用析构函数，所以不用担心内存泄露的发生。
BSTree<K>& operator=(const BSTree<K> t) { swap(_root, t._root); // 交换之后，不用担心内存泄漏，因为形参对象离开函数栈帧，会自动调用其析构函数，析构的是原来this指向的旧对象 //拷贝构造出来的新内容已经交换到this手上了，不用担心内存泄漏。 return *this; }
二、K模型和KV模型
1.key模型
1.
K模型即为二叉搜索树中只存储一个_key值，K模型中只有key作为关键码，关键码即为需要搜索的值。
2.
K模型的适用场景之一便是考虑在不在的问题，比如判断某个作家写的书中的单词是否合法，我们可以将词库中的单词作为_key值存储到搜索树里面，然后去搜索树中进行查找，判断当前的单词是否存在于搜索树中，单词作为string当然是可以比较大小的，所以我们只要定义出BSTree< string > T的对象即可，搜索的效率在logN到N之间。
另一种较为常见的场景是学生出入系统，车库出入系统等，都需要判断对应的对象是否存在，例如不是本校的学生不能刷卡进入校园，不是车库中的车，杆子不会抬起放入，这些都是判断在不在的情形，这样的情景我们称之为K模型。
2.key value模型
1.
另一种更为常见的模型是key value模型，即通过key关键码去查找与之对应的值value，即<Key, Value>的键值对，比如英汉互译，统计所给单词出现的次数，统计水果出现的次数，他们的键值对分别是<string, string>，<string, int>，<string, int>。
2.
下面便是KV模型下搜索树结点的定义，在比较和构建搜索树时，我们都是用关键码_key来进行比较，找到key后，通过key对应的结点地址当然可以轻松拿到对应的value值。
将K模型搜索树改造成KV模型，代码也是非常简单的，只需要在树结点的结构体里面增加一个变量即可， 树的模板中多增加一个value的类型V，其余部分都不用变，因为比较的逻辑都没有变，仅仅只是在结点里面多加了一个value值而已。
3.
例如英汉互译这样的场景，我们简单的在树中插入几个结点，然后判断输入的str是否在树里面，如果Find()查找到的话，那就通过Find()的返回结点地址输出结点对应的value值即可。
确定水果出现的次数也比较简单，如果水果存在于二叉搜索树，那就将水果的value值（value代表出现次数）+1，如果不存在那就插入结点，结点的value初始值设定为1即可。
namespace KV { template <class K, class V> struct TreeNode { TreeNode(const K& key, const V&value)//每一个结点里面既有_key又有_value :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} K _key; V _value; TreeNode<K,V>* _left; TreeNode<K,V>* _right; }; //BSTree<string, vector<string>> bookInfo template <class K, class V> class BSTree { typedef TreeNode<K, V> Node; 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->_right; } else if (key < cur->_key) { parent = cur; cur = cur->_left; } else return false; } // cur = new Node(val);//让局部指针cur指向新开辟结点有什么用？对搜索树一点影响都没有，你需要改变搜索树的链接关系。 if (key > parent->_key) parent->_right = new Node(key, value); else parent->_left = new Node(key, value); return true; } Node* Find(const K& key)//返回树的结点，结点里面有key和value { Node* cur = _root; while (cur) { if (key > cur->_key) { cur = cur->_right; } else if (key < cur->_key) { cur = cur->_left; } else return cur; } return nullptr; } void InOrder() { _InOrder(_root); } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << ":" << root->_value << endl; _InOrder(root->_right); } Node* _root = nullptr; }; }
void TestBSTree4()//测试KV模型 { // 将词库中的单词都放进这棵搜索树中，单词string之间是可以比较大小的，只要单词合法则一定能在搜索树中找到对应的string。 // Key模型，判断在不在？ // 场景：检查单词拼写是否正确/车库出入系统/…… //K::BSTree<string> dict; //Key/Value的搜索模型，通过Key查找或修改Value // 场景1：经典的英汉互译 KV::BSTree<string, string> dict;//value还可以是一颗搜索树，但如果数据量特别小的话，没必要用搜索树存，用vector就够了 dict.Insert("apple", "苹果"); dict.Insert("banana", "香蕉"); dict.Insert("pear", "鸭梨"); dict.Insert("watermelon", "西瓜"); string str; while (cin>>str) { //KV::TreeNode<string, string>* ret = dict.Find(str); auto ret = dict.Find(str); if (ret) cout << ret->_value << endl; else cout << "无此单词" << endl; } // 场景2：统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" ,"草莓"}; //统计次数这样的场景非常适合二叉搜索树或者哈希的方式来解决。尤其是你想通过一个值去找另一个值都可以用key value模型解决 KV::BSTree<string, int> countT; for (auto e : arr) { auto* cur = countT.Find(e);//没有找到返回nullptr if (cur == nullptr) countT.Insert(e, 1); else cur->_value++; } countT.InOrder(); }
