目录
前言：
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);
//找到了
else
return 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);
//冗余了，无法插入
else
return 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;
else
cout << "当前单词 " << 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;
else
cout << "当前单词 " << str << " 没有在词库中找到" << endl;
}
}
