目录
前言：
1.二叉搜索树
1.1二叉搜索树的定义
1.2二叉搜索树的特点
2.二叉搜索树的实现
2.1框架
2.2查找
2.3插入
2.4删除
1.右子树为空
2.左子树为空
3.左右都不为空
3.递归版本
3.1前序遍历
3.2中序遍历
3.3后续遍历
3.4查找（递归版）
3.5插入（递归版）
3.6删除（递归版）
4.内部函数补充
4.1销毁
4.2拷贝构造和赋值重载
5.应用场景
5.1单key场景
5.2key-value场景
6 面试经典题
前言：
1.二叉搜索树
1.1二叉搜索树的定义
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
对于搜索二叉树，对数据进行查找时，理想情况下时间复杂度为logN(二分查找），搜索查找还是很快的。
1.2二叉搜索树的特点
对于搜索二叉树，对该树进行中序遍历，得到的就是升序结果。比如一颗二叉搜索树如下图所示，对其进行中序遍历得到的结果为【1，3,4,6,7,8,10,13,14】
2.二叉搜索树的实现
我们想对一颗二叉搜索树进行增删查改，我们就要种一棵树，这棵树上的果子就是节点。
2.1框架
利用学过的类和对象、泛型编程，对搜索二叉树的框架进行搭建
namespace Cmx //创建一个属于自己的域
{template <class T>struct BSTreeNode{BSTreeNode<T>* _left;BSTreeNode<T>* _right;T _val;BSTreeNode(const T&val):_left(nullptr),_right(nullptr),_val(val){}};template <class T>class BSTree{typedef BSTreeNode<T> Node;public：//需要后续实现的函数 增删改查，前后中遍历，递归版本private:Node* _root;};
} 二叉搜索树的节点类需要写出构造函数，因为后面创建新节点时会用到；二叉搜索树的根可以给个缺省值 nullptr，确保后续判断不会出错.
2.2查找
因为是对确定的值进行查找，所以需要有比较的过程：
bool find(const T& key){Node* cur = _root;while (cur){if (cur->_val < key){cur = cur->_right;}else if (cur->_val > key){cur = cur->_left;}else{return true;}}return false;}当查找的值存在时
当查找的值不存在时
2.3插入
插入的具体过程如下：（非重复版）
bool Insert(const T& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_val < key){parent = cur;cur = cur->_right;}else if (cur->_val > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_val < key){parent->_right = cur;}else{parent->_left = cur;}return true;}2.4删除
删除需要注意的地方很多，也是面试常考的地方，删除逻辑：
1.右子树为空
右子树为空时，只 需要将其左子树与父节点进行判断链接即可，无论其左子树是否为空，都可以链接，链接完成后，删除目标节点
2.左子树为空
操作同上，转换托孤方向。
3.左右都不为空
当左右都不为空时，就有点麻烦了，需要找到一个合适的值（即 > 左子树所有节点的值，又 < 右子树所有节点的值），确保符合二叉搜索树的基本特点
符合条件的值有：左子树的最右节点（左子树中最大的）、右子树的最左节点（右子树中最小的），将这两个值中的任意一个覆盖待删除节点的值，都能确保符合要求
这里找的是待删除节点 左子树的最右节点
为什么找 左子树的最右节点或右子树的最左节点的值覆盖 可以符合要求？
因为左子树的最右节点是左子树中最大的值，> 左子树所有节点（除了自己），< 右子树所有节点
右子树的最左节点也是如此，都能符合要求
通俗理解：需要找待删除节点的值的兄弟来镇住这个位置，而它的兄弟自然就是 左子树最右节bool Erase(const T& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_val < key){parent = cur;cur = cur->_right;}else if (cur->_val > key){parent = cur;cur = cur->_left;}else{//找到该值//1.该节点左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left = cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}}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;}}}else //左右都不为空{Node* parent = cur;Node* leftMax = parent->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_val, leftMax->_val);if (parent->_left = leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}点 和 右子树最左节点，配合中序遍历结果可以确认
注意：
涉及更改链接关系的操作，都需要保存父节点的信息
右子树为空、左子树为空时，包含了删除 根节点 的情况，此时 parent 为空，不必更改父节点链接关系，更新根节点信息后，删除目标节点即可，因此需要对这种情况特殊处理
右子树、左子树都为空的节点，包含于 右子树为空 的情况中，自然会处理到
左右子树都不为空的场景中，parent 要初始化为 cur，避免后面的野指针问题
3.递归版本
我将二叉搜索树树的前序后序中序遍历放在这里，因为对于不同序的访问，我是利用递归实现的。
包括之前的插入，删除，查找我都要用递归实现。
3.1前序遍历
前序：根 -> 左 -> 右
在递归遍历时，先打印当前节点值（根），再递归左子树（左），最后递归右子树（右）
因为这里是一个被封装的类，所以面临着一个尴尬的问题：二叉搜索树的根是私有，外部无法直接获取
解决方案：
公有化（不安全，也不推荐）
通过函数获取（安全，但用着很别扭）
将这种需要用到根的函数再封装（完美解决方案）
这里主要来说说方案3：类中的函数可以直接通过 this 指针访问成员变量，但外部可没有 this 指针，于是可以先写一个外壳（不需要传参的函数），在这个外壳函数中调用真正的函数即可，因为这个外壳函数在类中，所以此时可以通过 this 指针访问根 _root
具体操作如下：
//===遍历===void PrevOrder(){_PrevOrder(_root);}protected:void _PrevOrder(const Node* root){if (root == nullptr)return;//前序：根左右cout << root->_key << " ";_PrevOrder(root->_left);_PrevOrder(root->_right);}
3.2中序遍历
中序：左 -> 根 -> 右
在递归遍历时，先递归左子树（左），再打印当前节点值（根），最后递归右子树（右）
中序遍历也需要用到根，同样对其进行再封装
void InOrder(){_InOrder(_root);}protected:void _InOrder(const Node* root){if (root == nullptr)return;//中序：左根右_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
3.3后续遍历
后序：左 -> 右-> 根
在递归遍历时，先递归左子树（左），再递归右子树（右），最后打印当前节点值（根）
一样需要进行再封装
void PostOrder(){_PostOrder(_root);}
protected:void _PostOrder(const Node* root){if (root == nullptr)return;//后序：左右根_PrevOrder(root->_left);_PrevOrder(root->_right);cout << root->_key << " ";}
3.4查找（递归版）
递归查找逻辑：如果当前根的值 < 目标值，递归至右树查找；如果当前根的值 > 目标值，递归至左树查找；否则就是找到了，返回 true
因为此时也用到了根 _root，所以也需要进行再封装
//===递归实现===bool FindR(const K& key) const{return _FindR(_root, key);}
protected://递归实现bool _FindR(Node* root, const K& key) const{//递归至叶子节点也没找到if (root == nullptr)return false;//递归至右树if (root->_key < key)return _FindR(root->_right, key);//递归至左树else if (root->_key > key)return _FindR(root->_left, key);//找到了elsereturn true;}
3.5插入（递归版）
基于递归查找的逻辑，实现递归插入
此时用到了一个很nb的东西：引用，实际插入时，甚至都不需要改链接关系，直接赋值即可
bool InsertR(const K& key){return _InsertR(_root, key);}
protected:bool _InsertR(Node*& root, const K& key){if (root == nullptr){//得益于引用，可以对不同栈帧中的值进行修改root = new Node(key);return true;}//递归至右树if (root->_key < key)return _InsertR(root->_right, key);//递归至左树else if (root->_key > key)return _InsertR(root->_left, key);//冗余了，无法插入elsereturn false;}
因为此时的参数是 节点指针的引用，所以在 保持原有链接属性的前提下，改变当前节点，即插入节点
3.6删除（递归版）
递归删除时也使用了引用，这样可以做到 在不同的栈帧中，删除同一个节点，而非临时变量
同时递归删除还用到了一种思想：转换问题的量级
比如原本删除的是根节点，但根节点之下还有很多节点，直接删除势必会造成大量的链接调整，于是可以找到 “保姆”（左子树的最右节点或右子树的最左节点），将 “保姆” 的值与待删除节点的值交换，此时递归至保姆所在的子树进行删除
因为保姆必然只带一个子树或没有子树，所以删除起来很简单
bool EraseR(const K& key){return _EraseR(_root, key);}
protected:bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key)return _EraseR(root->_right, key);else if(root->_key > key)return _EraseR(root->_left, key);else{Node* del = root; //需要保存一下待删除的节点信息//如果右树为空，则直接将左树覆盖上来if (root->_right == nullptr)root = root->_left;//如果左树为空，则直接将右树覆盖上来else if (root->_left == nullptr)root = root->_right;else{//递归为小问题去处理Node* maxLeft = root->_left;while (maxLeft->_right)maxLeft = maxLeft->_right;//注意：需要交换std::swap(root->_key, maxLeft->_key);//注意：当前找的是左子树的最右节点，所以递归从左子树开始return _EraseR(root->_left, key);}delete del; //释放节点return true;}}
注意：
再次递归时，需要传递 root->_left 而非 maxLeft，因为此时的 maxLeft 是临时变量，而函数参数为引用
传递 root->_left 的原因：找的保姆出自左子树的最右节点，所以要求左子树中找，不能只传递 root，这样会导致查找失败 -> 删除失败
要使用 swap 交换 maxLeft->_key 与 key，然后递归时，找的就是 key；如果不使用交换而去使用赋值，那么递归查找的仍是 maxLeft->_key，类似于迭代删除时，将多余的节点删除
4.内部函数补充
4.1销毁
创建节点时，使用了 new 申请堆空间，根据动态内存管理原则，需要使用 delete 释放申请的堆空间，但二叉搜索树是一棵树，不能直接释放，需要 递归式的遍历每一个节点，挨个释放
释放思路：后序遍历思想，先将左右子树递归完后，才释放节点
~BSTree(){destory(_root);}
protected://细节问题void destory(Node*& root){if (root == nullptr)return;//后序销毁destory(root->_left);destory(root->_right);delete root;root = nullptr;}
4.2拷贝构造和赋值重载
BSTree(const BSTree<T>& t){_root = (t._root);}BSTree<T>& operator=(BSTree<T> t){swap(_root, t._root);return *this;}5.应用场景
5.1单key场景
key 模型的应用场景：在不在
- 门禁系统
- 车库系统
- 检查文章中单词拼写是否正确
这些都是可以利用 key 模型解决，其实我们上面写的就是 key 模型，下面通过一段演示代码，展示 key 模型实现 单词查找系统
void BSTreeWordFind()
{vector<string> word = { "apple", "banana", "milk", "harmony" };Yohifo::BSTree<string> table;for (auto e : word)table.Insert(e);string str;while (cin >> str){if (table.Find(str))cout << "当前单词 " << str << " 存在于词库中" << endl;elsecout << "当前单词 " << str << " 没有在词库中找到" << endl;}
}
5.2key-value场景
key / value 的模型：应用搜索场景
中英文互译字典
电话号码查询快递信息
电话号码 + 验证码
key / value 模型比 key 模型 多一个 value，即 kv 模型除了可以用来查找外，还可以再带一个值用于统计，这其实就是哈希的思想（建立映射关系）
kv 模型需要将代码改一下，新增一个模板参数 class value，插入时新增一个参数，同时操作也会有轻微改动，查找时返回的不再是 bool ，而是指向当前节点的指针，其他操作可以不用变
注：即使是 kv 模型，也只是将 key 作为查找、插入、删除的依据，基本逻辑与 value 没有任何关系，value 仅仅起到一个存储额外值的作用
将代码进行小改动，具体可查看源码
实现一个简单的中英词典
void BSTreeDictionary()
{vector<pair<string, string>> word = { make_pair("apple", "苹果"), make_pair("banana", "香蕉"), make_pair("milk", "牛奶"), make_pair("harmony", "鸿蒙")};Yohifo::BSTreeKV<string, string> table;for (auto e : word)table.InsertR(e.first, e.second);string str;while (cin >> str){Yohifo::BSTreeNodeKV<string,string>* ret = table.FindR(str);if (ret)cout << "当前单词 " << str << " 存在于词库中，翻译为 " << ret->_value << endl;elsecout << "当前单词 " << str << " 没有在词库中找到" << endl;}
}
