目录
⼆叉搜索树的概念
⼆叉搜索树的性能分析
二叉搜索树的实现
结点类
赋值运算符重载函数
插入函数
非递归实现
递归实现
查找函数
非递归实现
递归实现
⼆叉搜索树的删除（重点）
二叉搜索树的应用
K模型
KV模型
⼆叉搜索树的概念
⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:
• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
• 它的左右⼦树也分别为⼆叉搜索树
• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续我们学习map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等 值，multimap/multiset⽀持插⼊相等值。
⼆叉搜索树的性能分析
最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为： logN
最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为： N
所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为： O(N)
那么这样的效率显然是⽆法满⾜我们需求的，我们后续博客中需要继续讲解⼆叉搜索树的变形，平衡⼆ 叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。 另外需要说明的是，⼆分查找也可以实现 O(logN) 2 级别的查找效率，但是⼆分查找有两⼤缺陷：
1. 需要存储在⽀持下标随机访问的结构中，并且有序。
2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数 据。 比特就业课 这⾥也就体现出了平衡⼆叉搜索树的价值。
二叉搜索树的实现
结点类
要实现二叉搜索树，我们首先需要实现一个结点类：
- 结点类当中包含三个成员变量：结点值、左指针、右指针。
- 结点类当中只需实现一个构造函数即可，用于构造指定结点值的结点。
//结点类
template <class K>
struct BSTreeNode
{K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;BSTreeNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};各类函数接口
//二叉搜索树
template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://构造函数BSTree();//拷贝构造函数BSTree(const BSTree<K>& t);//赋值运算符重载函数BSTree<K>& operator=(BSTree<K> t);//析构函数~BSTree();//插入函数bool Insert(const K& key);//删除函数bool Erase(const K& key);//查找函数Node* Find(const K& key);//中序遍历void InOrder();
private:Node* _root; //指向二叉搜索树的根结点
};
为了在实现其他接口的过程中方便随时检查，最好实现一个二叉搜索树的中序遍历接口，当我们对二叉搜索树进行一次操作后，可以调用中序遍历接口对二叉搜索树进行遍历，若二叉搜索树进行操作后的遍历结果仍为升序，则可以初步判断所实现的接口是正确。
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);}构造函数
//构造函数
BSTree():_root(nullptr)
{}拷贝构造函数
拷贝构造函数也并不难，拷贝一棵和所给二叉搜索树相同的树即可。注意这里是深拷贝，二叉树是天然的递归结构，所以直接递归拷贝就行。
//拷贝树
Node* _Copy(Node* root)
{if (root == nullptr) //空树直接返回return nullptr;Node* copyNode = new Node(root->_key); //拷贝根结点copyNode->_left = _Copy(root->_left); //拷贝左子树copyNode->_right = _Copy(root->_right); //拷贝右子树return copyNode; //返回拷贝的树
}
//拷贝构造函数
BSTree(const BSTree<K>& t)
{_root = _Copy(t._root); //拷贝t对象的二叉搜索树
}
赋值运算符重载函数
对于赋值运算符重载函数，下面将提供两种实现方法：
1.传统写法
先将当前二叉搜索树中的结点释放，然后完成所给二叉搜索树的拷贝即可。
//传统写法
const BSTree<K>& operator=(const BSTree<K>& t)
{if (this != &t) //防止自己给自己赋值{_Destory(_root); //先将当前的二叉搜索树中的结点释放_root = _Copy(t._root); //拷贝t对象的二叉搜索树}return *this; //支持连续赋值
}
2.现代写法
老思路，依然是交换，写法非常简洁，函数在接收右值时并没有使用引用进行接收，因为这样可以间接调用BSTree的拷贝构造函数完成拷贝构造。我们只需将这个拷贝构造出来的对象的二叉搜索树与this对象的二叉搜索树进行交换，就相当于完成了赋值操作，而拷贝构造出来的对象t会在该赋值运算符重载函数调用结束时自动析构。
析构函数
析构函数完成对象中二叉搜索树结点的释放，注意释放时采用后序释放，当二叉搜索树中的结点被释放完后，将对象当中指向二叉搜索树的指针及时置空即可。
//释放树中的结点
void _Destory(Node* root)
{if (root == nullptr){return;}_Destory(root->_left);_Destory(root->_right);delete root;}//析构函数
~BSTree()
{_Destory(_root);_root = nullptr;
}插入函数
根据二叉搜索树的性质，其插入操作非常简单：
如果是空树，则直接将插入结点作为二叉搜索树的根结点。
如果不是空树，则按照二叉搜索树的性质进行结点的插入。
若不是空树，插入结点的具体操作如下：
若待插入结点的值小于根结点的值，则需要将结点插入到左子树当中。
若待插入结点的值大于根结点的值，则需要将结点插入到右子树当中。
若待插入结点的值等于根结点的值，则插入结点失败。
如此进行下去，直到找到与待插入结点的值相同的结点判定为插入失败，或者最终插入到某叶子结点的左右子树当中
这里我们也给出两种解法
非递归实现
使用非递归方式实现二叉搜索树的插入函数时，我们需要定义一个parent指针，该指针用于标记待插入结点的父结点。
这样一来，当我们找到待插入结点的插入位置时，才能很好的将待插入结点与其父结点连接起来。
bool Insert(const K& key)
{// 如果根节点为空，则创建一个新节点作为根节点if (_root == nullptr){_root = new Node(key);return true;}// 用于遍历树的指针，初始指向根节点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{return false;}}// 创建一个新节点存储要插入的键cur = new Node(key);// 根据父节点的键和要插入的键的大小关系，将新节点连接到父节点的左子树或右子树if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;
}递归实现
递归实现二叉搜索树的插入操作也是很简单的，但是要特别注意的一点就是，递归插入函数的子函数接收参数root时，必须采用引用接收，因为只有这样我们才能将二叉树当中的各个结点连接起来。
// 辅助函数，用于递归插入节点
Node* InsertNode(Node* root, const K& key)
{// 如果当前节点为空，则创建新节点if (root == nullptr){return new Node(key);}// 如果键小于当前节点的键，递归插入到左子树if (key < root->_key){root->_left = InsertNode(root->_left, key);}// 如果键大于当前节点的键，递归插入到右子树else if (key > root->_key){root->_right = InsertNode(root->_right, key);}// 如果键等于当前节点的键，不进行插入操作并返回 nullptrelse{return nullptr;}return root;
}
// 插入函数，调用辅助函数进行插入操作
bool Insert(const K& key)
{Node* result = InsertNode(_root, key);if (result == nullptr){return false;}_root = result;return true;
}查找函数
1. 从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。
2. 最多查找⾼度次，⾛到到空，还没找到，这个值不存在。
3. 如果不⽀持插⼊相等的值，找到x即可返回
4. 如果⽀持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。如下图，查找3，要找到1的右孩⼦的那个3返回
非递归实现
二叉搜索树查找函数的非递归实现如下：
//查找函数
Node* Find(const K& key)
{Node* cur = _root;while (cur){if (key < cur->_key) //key值小于该结点的值{cur = cur->_left; //在该结点的左子树当中查找}else if (key > cur->_key) //key值大于该结点的值{cur = cur->_right; //在该结点的右子树当中查找}else //找到了值为key的结点{return cur; //查找成功，返回结点地址}}return nullptr; //树为空或查找失败，返回nullptr
}
递归实现
二叉搜索树查找函数的递归实现如下：
//递归查找函数的子函数
Node* _FindR(Node* root, const K& key)
{if (root == nullptr) //树为空return nullptr; //查找失败，返回nullptrif (key < root->_key) //key值小于根结点的值{return _FindR(root->_left, key); //在根结点的左子树当中查找}else if (key > root->_key) //key值大于根结点的值{return _FindR(root->_right, key); //在根结点的右子树当中查找}else //key值等于根结点的值{return root; //查找成功，返回根结点地址}
}
//递归查找函数
Node* FindR(const K& key)
{return _FindR(_root, key); //在_root当中查找值为key的结点
}⼆叉搜索树的删除（重点）
删除是在二叉搜索树中是一个比较复杂的操作，
⾸先查找元素是否在⼆叉搜索树中，如果不存在，则返回false。 如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）
1. 要删除结点N左右孩⼦均为空
2. 要删除的结点N左孩⼦位空，右孩⼦结点不为空
3. 要删除的结点N右孩⼦位空，左孩⼦结点不为空
4. 要删除的结点N左右孩⼦结点均不为空
对应以上四种情况的解决⽅案：
1. 把N结点的⽗亲对应孩⼦指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）
2. 把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点
3. 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点
4. ⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤替换法删除。找N左⼦树的值最⼤结点R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结 点，R结点符合情况2或情况3，可以直接删除。
这里较为复杂的就是要删除的结点左右均不为空，就是中间结点也有可能是根节点，这里需要特别注意。这里采取的是替换法，将minRight的key给要删除结点的key,这里可以直接覆盖，后面再把minRight释放掉即可。
bool Erase(const K& key)
{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;}else{//删除if (cur->_left == nullptr)//删除结点左为空，处理右边即可{//if (parent == nullptr)if (cur == _root)//考虑parent==nullptr{_root = cur->_right;}else{// 父亲指向我的右if (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//删除结点右为空，处理左边{if (cur == _root)//{_root = cur->_left;}else{// 父亲指向我的左if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;}else//删除左右均不为空，需要找一个结点来代替，这样才不破环结构{// 找右子树最小节点(最左)替代我的位置Node* minRightParent = cur;Node* minRight = cur->_right;while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (minRightParent->_left == minRight){minRightParent->_left = minRight->_right;}else//当你要删除的结点的右孩子没有左节点的情况{minRightParent->_right = minRight->_right;}delete minRight;}return true;}}return false;
}二叉搜索树的应用
K模型
K模型，即只有key作为关键码，结构中只需存储key即可，关键码即为需要搜索到的值。
比如：给定一个单词，判断该单词是否拼写正确。具体方式如下：
以单词集合中的每个单词作为key，构建一棵二叉搜索树。
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
KV模型
KV模型，对于每一个关键码key，都有与之对应的值value，即<key, value>的键值对。
比如：英汉词典就是英文与中文的对应关系，即<word, Chinese>就构成一种键值对。具体方式如下：
以<单词, 中文含义>为键值对，构建一棵二叉搜索树。注意：二叉搜索树需要进行比较，键值对比较时只比较key。
查询英文单词时，只需给出英文单词就可以快速找到与其对应的中文含义。
本篇博客到此结束，欢迎各位评论区留言~
