🌇个人主页：平凡的小苏
📚学习格言：命运给你一个低的起点，是想看你精彩的翻盘，而不是让你自甘堕落，脚下的路虽然难走，但我还能走，比起向阳而生，我更想尝试逆风翻盘。
🛸C++专栏：C++内功修炼基地
> 家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路 过的友友麻烦多多点赞关注。 欢迎你们的私信提问，感谢你们的转发！ 关注我，关注我，关注我，你们将会看到更多的优质内容！！
一、二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1.若他的左子树不为空，则左子树上所有节点的值小于根节点的值
2.若他的右子树不为空，则右子树上所有节点的值大于根节点的值
3.它的左右子树也分别为二叉搜索树
二叉搜索树的结构如下
template <class K,class V>
struct BSTreeNode//生成二叉搜索树的节点
{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value):_left(nullptr),_right(nullptr),_key(key),_value(value){}
};template<class K,class V>
class BSTree//表示整颗二叉搜索树
{typedef BSTreeNode<K,V> Node;
public:BSTree():_root(nullptr){}
private:Node* _root;
};
二、二叉搜索树的查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。
-
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能.
-
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：如下图所示
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：logN
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：O(N)
1、递归版本的二叉搜索树的查找
Node* _FindR(Node* root, const K& key)
{if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}
}
2、非递归版本的二叉搜索树的查找
Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return cur;}}return nullptr;
}
三、二叉搜索树的插入
二叉搜索树的插入需要考虑插入后，需要维持二叉搜索树的形态。
1、二叉搜索树的非递归写法
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 (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;
}
注意：这里要记录一个父亲节点，来确保是插入在左侧还是插入在右侧
2、二叉搜索树的递归写法
bool _InsertR(Node*& root, const K& key,const V& value)
{if (root == nullptr){root = new Node(key,value);return true;}if (root->_key < key){return _InsertR(root->_right, key,value);}else if (root->_key > key){return _InsertR(root->_left, key,value);}else{return false;}
}
递归写法巧就巧在形参是指针的引用，例如我现在要插入9，下层的root是上一层root->_left的别名， 下层root = new Node(key);即为上一层root->_left=new Node(key);这样插入节点就自动和父节点连接上了。
四、二叉搜索树的删除
二叉搜索树的节点进行删除后，同样需要维持二叉搜索树的形态。
二叉搜索树的删除无非是三种情况：
1、二叉搜索树非递归版本的删除
bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = 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 = cur->_left;while (leftMax->_right)//找到左树的最大节点，即在左树的最右边{parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);//交换数据//如上图，如果删除的是3，那么就会和1交换，即是如下这种情况，需要将3的左连接到1的左if (parent->_left == leftMax){parent->_left = leftMax->_left;}//如上图如果删除的是8，则会和6交换，则是如下这种情况，需要将10的有连接到6的左else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;
}
1、先通过二叉搜索树的性质找到要删除的节点；
2、找到需要删除的节点后，分三种情况进行讨论：
一、被删除节点的左孩子为空，除了cur等于根节点情况下，其他情况下，父节点的孩子指针由指向被删除节点转为指向被删除节点的右孩子。（如图删除14）
二、被删除节点的左孩子存在但右孩子为空，除了cur等于根节点情况下，其他情况下，父节点的孩子指针由指向被删除节点转为指向被删除节点的左孩子。（如图删除9）
三、被删除的节点均不为空，可以选用左树最大节点或者右树最小节点对被删除节点进行值替换，问题转化为第一种或第二种情况。（详见代码注释）
2、二叉搜索树递归版本的删除
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->_left == nullptr){root = root->_right;//因为是引用直接修改它的指向就可以}else if (root->_right == nullptr){root = root->_left;}else{Node* leftmax = root->_left;while (leftmax->_right)//找到左树的最大节点{leftmax = leftmax->_right;}swap(root->_key, leftmax->_key);//交换swap(root->_value, leftmax->_value);return _EraseR(root->_left, key);//再次进行递归删除，这样就转换成了情况1或者情况2 的删除}delete del;return true;}return false;
}
注意：由于引用的语法，循环版本不能使用引用，因为递归使其每个栈帧不一样了，所以可以使用引用
五、二叉搜索树的源码
1、key/value的搜索模型（节点既存key又存value)
key/value搜索模型指每一个key值，都有与之对应的value值，例如英汉互译，一个英文单词可以对应一个翻译字符串。该模型还可以用于统计相同内容出现次数。
2、key/value模型的源码
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <algorithm>
using namespace std;template <class K,class V>
struct BSTreeNode//生成二叉搜索树的节点
{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value):_left(nullptr),_right(nullptr),_key(key),_value(value){}
};template<class K,class V>
class BSTree//表示整颗二叉搜索树
{typedef BSTreeNode<K,V> Node;
public:BSTree():_root(nullptr){}BSTree(const BSTree<K,V>& t){_root = Copy(t._root);}BSTree<K, V>& operator=(BSTree<K, V> t){swap(_root, t._root);return *this;}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 (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;}void InOrder(){_InOrder(_root);cout << endl;}Node* Find(const K& key){Node* cur = _root;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){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = 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 = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}Node* FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key, const V& value){return _InsertR(_root, key,value);}bool EraseR(const K& key){return _EraseR(_root, key);}~BSTree(){Destroy(_root);}
private: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* copynewnode = new Node(root->_key,root->_value);copynewnode->_left = Copy(root->_left);copynewnode->_right = Copy(root->_right);return copynewnode;}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->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftmax = root->_left;while (leftmax->_right){leftmax = leftmax->_right;}swap(root->_key, leftmax->_key);swap(root->_value, leftmax->_value);return _EraseR(root->_left, key);}delete del;return true;}return false;}bool _InsertR(Node*& root, const K& key,const V& value){if (root == nullptr){root = new Node(key,value);return true;}if (root->_key < key){return _InsertR(root->_right, key,value);}else if (root->_key > key){return _InsertR(root->_left, key,value);}else{return false;}}Node* _FindR(Node* root, const K& key){if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}
private:Node* _root;
};void BSTreeTest()
{string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (auto& str : arr){auto ret = countTree.FindR(str);if (ret == nullptr){countTree.InsertR(str, 1);}else{ret->_value++;}}countTree.InOrder();
}
![[JavaScript游戏开发] Q版地图上让英雄、地图都动起来](https://img-blog.csdnimg.cn/725ebb89254c46589848d4a6335abbd6.png)
