数据结构系列之二叉搜索树

前言

这是我数据结构系列的第一篇，其余C语言模拟的数据结构均会在开学之后跟随老师上课而更新（虽然我已经写完了），更新这块主要是因为要由二叉搜索树讲到AVL树再讲到红黑树，因为map和set的底层是红黑树，就需要知道红黑树的原理等等来封装实现map和set。

二叉搜索树的部分一定要掌握，avl树和红黑树的基础就是二叉搜索树，也更容易理解map和set的特性。

一、什么是二叉搜索树

binary-search-tree,简称BST（不要叫成SBTree)，可以是空树，如果是非空树，满足下列规则：
1.如果根结点的左子树存在，那么左子树上的所有结点的键值都比根节点上的键值小。
2.如果根结点的右子树存在，那么右子树上的所有结点的键值都比根节点上的键值大。
3.左右子树也满足二叉搜索树的规则。
二叉搜索树又称二叉排序树，因为它走一个中序遍历拿到的就是升序。

二、二叉搜索树的模拟

一些重要的操作

要知道模拟，就需要了解重要的操作了，对于这样一棵树，操作当然是增删查了。不支持改是因为不能单独动某个点，否则会导致不再是一颗二叉搜索树，后面的set和map也均不支持改key，后面提到应用会涉及到key-value可以进行value的修改，或者修改可以进行erase这个点 + insert新点来达到类似改的效果（但实际上并不是直接修改）。
我们模拟的增删查均可以实现递归和非递归版本，其中递归版本不好理解但是代码量较少，非递归版本好理解但是细节问题很多且很容易出错，代码量很长。

1.增加 -bool insert(const T& key)

增加相对好写，因为有这样的特性在，大致思路就是比当前结点大就往右走，小于就往左走，如果相等直接返回false，走到空进行连接即可。

2.查找- bool find(const T& key)

也比较好写，和insert的过程类似，就是比当前结点大就往右走，小于就往左走，如果相等直接返回true，走到空返回false。

3.删除-bool erase(const T& key)

这个是相对麻烦的场景，要考虑的东西很多。
1.先找到要删的结点，过程和find类似，如果找到了，进行下一步，如果没找到，直接返回false就可以。
2.找到要删的结点之后，分为四种情况。
2.1 如果既没有左孩子也没有右孩子，直接删除即可

2.2 如果有左孩子没有右孩子，父节点与其左孩子节点链接即可，考虑情况：
1.父节点为空。
2.父结点的左边是要删除结点还是右边是要删除结点

2.3 如果有右孩子没有左孩子，父节点与其右孩子节点链接即可，考虑情况：
1.父节点为空。
2.父结点的左边是要删除结点还是右边是要删除结点。

2.4 如果既有左孩子又有右孩子呢？这时要用替换法，步骤：
1.找左子树的最大结点或者右子树的最小结点。
2.将被删结点的值与其交换。
3.如果左子树的最大结点有左孩子，转化为第二种情况，右子树的最小结点有右孩子。
4.删除左子树的最大结点 / 右子树的最小结点。

这就是删除的步骤了，注意：一个孩子和没有孩子的情况可以归为一类，因为直接指向左边/右边就可以，如果有结点就链接上了，没有就链接上nullptr也符合。

下图演示删除一些结点的过程：
在这里插入图片描述
接着就是一些比较简单的，结点啊啥的，先写个结点，这里的结点只需要维护左右孩子，可以搞成三叉链（还有父亲）但是没必要，会更加麻烦

template<class T>
class BSTreeNode
{
public:BSTreeNode<T>* _left;BSTreeNode<T>* _right;T _key;
public:BSTreeNode(const T& val = T()):_key(val),_left(nullptr), _right(nullptr){}
};

二叉树：

template<class T>
class BSTree
{typedef BSTreeNode<T> Node;public:BSTree():_root(nullptr){}private:Node* _root;
}

三、非递归代码

非递归除了删除还是比较好写的。
直接上代码就行

insert

		bool insert(const T& x){if (_root == nullptr){Node* newnode = new Node(x);_root = newnode;return true;}else{//找到位置Node* cur = _root;Node* _parent = nullptr;while (cur != nullptr){if (cur->_key < x){_parent = cur;cur = cur->_right;}else if (cur->_key > x){_parent = cur;cur = cur->_left;}else{cout << "插入失败" << endl;return false;}}Node* newnode = new Node(x);//链接起来if (_parent->_key > x){_parent->_left = newnode;}else{_parent->_right = newnode;}return true;}}

find

bool find(const T& val)
{Node* cur = _root;while (cur){if (cur->_key > val){cur = cur->_left;}else if (cur->_key < val){cur = cur->_right;}else{return true;}}return false;
}

erase

erase像我上面一样把握住细节就行。
像我上面一步一步思考就行：
首先先找到要删除结点—
分为三种情况，左为空，右为空，左右都不为空，其中左为空和右为空代码类似----
左为空，先看父亲是不是空，如果父亲是空，说明cur是根，改一下根就可以，如果不是空，看父亲是左链接的cur还是右，将父亲和cur的右边链接起来就可以—
右为空情况类似–
看都不为空，要找左子树的最大结点，也要记录最大结点的父亲，因为还要链接，找到最大结点，判断最大结点的父亲是左链接还是右，与lmax的左相连即可，因为lmax一定没有右结点，他是最大，因为最后要删cur，再把lmax给cur即可。注意：代码里写了不可递归去删，因为此时已经不是二叉搜索树。
完整代码：

	bool erase(const T& val){Node* cur = _root;Node* _parent = nullptr;while (cur != nullptr){if (cur->_key < val){_parent = cur;cur = cur->_right;}else if (cur->_key > val){_parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (_parent == nullptr){_root = cur->_right;}else{if (_parent->_left == cur){_parent->_left = cur->_right;}else{_parent->_right = cur->_right;}}}else if (cur->_right == nullptr){if (_parent == nullptr){_root = cur->_left;}else{if (_parent->_left == cur){_parent->_left = cur->_left;}else{_parent->_right = cur->_left;}}}else{//左边树的最大结点Node* lmaxp = cur;Node* lmax = cur->_left;while (lmax->_right){lmaxp = lmax;lmax = lmax->_right;}//lmax为最大结点swap(lmax->_key, cur->_key);//这里不能递归去删，因为此时已经不是搜索二叉树，比如要删的结点是8，swap的结点是7，//去递归找8，最开始就会去右边发现找不到，所以不能递归if (lmaxp->_left == lmax){lmaxp->_left = lmax->_left;}else{lmaxp->_right = lmax->_left;}cur = lmax;}delete cur;return true;}}return false;}

正确性

验证正不正确，首先先尝试插入和走一个中序遍历，这没问题就去检查find，find没问题，就去erase，如果程序不会崩溃一般是没问题，建议把所有结点从上往下删并且每次中序跑一遍，这样都没问题基本就没问题了。

四、递归代码

循环一般都是可以改递归的，有递归和非递归还是优先写非递归，因为递归毕竟要建立一层一层的栈帧。
递归最简单的就是find了，轻轻松松写下来
因为树里的递归一般都需要拿结点来玩，而外面无法传根节点，所以需要写一个子函数把根节点传过去即可。
冷知识：递归单词是recursion

find:

bool _find(const T& val, Node* node)
{if (node == nullptr) return false;if (node->_val > val) return _find(val, node->_left);else if (node->_val < val) return _find(val, node->_right);else return true;
}bool find(const T& val)
{return _find(val, _root);
}

insert

insert的递归还是很牛的，先看代码再解释。


bool insert(const T& x)
{return _insert(x, _root);
}
bool _insert(const T& val, Node*& node)
{if (node == nullptr){node = new Node(val);return true;}if (val < node->_val) return _insert(val, node->_left);else if (val > node->_val)	return _insert(val, node->_right);else return false;
}

这里一个引用直接无敌，这里一层一层取别名只有走到空的时候起了作用，通过引用传递来修改上层的指针，比如到最后一层的左边，node是node->_left的别名，node走到nullptr，搞了一个结点，相当于node->_left = new Node(val);不仅不用额外搞父节点，代码也简洁很多。

不用引用的递归–非常不推荐

bool _insert(const T& val, Node* node, Node* parent)
{if (_root == nullptr){_root = new Node(val);return true;}if (node == nullptr){Node* newnode = new Node(val);if (parent->_val > val){parent->_left = newnode;}else{parent->_right = newnode;}return true;}if (node->_val > val){return _insert(val, node->_left, node);}else if (node->_val < val){return _insert(val, node->_right, node);}else{return false;}
}

erase

同样使用递归,先看代码再解释，其实能搞明白insert还是很好写的

bool erase(const T& val)
{return _erase(val, _root);
}
bool _erase(const T& val, Node* & node)
{if (node == nullptr) return false;if (node->_val < val) return _erase(val, node->_right);else if (node->_val > val) return _erase(val, node->_left);else{Node* del = node;if (node->_left == nullptr) {node = node->_right;}else if (node->_right == nullptr) {node = node->_left;}else {Node* lmax = node->_left;while (lmax->_right) lmax = lmax->_right;swap(lmax->_val, node->_val);return _erase(val,node->_left);}delete del;return true;}
}

前面都是正常逻辑，主要看else里的，简单画个图理解
在这里插入图片描述
并且这个可以最后交换完递归去删，为什么？为什么非递归不能递归去删？
来看：

所以递归写起来还是很爽的。

五、完善代码

1.拷贝构造

这里当然不能浅拷贝，需要拷贝出一颗树，返回根结点，所以需要再写一个函数,按结点拷贝就可以。走一个前序比较舒服，因为中序和后序代码还得多写两句，析构也是后序来析构。

BSTree(const BSTree<T>& t)
{t._root = Copy(_root);
}
Node* Copy(Node* node)
{if (node == nullptr) return nullptr;Node* newnode = new Node(node->_key,node->_val);newnode->_left = Copy(node->_left);newnode->_right = Copy(node->_right);return newnode;
}

2.赋值运算符重载

有了拷贝构造直接现代写法

BSTree<T>& operator=(BSTree<T>&& t)
{swap(_root, t._root);return *this;
}
BSTree<T>& operator=(const BSTree<T>& t)
{BSTreeT> tmp(t);swap(tmp._root, _root);return *this;
}

3.析构函数

同样也需要一个额外的函数，后序来删除,也比较简单

~BSTree()
{Destroy(_root);
}
void Destroy(Node*& node)
{if (node == nullptr) return;Destroy(node->_left);Destroy(node->_right);delete node;node = nullptr;
}

六、应用

1.K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
set是key模型，map是KV模型，学到底层会发现set也使用的key-value模型。

将搜索二叉树改为key和key-value模型，其实很简单，key模型就是模板参数是key，key-value模型模板参数就是K，V，然后插入的是pair<K,V> p;结点里存储的也是KV结构。
这里就不放代码了，比较简单，完整代码在：
个人gitee