目录

前文

一，什么是二叉搜索树？

1.1 二叉搜索树的概念

二， 二叉搜索树的常用操作及其实现

2.1 查找

2.2 插入

 2.3 删除

三，二叉搜索树的应用

3.1 K模型

3.2 KV模型

四，二叉搜索树的性能分析

五，代码

总结

---

前文

本文主要是带领大家深入了解二叉搜索树的实现以及使用

ps：二叉搜索树的所有代码会在文末贴出(包括构造，析构，赋值等)

一，什么是二叉搜索树？

1.1 二叉搜索树的概念

二叉搜索树又称二叉排序树，它可能是个空树，或是具有以下特征的二叉树

1.若其左子树不为空，则其左子树上的所有值都小于根

2.若其右子树不为空，则其右子树上的所有值都大于根

3.其左右子树也符合二叉搜索树

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。 

二， 二叉搜索树的常用操作及其实现

上图为搜索二叉树的结点结构以及成员变量

2.1 查找

实现思路：

1.从根开始比较，比根大往右走，比根小往左走

2.最多比较树的高度次，走到空还没找到就返回false

 如上图所示，左边为非递归实现，右边是递归实现，这里递归实现需要注意，由于在类中都是通过*this指针调用成员函数，而*this指针是隐藏的无法控制递归条件，所以在类中写递归需要通过子函数完成递归调用。

---

2.2 插入

实现思路：

1.树为空，则直接new一个新节点给root

2.树不为空，通过二叉树查找的规则找到空位置，插入即可

 代码如下

 2.3 删除

实现思路：

利用二叉树查找的规则找到目标节点，不存在则返回false，但是删除的时候需要考虑以下四种情况

1.目标节点没有左右孩子

2.目标节点有左孩子，没右孩子

3.目标节点有右孩子，没有左孩子

4.目标节点左右孩子都有

 因为只有左孩子或者只有右孩子的处理方式都可以处理左右孩子都没有的情况，所以我们将左右孩子都没有的处理方式和只有左孩子的处理方式合并。

处理方式如下：

2.删除该节点，并且被删除节点的父节点指向被删除节点的左孩子——直接删除

 3.删除该节点，并且被删除节点的父节点指向被删除节点的右孩子——直接删除

 4.找到能够替代其位置的值，也就是要满足左子树小于该值，右子树大于该值，我们可以找左子树的最大值或者右子树的最小值，然后被删除节点赋值成找到的最大值或最小值，在删除最大值或最小值节点。

 

 如上图左边是非递归写法，右边是递归写法，有看不懂的可以私信我

三，二叉搜索树的应用

3.1 K模型

K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值

实际运用：

给一个单词，判断该单词是否拼写正确，具体方式：

具体方式如下：

1.以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
2.在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

3.2 KV模型

每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

1.比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；

2.再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

四，二叉搜索树的性能分析

在二叉搜索树中查找是绕不过去的功能，无论是插入还是删除都必须先查找，因此查找的效率和二叉搜索树的性能直接挂钩。

 尽管是同一组序列，但是不同的插入顺序构造出的搜索二叉树也是不一样的，如上图所示，左边是比较正常的树，右边是极端情况下的歪脖子树。

最优情况下，也就是类似于左边情况，复杂度就是树的高度，也就是：logN

最差情况下，类似于右边的歪脖子树，此时树的高度接近于N，因此其复杂度就是:N、

那么针对右边的歪脖子树有什么优化方法呢？

肯定是有的，后续学习的AVL树和红黑树就会起到极大的效果

五，代码

//K模型
namespace key
{template<class K>struct BSTreeNode{BSTreeNode(K key):_left(nullptr), _right(nullptr), _key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;};template<class K>class BSTree{typedef BSTreeNode<K> Node;public://构造函数BSTree():_root(nullptr){}//拷贝构造函数,用copy函数前序遍历拷贝BSTree(BSTree<K>& t){_root = copy(t._root);}Node* copy(Node* root){if (root == nullptr)return nullptr;Node* ret = new Node(root->_key);copy(root->_right);copy(root->_left);return ret;}//赋值重载BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}//析构函数,调用Destory后续遍历销毁即可~BSTree(){Destory(_root);}void Destory(Node*& root){if (root == nullptr)return;Destory(root->_right);Destory(root->_left);delete root;root = nullptr;}//查找bool Find(const K& key){if (_root == nullptr)return false;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 Findr(const K& key){_Findr(_root, key);}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;}return false;}//删除(erase)bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;//找val的位置while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{if (cur->_right == nullptr)//目标位置没有右孩子{if (cur == _root)//删除根的情况{_root = cur->_left;delete cur;}else{if (parent->_left == cur){parent->_left = cur->_left;delete cur;}else{parent->_right = cur->_left;delete cur;}}}else if (cur->_left == nullptr){if (cur == _root)//删除根的情况{_root = cur->_right;delete cur;}else{if (parent->_left == cur){parent->_left = cur->_right;delete cur;}else{parent->_right = cur->_right;delete cur;}}}else{//我们这里寻找左子树的最大值Node* maxLeft = cur->_left;Node* pmaxLeft = cur;while (maxLeft->_right){pmaxLeft = maxLeft;maxLeft = maxLeft->_right;}cur->_key = maxLeft->_key;if (pmaxLeft->_left == maxLeft){pmaxLeft->_left = maxLeft->_left;delete maxLeft;}else if (pmaxLeft->_right == maxLeft){pmaxLeft->_right = maxLeft->_left;delete maxLeft;}}return true;}}return false;}//递归删除bool Eraser(const K& key){return _Eraser(_root, key);}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* cur = root;if (root->_right == nullptr){/*Node* cur = root;*/root = root->_left;/*delete cur;*/}else if (root->_left == nullptr){/*Node* cur = root;*/root = root->_right;/*delete cur;*/}else//左右子树都存在{Node* pcur = cur;cur = cur->_left;while (cur->_right)//找左树最大值{pcur = cur;cur = cur->_right;}root->_key = cur->_key;/*if (pcur->_left == cur){pcur->_left = cur->_left;}else if (pcur->_right==cur){pcur->_right = cur->_left;}*/return _Eraser(root->_left, root->_key);}delete cur;return true;}return false;}//插入,成功插入返回true，失败也就是已有所要插入的数字则返回falsebool Insert(const K& key){if (_root == nullptr){_root = new Node(key);}else{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->_right = cur;}else{parent->_left = cur;}}return true;}//递归插入bool Insertr(const K& key){return _Insertr(_root, 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);}return false;}//中层遍历void InOrder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}private:Node* _root = nullptr;};
}

总结

本篇文章主要讲解二叉树的基本概念，实现以及应用场景，希望铁子们能有所收货