1.什么是二叉搜索树

2.二叉搜索树的性能分析

3.二叉搜索树的实现

3.1二叉搜索树的插入

这里我们实现的二叉搜索树暂时不让重复的字符进行插入

//插入函数
bool Insert(const K& key)
{if (_root == nullptr){//当根节点为空时，需要初始化根节点_root = new Node(key);return true;}Node* pcur = _root;Node* parent = nullptr;while(pcur){if (pcur->_key > key){parent = pcur;pcur = pcur->_left;}else if (pcur->_key < key){parent = pcur;pcur = pcur->_right;}else return false;//不支持相同的值进行重复插入}if (parent->_left == pcur) parent->_left = new Node(key);else parent->_right = new Node(key);return true;
}

3.2二叉搜索树的查找

二叉搜索树中如果没有相同元素的话，那么查找起来是很简单的：

//二叉搜索树的查找
bool Find(const K& key)
{Node* pcur = _root;while (pcur){if (pcur->_key > key) pcur = pcur->_left;else if (pcur->_key < key) pcur = pcur->_right;else return true;}return false;
}

而如果有相等的值进行查找，其实是查找出现的第一个数据，这个之后会看：

这里出现的问题：

3.3二叉树搜索树的打印

直接一个中序遍历即可，还是十分简单的：

void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);
}

但是调用会出现错误，因为我们在外面拿不到_root，所以这里有两个方法：
1.实现一个Getroot方法
2.再实现一个类函数，在类中可以调用_InOrder函数
这里采用第二种方式：

3.4二叉树搜索树的删除

二叉搜索树的删除相对来说比较复杂，我们画图来看：

//二叉树的删除
bool Erase(const K& key)
{//对于删除，我们肯定要先找到这个结点Node* parent = nullptr;Node* pcur = _root;while (pcur){if (pcur->_key < key){parent = pcur;pcur = pcur->_right;}else if (pcur->_key > key){parent = pcur;pcur = pcur->_left;}else{//这里就找到了该结点，进行删除操作if (pcur->_left == nullptr){if (parent == nullptr) _root = pcur->_right;else{//左结点为空if (pcur == parent->_right) parent->_right = pcur->_right;else parent->_left = pcur->_right;}delete pcur;//pcur结点是需要被删除的}else if (pcur->_right == nullptr){if (parent == nullptr) _root = pcur->_left;else{//右结点为空if (pcur == parent->_right)parent->_right = pcur->_left;elseparent->_left = pcur->_left;}delete pcur;//pcur结点是需要被删除的}else{//左右结点都不为空时，我们这里采用寻找右子树的最小结点Node* minright = pcur->_right;Node* minparent = pcur;while (minright->_left) minparent = minright, minright = minright->_left;pcur->_key = minright->_key;if (minparent->_left == minright) minparent->_left = minright->_right;else minparent->_right = minright->_right;delete minright;}return true;}}return false;
}

3.5全部代码实现

//结点的结构体
template<class K>
struct BSTNode
{//结点中需要一个值，然后再存储左右结点的指针即可K _key;BSTNode<K>* _left;BSTNode<K>* _right;//构造BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};//class SearchBinaryTree
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* pcur = _root;Node* parent = nullptr;while(pcur){if (pcur->_key < key){parent = pcur;pcur = pcur->_right;}else if (pcur->_key > key){parent = pcur;pcur = pcur->_left;}else {return false;//不支持相同的值进行重复插入}}pcur = new Node(key);if (parent->_key < key) parent->_right = pcur;else parent->_left = pcur;这个比较不能是这样比较的，应该是key值的比较来确定左树还是右树//if (parent->_left == pcur) parent->_left = pcur;//else parent->_right = pcur;return true;}//二叉搜索树的查找bool Find(const K& key){Node* pcur = _root;while (pcur){if (pcur->_key > key) pcur = pcur->_left;else if (pcur->_key < key) pcur = pcur->_right;else return true;}return false;}//二叉树的删除bool Erase(const K& key){//对于删除，我们肯定要先找到这个结点Node* parent = nullptr;Node* pcur = _root;while (pcur){if (pcur->_key < key){parent = pcur;pcur = pcur->_right;}else if (pcur->_key > key){parent = pcur;pcur = pcur->_left;}else{//这里就找到了该结点，进行删除操作if (pcur->_left == nullptr){if (parent == nullptr) _root = pcur->_right;else{//左结点为空if (pcur == parent->_right) parent->_right = pcur->_right;else parent->_left = pcur->_right;}delete pcur;//pcur结点是需要被删除的}else if (pcur->_right == nullptr){if (parent == nullptr) _root = pcur->_left;else{//右结点为空if (pcur == parent->_right)parent->_right = pcur->_left;elseparent->_left = pcur->_left;}delete pcur;//pcur结点是需要被删除的}else{//左右结点都不为空时，我们这里采用寻找右子树的最小结点Node* minright = pcur->_right;Node* minparent = pcur;while (minright->_left) minparent = minright, minright = minright->_left;pcur->_key = minright->_key;if (minparent->_left == minright) minparent->_left = minright->_right;else minparent->_right = minright->_right;delete minright;}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);}Node* _root = nullptr;
};int main()
{BSTree<int> b;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){b.Insert(e);}b.InOrder();b.Erase(8);b.InOrder();for (auto e : a){b.Erase(e);b.InOrder();}return 0;
}

4.二叉搜索树的使用场景

4.1key使用场景

4.2 key/value搜索场景

我们可以简单看一下使用场景（比如我们要查汉字出现的次数）：