二叉搜索树
二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
还有一个注意的点：
二叉搜索树的中序遍历一定可以是一个有序的序列，并且再插入节点后依旧是一个二叉搜索树的结构！
例如：
下图中打x叉的就不是二叉搜索树，因为第三层的5小于他的父节点10，打勾的就是二叉搜索树，它满足了二叉搜索树的所有条件
二叉搜索树操作
首先给出一个二叉搜索树的例子：
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
1 二叉搜索树的查找
1 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
2 最多查找高度次，走到到空，还没找到，这个值不存在。
2 二叉搜索树的插入
插入的具体过程如下：
1 树为空，则直接新增节点，赋值给root指针
2 树不空，按二叉搜索树性质查找插入位置，插入新节点
其实插入的节点到最终都是一个叶子节点，所以二叉搜索树的插入还是很简单的，就比如我要插入0和16，最终都是成为这棵树的新的叶子节点
3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
1 要删除的结点无孩子结点
2 要删除的结点只有左孩子结点
3 要删除的结点只有右孩子结点
4 要删除的结点有左、右孩子结点
虽然有四种情况，但是第二种情况和第三种情况可以看作是一个情况，第一种情况就很简单的，直接删除掉就是了，但是其他三种需要考虑到他们的孩子交给谁托管的问题，对此我们进行了总结：
情况2：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
情况3：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
情况4：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题
针对上面的几种情况，我们用实例来理解：
请看图
删除7（删除节点无孩子节点）
当删除节点没有孩子节点时，就不用管其他的，直接去掉这个节点即可
删除14（删除节点无右孩子节点）
其实没有左孩子或者右孩子节点都可视为一种情况，就是只有一个节点的情况，都需要将自己的那个孩子节点交给自己的父节点托管
删除3和8（删除节点左孩子和右孩子节点都有）
当删除节点既有左孩子又有右孩子的时候我们面对的问题就是他被删除后他的两个孩子节点怎么办，这个时候我们就有两种解决的办法，一个是找一个左子树的最大节点，另一种办法就是找右子树的最小节点来替代这个被删除的节点的值，这种情况不同于上面两种情况，我们叫做替代删除
二叉搜索树的实现
节点框架的构造
要实现二叉搜索树，我们首先要用结构体定义一个节点的内容：
我们用模板就很方便，无论他是什么类型，然后把我们在结构体里面再定义一个构造函数，并且直接使用初始化列表进行初始化
template<class K> struct BSTreeNode { BSTreeNode<K> _left; BSTreeNode<K> _right; K _key; BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) {} };
二叉搜索树的插入
二叉搜索树的插入有两种情况：
空树和非空树
空树时直接令key值节点为root节点
非空树时就要向下找了
bool Insert(const K& key) { //空树时直接令根节点为插入节点的_key为key if (_root == nullptr) { _root = new Node(key); return true; } //否则就需要向下找合适的地方 Node* parent = nullptr; Node* cur = _root; while (cur) { //最后parent这个节点就是需要插入节点的父节点 parent = cur; //如果cur的_key小于key，那么cur就向他的右子树向下查找 if (cur->_key < key) { cur = cur->_right; } //向左子树向下查找 if (cur->_key > key) { cur = cur->_left; } //如果相等就不能插入，返回false else { return false; } } //将cur节点填入key，如果parent父节点的值小于key，则将cur放在parent的右边，大于则反之 cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } //最后记得返回true return true; }
例如，我要再一棵树上插入key为11的节点
二叉搜索树的查找
二叉搜索树的查找就很容易了，只要判断大小即可，到最后如果还没有结束就是返回false
bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key > key) { cur = cur->_left; } if (cur->_key < key) { cur = cur->_right; } //相等就返回true else { return true; } } return false; }
二叉搜索树的删除
前面我们就提到过二叉搜索树的删除节点就要分为好几种情况，这个部分时二叉搜索树实现中最难的
分为三部分：
左为空
//左为空 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; //subLeft再遍历完成后就是右子树的最小节点 while (subLeft->_left) { parent = subLeft; subLeft = subLeft->_left; } //cur就是你要删除的节点，将subleft的_key和cur的_key交换 swap(cur->_key, subLeft->_key); //将subLeft的右节点直接链接到parent if (subLeft == parent->_left) { parent->_left = subLeft->_right; } else { parent->_right = subLeft->_right; } //最后删除subleft，替代删除了原本cur内的_key delete subLeft; }
注释为大家讲解了
完整代码如下：
bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { //找_key为key的节点 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; //subLeft再遍历完成后就是右子树的最小节点 while (subLeft->_left) { parent = subLeft; subLeft = subLeft->_left; } //cur就是你要删除的节点，将subleft的_key和cur的_key交换 swap(cur->_key, subLeft->_key); //将subLeft的右节点直接链接到parent if (subLeft == parent->_left) { parent->_left = subLeft->_right; } else { parent->_right = subLeft->_right; } //最后删除subleft，替代删除了原本cur内的_key delete subLeft; } return true; } } return false; }
二叉搜索树的应用
- K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。 - KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
KV结构我们就要用到模板的便利了
// 改造二叉搜索树为KV结构 template<class K, class V> struct BSTNode { BSTNode(const K& key = K(), const V& value = V()) : _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value) {} BSTNode<T>* _pLeft; BSTNode<T>* _pRight; K _key; V _value }; template<class K, class V> class BSTree { typedef BSTNode<K, V> Node; typedef Node* PNode; public: BSTree() : _pRoot(nullptr) {} PNode Find(const K& key); bool Insert(const K& key, const V& value) bool Erase(const K& key) private: PNode _pRoot; }; void TestBSTree3() { // 输入单词，查找单词对应的中文翻译 BSTree<string, string> dict; dict.Insert("string", "字符串"); dict.Insert("tree", "树"); dict.Insert("left", "左边、剩余"); dict.Insert("right", "右边"); dict.Insert("sort", "排序"); // 插入词库中所有单词 string str; while (cin >> str) { BSTreeNode<string, string>* ret = dict.Find(str); if (ret == nullptr) { cout << "单词拼写错误，词库中没有这个单词:" << str << endl; } else { cout << str << "中文翻译:" << ret->_value << endl; } } } void TestBSTree4() { // 统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; BSTree<string, int> countTree; for (const auto& str : arr) { // 先查找水果在不在搜索树中 // 1、不在，说明水果第一次出现，则插入<水果, 1> // 2、在，则查找到的节点中水果对应的次数++ //BSTreeNode<string, int>* ret = countTree.Find(str); auto ret = countTree.Find(str); if (ret == NULL) { countTree.Insert(str, 1); } else { ret->_value++; } } countTree.InOrder(); }
好了，今天的分享到这里就结束了，感谢大家的支持!
