一、二叉搜索树概念
什么是二叉搜索树？
二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下几个条件：
- 左子树中所有节点的值小于当前节点的值。
- 右子树中所有节点的值大于当前节点的值。
- 左子树和右子树也都是二叉搜索树。
二叉搜索树的中序遍历可以得到一个升序的序列，因此它常被用来实现有序集合或映射。在二叉搜索树中，查找、插入和删除操作的时间复杂度通常为O(logn)，其中n为树中节点的数量，这得益于二叉搜索树的结构和查找方法。
如下便是一颗二叉搜索树：
一句话总结二叉搜索树：
左子树节点总是比父节点小，右子树节点总是比父节点大的二叉树。
二叉搜索树的基本操作
利用二叉搜索树特性排升序。一听到二叉树，我们通常会想到的是什么？递归！请细细想想我们二叉搜索树的特点->左边的节点总是比父节点小，右边的节点总是比父节点大！那么我们对它使用中序遍历会发生什么呢？还是上面的那颗二叉树，对他进行中序遍历后：
中序遍历结果：arr={1,3,4,6,7,8,10,13,14};
二、二叉搜索树的实现
节点的定义
说来惭愧作者在此前实现数据结构都是用C语言实现的 o (╥﹏╥)o. ，本文应该是作为作者第一篇用C++实现的数据结构，也算是一个新的起点吧！
与C语言的区别主要还是在于在此使用struct（实际上是类）可以在定义时就进行初始化，利用的就是类的初始化列表的作用，这就省去了我们C语言时需要额外定义以及调用的初始化操作。只能说有了C++，C语言什么的不认识啦ʅ（´◔౪◔）ʃ
//节点定义 template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) {} };
二叉搜索树的定义
对于节点实例化并且重命名，并且给数据进行缺省赋值。
//二叉搜索树 template<class K> class BSTree { typedef BSTreeNode<K> Node; public: //...诸多的操作 private: Node* _root = nullptr; };
非递归操作
插入操作
插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
思路：判断是否为空->是-》直接给根节点赋值->否->进行循环遍历对要插入的值进行“比大小”->大往右，小往左遍历，直到空为止->比较空位置父节点的大小，大插右，小插左
//插入操作，按照左小右大的规则 bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { parent = cur; if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return false; } } cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; }
查找操作
通过搜索二叉树的特性，通过比较大小即可完成查找。
//查找操作 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; } else { return true; } } return false; }
删除操作（重点及难点！！！）
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除
而在b、c、d这三种情况中，b和c又很相似，所以以大类来划分，我们实际可以分为两种。一种是要删除的节点只有一个左孩子或者右孩子，另一种是有两个孩子节点。
现在详细介绍这两种情况：
当只有一个孩子节点时： 当要删节点的左孩子为空时，我们只需要将右半边给他的父亲就行，当然我们也需要注意以下两点：1、如果要删节点是根节点，那么我们需要将它的右孩子的地址覆盖原节点。2、要删节点不是根节点，那么我们也需要判断要删节点是它父节点的左孩子还是右孩子；左孩子则父节点的左孩子节点指向要删孩子的右孩子，右孩子则父节点的右孩子节点指向要删孩子的右孩子。当要删右孩子时也是同理，只是需要注意此时要注意的第二点中要指向的是要删节点是右孩子。下面上半部分的图为此部分的图解~
当有两个孩子节点时：我们则需要用到替换法。首先，我们需要根据以下规则中的一个规则：1、找到要删节点的左子树的最大节点。2、找到要删奇点的右子树的最小节点。接着，交换要删节点和找到的这个节点。最后，删除找到节点的位置，这个时候，我们就需要返回到上一部分我们只有一个孩子节点时要走的步骤，进行相应的操作。为什么呢？因为我们都知道要找最小或者最大只有在最左或者最右。而此时我们一定满足只有一个孩子节点时的于要求。下面下半部分的图为此部分的图解，这里取右子树的最小~
实现如下：
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 (cur == _root)//要删即为根节点 { _root = cur->_right; } else { if (cur == parent->_left)//因为左一定为空，为父节点的左则将右半边给父即可 { parent->_left = cur->_right; } else//同理为父节点的右则将右半边给父 { parent->_right = cur->_right; } } delete cur; } else if (cur->_right == nullptr)//右为空的情况 { //同理左为空 if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else//左右都不为空 {//可以选择找该节点左子树的最大节点（最右节点）或者右子树的最小节点（最左节点） //这里找右树的最小节点(最左节点) Node* parent = cur; Node* subleft = cur->_right; while (subleft->_left) { parent = subleft; subleft = subleft->_left; } swap(cur->_key, subleft->_key); //由于找到的是最左，则默认左为空,所以只需将右链接给父节点 if (subleft == parent->_left) { parent->_left = subleft->_right; } else { parent->_right = subleft->_right; } delete subleft; } return true; } } return false; }
递归法操作
中序遍历排升序（经典操作！）
上面详细介绍过了，不多阐述~
void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); }
插入操作（递归）
实际上同非递归的原理是相同的，不多阐述。实在不行画递归展开图就理解了~
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; }
查找操作（递归）
bool _FindR(Node* root, const K& key) { 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; } }
删除操作（递归）
实际上操作同非递归是一致的 ，特别注意接口的对于root的引用，这对于后续删除很有作用。当要删除只有一个孩子节点的节点时，同非递归的思想是一样的。当要删节点有两个孩子节点时，在最后面采取的是装换成在子树中去删除，同非递归中的找到替换节点转到只有一个孩子的操作是一样的思想。
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//找到了开始删除 { //实际上的操作同非递归差不多，这里巧妙的对root运用了引用 if (root->_left == nullptr) { Node* del = root; root = root->_right; delete del; return true; } else if (root->_right == nullptr) { Node* del = root; root = root->_left; delete del; return true; } else//找右子树的最大 { Node* subleft = root->_right; while (subleft->_left) { subleft = subleft->_left; } swap(root->_key, subleft->_key); // 转换成在子树去递归删除 return _EraseR(root->_right, key); } } }
二叉搜索树的应用
以上我们实现的二叉搜索树实际上也被称为K模型，而实际上还有一种模型叫做KV模型，以下为详细介绍：
1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。比如：
给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如
英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对
KV模型二叉搜索树
KV模型实际上同K模型差不多， 只是在K模型的基础上加了一个value值，对于其它的操作都是相似的，以下给出KV模型的整体代码：
namespace kv { 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: 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) { parent = cur; if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return false; } } cur = new Node(key, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } 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; } else { return cur; } } return nullptr; } 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 { // 准备删除 20:15继续 if (cur->_left == nullptr) {//左为空 if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } } else if (cur->_right == nullptr) {//右为空 if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } } else {//左右都不为空 // 右树的最小节点(最左节点) Node* parent = cur; Node* subLeft = cur->_right; while (subLeft->_left) { parent = subLeft; subLeft = subLeft->_left; } swap(cur->_key, subLeft->_key); if (subLeft == parent->_left) parent->_left = subLeft->_right; else parent->_right = subLeft->_right; } 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 << endl; _InOrder(root->_right); } private: Node* _root = nullptr; }; }
三、整体代码
#pragma once #include<iostream> using namespace std; namespace K { //节点定义 template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) {} }; //二叉搜索树 template<class K> class BSTree { typedef BSTreeNode<K> Node; public: //插入操作，按照左小右大的规则 bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { parent = cur; if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return false; } } cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } //查找操作 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; } else { return true; } } return false; } 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 (cur == _root)//要删即为根节点 { _root = cur->_right; } else { if (cur == parent->_left)//因为左一定为空，为父节点的左子树则将右半边给父即可 { parent->_left = cur->_right; } else//同理为父节点的右则将右半边给父 { parent->_right = cur->_right; } } delete cur; } else if (cur->_right == nullptr)//右为空的情况 { //同理左为空 if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else//左右都不为空 {//可以选择找该节点左子树的最大节点（最右节点）或者右子树的最小节点（最左节点） //这里找右树的最小节点(最左节点) Node* parent = cur; Node* subleft = cur->_right; while (subleft->_left) { parent = subleft; subleft = subleft->_left; } swap(cur->_key, subleft->_key); //由于找到的是最左，则默认左为空,所以只需将右链接给父节点 if (subleft == parent->_left) { parent->_left = subleft->_right; } else { parent->_right = subleft->_right; } delete subleft; } return true; } } return false; } void InOrder()//中序遍历即排升序 { _InOrder(_root); cout << endl; } bool FindR(const K& key)//递归找 { return _FindR(_root, key); } bool InsertR(const K& key)//递归插入 { return _InsertR(_root, key); } bool EraseR(const K& key)//递归删 { return _EraseR(_root, key); } BSTree() = default;// C++11 ~BSTree() { Destroy(_root); } BSTree(const BSTree<K>& t) { _root = Copy(t._root); } // t1 = t3 BSTree<K>& operator=(BSTree<K> t) { swap(_root, t._root); return *this; } private: Node* Copy(Node* root) { if (root == nullptr) return nullptr; Node* newRoot = new Node(root->_key); newRoot->_left = Copy(root->_left); newRoot->_right = Copy(root->_right); return newRoot; } void Destroy(Node*& root) { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; root = nullptr; } 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//找到了开始删除 { //实际上的操作同非递归差不多，这里巧妙的对root运用了引用 if (root->_left == nullptr) { Node* del = root; root = root->_right; delete del; return true; } else if (root->_right == nullptr) { Node* del = root; root = root->_left; delete del; return true; } else//找右子树的最大 { Node* subleft = root->_right; while (subleft->_left) { subleft = subleft->_left; } swap(root->_key, subleft->_key); // 转换成在子树去递归删除 return _EraseR(root->_right, key); } } } 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; } bool _FindR(Node* root, const K& key) { 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; } } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } Node* _root = nullptr; }; } namespace kv { 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: 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) { parent = cur; if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return false; } } cur = new Node(key, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } 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; } else { return cur; } } return nullptr; } 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 { // 准备删除 20:15继续 if (cur->_left == nullptr) {//左为空 if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } } else if (cur->_right == nullptr) {//右为空 if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } } else {//左右都不为空 // 右树的最小节点(最左节点) Node* parent = cur; Node* subLeft = cur->_right; while (subLeft->_left) { parent = subLeft; subLeft = subLeft->_left; } swap(cur->_key, subLeft->_key); if (subLeft == parent->_left) parent->_left = subLeft->_right; else parent->_right = subLeft->_right; } 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 << endl; _InOrder(root->_right); } private: Node* _root = nullptr; }; }
感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
