目录
一、二叉搜索树的概念
（一）概念
（二）主要功能
二、二叉搜索树的性能分析
三、二叉搜索树的插入与中序遍历
（一）插入
（二）中序遍历
（三）验证
四、二叉搜索树的查找
五、二叉搜索树的删除
六、二叉搜索树的整体代码实现
七、二叉搜索树key和key/value使用场景
（一）key搜索场景
（二）key/value搜索场景
（三）key/value二叉搜索树实现代码
一、二叉搜索树的概念
（一）概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
① 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
② 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
③ 它的左右子树也分别为⼆叉搜索树。
④ 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续学习map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。
二叉搜索树如下图所示：
（二）主要功能
二叉搜索树的主要功能是：搜索；次要功能是排序。
二、二叉搜索树的性能分析
因为二叉搜索树本身性质的原因，在搜索树中节点时，搜索的节点小于根节点就会向左走，大于就会向右走，重复以上操作，直到找到该节点为止。若果遇到找到底的情况，只需找【树的高度】次就行。
详细情况分析如下：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为：log2 N；
最差情况下，⼆叉搜索树退化为单支树(或者类似单支)，其高度为： N；
所以综合而言二叉搜索树增删查时间复杂度为： O(N)。
那么这样的效率显然是无法满足我们的需求，后续需要继续学习二叉搜索树的变形，平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据。
另外需要说明的是，二分查找也可以实现 O(log2 N) 级别的查找效率，但是二分查找有两大缺陷：
1. 需要存储在【支持下标随机访问】的结构中（数组），并且有序。
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
这里也就体现出了平衡⼆叉搜索树的价值。
三、二叉搜索树的插入与中序遍历
（一）插入
插入的具体过程如下：
1. 树为空，则直接新增结点，赋值给root指针；
2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
过程如下图所示：
实现代码如下：
//节点的插入函数(不考虑相同值的情况)
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* curparent = nullptr;while (cur){if (cur->_key < key){curparent = cur;cur = cur->_right;}else if (cur->_key > key){curparent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(key);if (curparent->_key < key)curparent->_right = cur;elsecurparent->_left = cur;return true;
}注意：
① cur只是寻找位置，并不是插入的关键，关键是另设一个指针变量curparent顺着cur下来且在cur的上一级进行链接。
② 当插入的二叉树的值相同的时候，不管是插入到左边还是右边都都一样的，因为后面的AVL树会对不平衡的树进行旋转，使其平衡，旋转之后的树就成为了新的树；且实践时一般不用二叉搜索树。
（二）中序遍历
因为外面不好找根节点，难以传参数进来，所以在外面再包一层，方便使用中序遍历。
代码实现如下：
void InOrder(){_InOrder(_root);cout << endl;}
private://中序遍历void _InOrder(Node* _root){if (_root == nullptr){return;}_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}（三）验证
以上整体如下，并写出例子检验：
BST.h文件如下：
#pragma once
#include<iostream>
using namespace std;namespace zyb
{//树节点模板template<class K>struct BSTNode{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key)//const+引用避免权限放大，能接收的值更广泛:_key(key), _left(nullptr), _right(nullptr){}};template<class K>class BSTree{typedef BSTNode<K> Node;public://节点的插入函数(不考虑相同值的情况)bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* curparent = nullptr;while (cur){if (cur->_key < key){curparent = cur;cur = cur->_right;}else if (cur->_key > key){curparent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(key);if (curparent->_key < key)curparent->_right = cur;elsecurparent->_left = cur;return true;}//因为外面不好找根节点，难以传参数进来，所以在外面再包一层//方便使用中序遍历void InOrder(){_InOrder(_root);cout << endl;}private://中序遍历void _InOrder(Node* _root){if (_root == nullptr){return;}_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}private://成员属性Node* _root = nullptr;};}
test.cpp文件如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include"BST.h"void test01()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };zyb::BSTree<int> bst;for (auto& e : a){bst.Insert(e);}bst.InOrder();
}int main()
{test01();return 0;
}运行结果如下：
四、二叉搜索树的查找
1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。
2. 最多查找高度次，走到到空，还没找到，这个值不存在。
3. 如果不不持插入相等的值，找到x即可返回。
4. 如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回：
实现代码如下：
//节点的查找(找到返回true，反之则false)
bool Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}elsereturn true;}return false;
}五、二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回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，可以直接删除。
总结：
① 一边节点为空的话，删除该节点，让父节点指向删除节点的另一边节点。
② 删除节点有两个孩子节点的话用替代法，即【左子树的最右节点】或【右子树的最左节点】进行替代，而后转为第一种情况删除该节点。
实现代码如下：
//节点的删除
bool Erase(const K& key)
{Node* cur = _root;Node* curparent = nullptr;//因为要考虑删除只有一个孩子节点的节点，所以删除节点的父节点要设置//以便来连接删除节点的孩子节点while (cur){if (cur->_key < key){curparent = cur;cur = cur->_right;}else if (cur->_key > key){curparent = cur;cur = cur->_left;}else//先找到需要删除的节点{//以下开始分情况删除//① 只有一个孩子节点或者没有孩子节点的情况// 删除节点的左子树为空，把右子树拼接到父节点上if (nullptr == cur->_left){if (nullptr == curparent)_root = cur->_right;else{if (curparent->_left == cur)curparent->_left = cur->_right;elsecurparent->_right = cur->_right;}delete cur;return true;}// 删除节点的右子树为空，把左子树拼接到父节点上else if (nullptr == cur->_right){if(nullptr == curparent)_root = cur->_left;else{if (curparent->_left = cur)curparent->_left = cur->_right;elsecurparent->_right = cur->_right;}}// ② 删除节点的左右函数都不为空的情况// 需要使用替换法，假设替换的是右子树的最小节点else{Node* minNodeParent = cur;Node* minNode = cur->_right;//这里设置右子树最小节点的父节点是因为替换法会转变成前两种情况，//需要设置一个父节点来链接替换节点的孩子节点while (minNode->_left){minNodeParent = minNode;minNode = minNode->_left;}//这一步找到右子树的最小值//替换：cur->_key = minNode->_key;//删除右子树的最小节点，将它的右节点拼接到这个最小节点的父节点上// 需检测minNodeParent节点哪边是minNode节点if (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;elseminNodeParent->_right = minNode->_right;delete minNode;return true;}}}return false;
}六、二叉搜索树的整体代码实现
BST.h文件：
#pragma once
#include<iostream>
using namespace std;namespace zyb
{//树节点模板template<class K>struct BSTNode{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key)//const+引用避免权限放大，能接收的值更广泛:_key(key), _left(nullptr), _right(nullptr){}};template<class K>class BSTree{typedef BSTNode<K> Node;public://节点的插入函数(不考虑相同值的情况)bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* curparent = nullptr;while (cur){if (cur->_key < key){curparent = cur;cur = cur->_right;}else if (cur->_key > key){curparent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(key);if (curparent->_key < key)curparent->_right = cur;elsecurparent->_left = cur;return true;}//节点的查找(找到返回true，反之则false)bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}elsereturn true;}return false;}//节点的删除bool Erase(const K& key){Node* cur = _root;Node* curparent = nullptr;//因为要考虑删除只有一个孩子节点的节点，所以删除节点的父节点要设置//以便来连接删除节点的孩子节点while (cur){if (cur->_key < key){curparent = cur;cur = cur->_right;}else if (cur->_key > key){curparent = cur;cur = cur->_left;}else//先找到需要删除的节点{//以下开始分情况删除//① 只有一个孩子节点或者没有孩子节点的情况// 删除节点的左子树为空，把右子树拼接到父节点上if (nullptr == cur->_left){if (nullptr == curparent)_root = cur->_right;else{if (curparent->_left == cur)curparent->_left = cur->_right;elsecurparent->_right = cur->_right;}delete cur;return true;}// 删除节点的右子树为空，把左子树拼接到父节点上else if (nullptr == cur->_right){if(nullptr == curparent)_root = cur->_left;else{if (curparent->_left = cur)curparent->_left = cur->_right;elsecurparent->_right = cur->_right;}}// ② 删除节点的左右函数都不为空的情况// 需要使用替换法，假设替换的是右子树的最小节点else{Node* minNodeParent = cur;Node* minNode = cur->_right;//这里设置右子树最小节点的父节点是因为替换法会转变成前两种情况，//需要设置一个父节点来链接替换节点的孩子节点while (minNode->_left){minNodeParent = minNode;minNode = minNode->_left;}//这一步找到右子树的最小值//替换：cur->_key = minNode->_key;//删除右子树的最小节点，将它的右节点拼接到这个最小节点的父节点上// 需检测minNodeParent节点哪边是minNode节点if (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;elseminNodeParent->_right = minNode->_right;delete minNode;return true;}}}return false;}//因为外面不好找根节点，难以传参数进来，所以在外面再包一层//方便使用中序遍历void InOrder(){_InOrder(_root);cout << endl;}private://中序遍历void _InOrder(Node* _root){if (_root == nullptr){return;}_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}private://成员属性Node* _root = nullptr;};}
test.cpp文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include"BST.h"void test01()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };zyb::BSTree<int> bst;for (auto& e : a){bst.Insert(e);}cout << bst.Find(7) << endl;bst.InOrder();bst.Erase(8);bst.InOrder();
}int main()
{test01();return 0;
}以上代码的运行结果如下：
七、二叉搜索树key和key/value使用场景
（一）key搜索场景
只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。
场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。
（二）key/value搜索场景
每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走⼆叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。
场景1：简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文。
场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间减去入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在则说明单词第一次出现：（单词，1），单词存在，则++单词对应的次数。
（三）key/value二叉搜索树实现代码
key_value.h文件：
#pragma once
#include<iostream>
using namespace std;namespace key
{//树节点模板template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& value)//const+引用避免权限放大，能接收的值更广泛:_key(key),_value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree{typedef BSTNode<K, V> Node;public://节点的插入函数(不考虑相同值的情况)bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* cur = _root;Node* curparent = nullptr;while (cur){if (cur->_key < key){curparent = cur;cur = cur->_right;}else if (cur->_key > key){curparent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(key, value);if (curparent->_key < key)curparent->_right = cur;elsecurparent->_left = cur;return true;}//节点的查找(找到返回true，反之则false)Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}elsereturn cur;}return nullptr;}//节点的删除bool Erase(const K& key){Node* cur = _root;Node* curparent = nullptr;//因为要考虑删除只有一个孩子节点的节点，所以删除节点的父节点要设置//以便来连接删除节点的孩子节点while (cur){if (cur->_key < key){curparent = cur;cur = cur->_right;}else if (cur->_key > key){curparent = cur;cur = cur->_left;}else//先找到需要删除的节点{//以下开始分情况删除//① 只有一个孩子节点或者没有孩子节点的情况// 删除节点的左子树为空，把右子树拼接到父节点上if (nullptr == cur->_left){if (nullptr == curparent)_root = cur->_right;else{if (curparent->_left == cur)curparent->_left = cur->_right;elsecurparent->_right = cur->_right;}delete cur;return true;}// 删除节点的右子树为空，把左子树拼接到父节点上else if (nullptr == cur->_right){if (nullptr == curparent)_root = cur->_left;else{if (curparent->_left = cur)curparent->_left = cur->_right;elsecurparent->_right = cur->_right;}}// ② 删除节点的左右函数都不为空的情况// 需要使用替换法，假设替换的是右子树的最小节点else{Node* minNodeParent = cur;Node* minNode = cur->_right;//这里设置右子树最小节点的父节点是因为替换法会转变成前两种情况，//需要设置一个父节点来链接替换节点的孩子节点while (minNode->_left){minNodeParent = minNode;minNode = minNode->_left;}//这一步找到右子树的最小值//替换：cur->_key = minNode->_key;//删除右子树的最小节点，将它的右节点拼接到这个最小节点的父节点上// 需检测minNodeParent节点哪边是minNode节点if (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;elseminNodeParent->_right = minNode->_right;delete minNode;return true;}}}return false;}//因为外面不好找根节点，难以传参数进来，所以在外面再包一层//方便使用中序遍历void InOrder(){_InOrder(_root);cout << endl;}private://中序遍历void _InOrder(Node* _root){if (_root == nullptr){return;}_InOrder(_root->_left);cout << _root->_key << _root->_value<<" ";_InOrder(_root->_right);}private://成员属性Node* _root = nullptr;};}
test.cpp文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include"key_value.h"void test02()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };key::BSTree<string,int> bst;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的结点中水果对应的次数++auto ret = bst.Find(str);if (ret == NULL){bst.Insert(str, 1);}else{ret->_value++;}}bst.InOrder();
}int main()
{test02();return 0;
}运行结果如下：
以上内容仅供分享，若有错误，请多指正。