【C++杂货铺】二叉搜索树

---

目录

前言 

二叉搜索树的概念

二叉搜索树的操作

二叉搜索树的查找

二叉搜索树的插入

二叉搜书树的删除

二叉搜索树的应用

二叉搜索树的实现

二叉搜索树的性能分析

总结

---

前言 

        欢迎观看本期博文，这期内容讲解二叉搜索树，包括了什么是二叉搜索树，如何实现二叉搜索树，以及二叉搜索树的应用，此外还会分析二叉搜索树的性能。

        在二叉搜索树应用中，会包含K模型，对应的是STL中set容器;KV模型，对应的是STL中的map容器。

二叉搜索树的概念

        二叉搜索树又称为二叉排序树，它或是一颗空树，或者具有以下性质的二叉树：

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

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

3. 它的左右子树也称为二叉搜索树。

二叉搜索树的操作

二叉搜索树的查找

1. 从根开始比较查找，比根大的往右查找，比根小的往左边查找。

2. 最多查找高度次，走到为空，还没找到，则这个值不存在。

二叉搜索树的插入

1. 树为空，则直接新增节点，赋值给root指针。

2. 树不为空，按二叉搜索树性质查找插入位置，插入新节点。

二叉搜书树的删除

        首先查找元素是否在二叉搜索树总，如果不存在，则返回，否则要删除的节点可能分为下面四种情况：

1. 要删除的节点无孩子节点

2. 要删除的节点只有左孩子节点

3. 要删除的节点只有右孩子节点

4. 要删除的节点有左右孩子节点。

        开起来有四种情况，实际情况1可以与情况2或者3结合起来，因此真正的删除过程如下：

情况A：删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点 --> 直接删除。

情况B：删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点--> 直接删除。

情况C：在它的右子树中寻找中序心爱的第一个节点（Key值最小），用它的值填补被删除节点中，再来处理该节点的删除问题 ---> 替换法删除。

二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方 式在现实生活中非常常见： 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文就构成一种键值对； 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出 现次数就是就构成一种键值对。

二叉搜索树的实现

1. K模型：

template struct BSTreeNode{BSTreeNode(K key): _key(key),_left(nullptr), _right(nullptr){}K _key;BSTreeNode* _left;BSTreeNode* _right;};templateclass BSTree{typedef BSTreeNode  Node;void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout _key _right);}public://插入bool Insert(K key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key _right;}else{return false;}}if (key > parent->_key){cur = new Node(key);parent->_right = cur;}else{cur = new Node(key);parent->_left = cur;}return true;}//删除bool Erase(const K& key){Node* cur = _root;Node* parent = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key _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;}}delete cur;}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{//左子树最大的 || 右子树最小的Node* RightMin = cur->_right;Node* RightMinParent = cur;while (RightMin->_left){RightMinParent = RightMin;RightMin = RightMin->_left;}swap(RightMin->_key, cur->_key);if(RightMin == RightMinParent->_left)RightMinParent->_left = RightMin->_right;elseRightMinParent->_right = RightMin->_right;delete RightMin;}return true;}}return false;}//查找Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key _right;}else{cout _key _key _right;}else{return false;}}if (key > parent->_key){cur = new Node(key,val);parent->_right = cur;}else{cur = new Node(key,val);parent->_left = cur;}return true;}//删除bool Erase(const K& key){Node* cur = _root;Node* parent = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key _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;}}delete cur;}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{//左子树最大的 || 右子树最小的Node* RightMin = cur->_right;Node* RightMinParent = cur;while (RightMin->_left){RightMinParent = RightMin;RightMin = RightMin->_left;}swap(RightMin->_key, cur->_key);if (RightMin == RightMinParent->_left)RightMinParent->_left = RightMin->_right;elseRightMinParent->_right = RightMin->_right;delete RightMin;}return true;}}return false;}//查找Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key _right;}else{return cur;}}return cur;}//遍历void InOrder(){_InOrder(_root);cout