【C++深度探索】二叉搜索树的全面解析与高效实现
这里将会不定期更新有关C/C++的内容，欢迎大家点赞，收藏，评论🥳🥳🎉🎉🎉
文章目录
- 1.二叉搜索树
- 2.二叉搜索树的功能
- 3.二叉搜索树的实现
- ✨二叉搜索树的结构
- ✨插入函数Insert()
- ✨查找函数Find()
- ✨删除函数Erase()
- ✨中序遍历InOrder()
- ✨析构函数
- 4.二叉搜索树的应用
- 5.二叉搜索树的性能分析
- 6.结语
1.二叉搜索树
二叉搜索树(BST,Binary Search Tree)又称二叉排序树，是一种特殊的二叉树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
二叉搜索树（Binary Search Tree）的每个节点的左子树中的所有节点都比该节点小，右子树中的所有节点都比该节点大。这个特性使得二叉搜索树可以用来实现非常高效的查找、插入和删除操作。
2.二叉搜索树的功能
二叉搜索树是一种特殊的二叉树，它具有以下功能：
- 插入节点：可以将一个新节点插入到二叉搜索树中。
void TestBSTree() { //插入节点 BSTree dict; dict.Insert("insert", "插入"); dict.Insert("erase", "删除"); dict.Insert("select", "查找"); dict.Insert("sort", "排序"); }这里实现的二叉搜索树每次插入的是两个值，模拟键值对，二叉搜索树的节点除了左右子节点指针也不再只存储一个值，而是两个。也就是说当我们知道一个值时，就可以利用它来查找另外一个值。
键值对（key-value pair）是指在计算机科学中用来存储和表示数据的一种结构。它由两部分组成：键（key）和值（value）。键是一个唯一的标识符，用来定位和访问值；值是与键相关联的数据。例如，一个简单的键值对可以表示一个人的姓名和年龄：键是“姓名”，值是“张三”；键是“年龄”，值是“25”。
- 删除节点：可以删除二叉搜索树中的一个节点。
void TestBSTree() { BSTree dict; dict.Insert("insert", "插入"); dict.Insert("erase", "删除"); dict.Insert("select", "查找"); dict.Insert("sort", "排序"); //删除节点 dict.Erase("insert"); }- 查找节点：可以根据给定的值，在二叉搜索树中查找对应的节点。
void TestBSTree() { BSTree dict; dict.Insert("insert", "插入"); dict.Insert("erase", "删除"); dict.Insert("select", "查找"); dict.Insert("sort", "排序"); dict.Erase("insert"); //查找节点 cout_value BSTree //键值对 K _key; V _value; //左右子节点 struct BSTreeNode* _left; struct BSTreeNode* _right; //默认构造 BSTreeNode(const K& key = K(), const V& value = V()) :_key(key) ,_value(value) ,_left(nullptr) ,_right(nullptr) {} }; typedef BSTreeNode BSTree>str) { auto ret = dict.Find(str); if (ret) { cout cout "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" }; // 统计水果出现的次 BSTree auto ret = countTree.Find(str); if (ret == NULL) { countTree.Insert(str, 1); } else { ret-_value++; } } countTree.InOrder(); } //创建新节点 Node* newnode = new Node(key, value); //当二叉搜索树为空时 if (_root == nullptr) { _root = newnode; return true; } //二叉搜索树不为空 Node* cur= _root; Node* parent = _root;//记录父节点 //遍历节点找到插入位置 while (cur!= nullptr) { if (cur-_key key) { parent = cur; cur= cur-_left; } else if (key cur->_key) { parent = cur; cur= cur->_right; } else { //相等时，插入失败 return false; } } //判断是插入parent节点的左节点还是右节点 if(key>parent->_key) { parent->_right = newnode; } else { parent->_left = newnode; } return true; }因为二叉搜索树的性质，所以我们只需要比较节点的_key值即可，如果插入的节点的_key值比当前节点大就往当前节点的右子树寻找，反正就往左子树寻找合适的位置，如果相等就插入失败，返回false，因为这里的二叉搜索树不能存储相同的节点。
其次，找到合适位置后，我们还需要记录该位置的父节点，一遍将新节点与二叉搜索树链接在一起，有了插入位置的父节点，然后判断是插入左边还是右边即可完成插入，返回true。
✨查找函数Find()
查找函数其实在插入函数时确定新节点插入的位置就已经实现了类似的逻辑，不同的是如果插入时找到相同的节点则插入失败，而查找时找到相同的节点则查找成功，返回该节点的指针即可。
Node* Find(const K& key) { Node* cur= _root; while (cur!= nullptr) { if (cur->_key > key) { cur= cur->_left; } else if (key > cur->_key) { cur= cur->_right; } else { //相等时，找到了 return cur; } } //这里表示没找到 return nullptr; }这里使用循环遍历二叉搜索树来查找，当root不为空并且还没有找到时就会一直查找，而当root为空并且还没有找到此时就可以返回空指针，表示当前二叉搜索树不存在要查找的节点。
✨删除函数Erase()
删除函数的逻辑较为复杂一些，首先要查找到删除的节点，没有找到就返回False，如果找到，那么我们需要根据该节点的位置，或者说该节点有几个子节点来实现不同的删除逻辑。
如果被删除的节点没有子节点或是只有一个子节点，都比较容易解决只有把父节点指向该节点的子节点即可，如果没有子节点，则让父节点指向空即可，所以一个节点和没有节点的情况可以综合起来考虑，上述代码为了逻辑清晰分开考虑了，大家也可以根据自己的想法选择。
如果有两个子节点，删除该节点，那他的两个孩子该怎么办呢😱，所以我们应该从其右子树所有节点中选择最小的那一个minright节点替代被删除的节点root，这样替代后，左子树的所有节点依然小于minright，右子树的所有节点依然大于minright，满足二叉搜索树的性质。当然也可以选择左子树的最大节点maxleft来替代root。
替代可以选择交换节点内部的键值也可以直接交换节点的指针，交换键值较容易一些，这里选择交换键值。
bool Erase(const K& key) { //没有节点 if (_root == nullptr) { return false; } //先找到，再删除释放 Node* cur = _root; Node* parent = _root;//记录父节点 while (cur != nullptr) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { //找到，判断要被删除的节点有几个子节点 //1.没有子节点 if (cur->_left == nullptr && cur->_right == nullptr) { //判断该节点是在父节点的左边还是右边 if (parent->_key > cur->_key) { //在左边 parent->_left = nullptr; delete cur; } else if(cur->_key > parent->_key) { //在右边 parent->_right = nullptr; delete cur; } else { //就是根节点 delete cur; _root = nullptr; } } //2.只有一个节点 else if (cur->_right == nullptr) { //先看只有左节点的情况 //判断该节点是在父节点的左边还是右边 if (parent->_key > cur->_key) { //在左边 parent->_left = cur->_left; delete cur; } else if(cur->_key > parent->_key) { //在右边 parent->_right = cur->_left; delete cur; } else { //根节点 _root = cur->_left; delete cur; } } //2.只有一个节点 else if (cur->_left == nullptr) { //只有右节点的情况 //判断该节点是在父节点的左边还是右边 if (parent->_key > cur->_key) { //在左边 parent->_left = cur->_right; delete cur; } else if(cur->_key > parent->_key) { //在右边 parent->_right = cur->_right; delete cur; } else { //根节点 _root = cur->_right; delete cur; } } //3.有两个节点的情况 else { //先找右边最小的值交换 Node* minright = cur->_right; Node* pminright = cur;//记录父节点 while (minright->_left) { Node* pminright = minright;//记录父节点 minright = minright->_left; } //找到后,将minright节点的位置删除 if (pminright->_right == minright) { pminright->_right = minright->_right; } else { pminright->_left = minright->_right; } //交换节点的值即可 cur->_key = minright->_key; cur->_value = minright->_value; delete minright; } return true; } } //没找到，删除失败 return false; }删除同样需要将删除的节点的父节点与子节点链接起来，所以需要一个parent指针来记录删除节点的父节点，当然如果父节点就是自己，那么表示删除的是根节点，这时我们又要另外考虑。
✨中序遍历InOrder()
中序遍历就可以使用我们学习二叉树时的递归来实现，非常简单。
void InOrder() { _InOrder(_root); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout _key _Order(_root); } private: void _Order(Node* root) { if (root == nullptr) { return; } _Order(root-_left); _Order(root->_right); delete root; }4.二叉搜索树的应用
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
void TestBSTree() { BSTree dict; dict.Insert("insert", "插入"); dict.Insert("erase", "删除"); dict.Insert("select", "查找"); dict.Insert("sort", "排序"); //dict.InOrder(); string str; while (cin >> str) { auto ret = dict.Find(str); if (ret) { cout cout string strs[] = { "left", "left", "up", "down", "left", "right", "left", "up", "right" }; // 统计单词出现的次数 BSTree auto ret = countTree.Find(str); if (ret == NULL) { countTree.Insert(str, 1); } else { ret-_value++; } } countTree.InOrder(); }
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
- 查找节点：可以根据给定的值，在二叉搜索树中查找对应的节点。
- 删除节点：可以删除二叉搜索树中的一个节点。
- 插入节点：可以将一个新节点插入到二叉搜索树中。
