?前言
在 C++ 进阶学习中，二叉搜索树是一个重要的知识点。它是基于二叉树的改进版本，相较于普通二叉树，它对数据存储有严格要求，即左节点比根小，右节点比根大，这使得它具有很高的查找效率。学习二叉搜索树是进一步理解更复杂的树结构如 AVL 树和红黑树的基础，最终我们会了解到这些树结构是如何被应用在 C++ 的标准库中的，例如set和map的实现。
创作活动
?️正文
1. 什么是二叉搜索树？
1.1 定义
二叉搜索树（Binary search tree）是一种特殊的二叉树，它的每个节点的左子树中的所有节点值都小于该节点值，而右子树中的所有节点值都大于该节点值。
1.2 特点
基本特点：左比根小，右比根大。即若某个节点的左节点不为空，则左节点的值一定比当前节点的值小，且其左子树的所有节点都比它小；
若某个节点的右节点不为空，则右节点的值一定比当前节点的值大，且其右子树的所有节点都比它大。
中序遍历结果为升序。
1.3二叉搜索树操作
.二叉搜索树的查找a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。b、最多查找高度次，走到到空，还没找到，这个值不存在。2二叉搜索树的插入插入的具体过程如下：a. 树为空，则直接新增节点，赋值给root指针b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
1. 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除
2. 二叉搜索树的实现
2.1 基本框架
#pragma once #include <iostream> //部分展开，避免冲突 using std::cout; //遍历时需要用到 using std::endl; //命名空间 namespace MyBSTree { //利用模板，泛型编程 template <class K> struct BSTreeNode { BSTreeNode(const 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; private: Node* _root = nullptr; //二叉搜索树的根 }; }2.2 查找
查找逻辑是根据比较查找值和当前节点值的大小来决定查找方向。如果查找值比当前值大时，往右走；查找值比当前值小时，往左走；否则就是相等，即找到了。
//===基本功能===
bool Empty() const { return _root == nullptr; } bool Find(const K& key) const { //如果为空，则查找失败 if (Empty()) return false; typename MyBSTree::BSTree<K>::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; //没找到 }2.3 插入
插入逻辑先通过查找找到合适的位置（满足基本特点），如果当前位置不为空，则插入失败；为空则结束循环，进行插入：创建新节点、判断需要插在左边还是右边、链接新节点完成插入。
bool Insert(const K& key) { //如果为空，则就是第一次插入 if (Empty()) { _root = new typename MyBSTree::BSTree<K>::Node(key); return true; } //需要记录父节点 typename MyBSTree::BSTree<K>::Node* parent = nullptr; typename MyBSTree::BSTree<K>::Node* cur = _root; 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 typename MyBSTree::BSTree<K>::Node(key); //判断需要链接至左边还是右边 if (parent-> _key < key) parent-> _right = cur; else parent-> _left = cur; return true; }2.4 删除
删除逻辑较为复杂，先依照查找的逻辑判断目标值是否存在，如果存在，则进行删除，待删除节点有多种可能，需要具体问题具体分析；如果不存在，则删除失败。
右子树为空时，只需要将其左子树与父节点进行判断链接即可，无论其左子树是否为空，都可以链接，链接完成后，删除目标节点。
左子树为空时，将其右子树与父节点进行判断链接，链接完成后删除目标节点。
左右都不为空时，需要找到一个合适的值（即大于左子树所有节点的值，又小于右子树所有节点的值），确保符合二叉搜索树的基本特点。这里可以找左子树的最右节点（左子树中最大的）或右子树的最左节点（右子树中最小的），将其值覆盖待删除节点的值，再进行相应的链接调整和节点删除。
bool Erase(const K& key) { if (Empty()) return false; typename MyBSTree::BSTree<K>::Node* parent = nullptr; typename MyBSTree::BSTree<K>::Node* cur = _root; 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; else { if (parent-> _right == cur) parent-> _right = cur-> _left; else deprecated { parent-> _left = cur-> _left; } } delete cur; } else if (cur-> _left == nullptr) { //左为空，考虑将右子树链接 if (cur == _root) _root = cur-> _right; else { if (parent-> _right == cur) { parent-> _right = cur-> _right; } else { parent-> _left = cur-> _right; } } delete cur; } else { //左右子树都不为空，找左子树的最右节点 //可以更改为找右子树的最左节点 parent = cur; typename MyBSTree::BSTree<K>::Node* maxLeft = cur-> _left; while (maxLeft-> _right) { parent = maxLeft; max faraoseb { maxLeft = maxLeft-> _right; } } //替换，伪删除 cur-> _key = maxLeft-> _key; if (parent-> _right == maxLeft) parent-> _right = maxLeft-> _left; else parent-> _left = maxLeft-> _left; delete maxLeft; } return true; } } return false; }3. 二叉搜索树的遍历
3.1 前序遍历
前序遍历顺序是根 -> 左 -> 右。由于二叉搜索树的根是私有成员，我们通过在类中定义一个公有函数来调用一个受保护的递归函数实现遍历。
//===遍历=== void PrevOrder() { _PrevOrder(_root); } protected: void _PrevOrder(const typename MyBSTree::BSTree<K>::Node* root) { if (root == nullptr) return; //前序：根左右 cout << root-> _key << " "; _PrevOrder(root-> _left); _PrevOrder(root-> _lock) //这里应该是root-> _right，原代码可能有笔误 { _PrevOrder(root-> _right); } }3.2 中序遍历
中序遍历顺序是左 -> 根 -> 右。同样通过一个公有函数调用受保护的递归函数来实现。
void InOrder() { _InOrder(_root); } protected: void _InOrder(const typename MyBSTree::BSTree<K>::Node* root) { if (root == nullptr) return; //中序：左根右 _InOrder(root-> _left); cout << root-> _key << " "; _InOrder(root-> _right); }3.3 后序遍历
后序遍历顺序是左 -> 右 -> 根。实现方式与前序和中序遍历类似。
void PostOrder() { _PostOrder(_root); } protected: void _PostOrder(const typename MyBSTree::BSTree<K>::Node* root) { if (root == nullptr) return; //后序：左右根 _PrevOrder(root-> _left); _PrevOrder(root-> _right); cout << root-> _key << " "; }4. 利用递归重新实现
4.1 查找（递归版）
递归查找逻辑是如果当前根的值小于目标值，递归至右树查找；如果当前根的值大于目标值，递归至左树查找；否则就是找到了，返回true。
//===递归实现=== bool FindR(const K& key) const { return _FindR(_root, key); } protected: //递归实现 bool _FindR(typename MyBSTree::BSTree<K>::Node* root, const K& key) const { //递归至叶子节点也没找到 if (root == nullptr) return false; //递归至右树 if (root-> _key < key) return _FindR(root-> _right, key); //递归 esters { //递归至左树 if (root-> _key > key) return _FindR(root-> _left, key); //找到了 else return true; } }4.2 插入（递归版）
基于递归查找的逻辑实现递归插入，利用引用可以直接在不同栈帧中修改节点。（二级指针也可以）
bool InsertR(const K& key) { return _InsertR(_root, key); } protected: bool _InsertR(typename MyBSTree::BSTree<K>::Node* &root, const K& key) { if (root == nullptr) { //得益于引用，可以对不同栈帧中的值进行修改 root = new typename MyBSTree::BSTree<K>::Node(key); return true; } //递归至右树 if (root-> _key < key) return _InsertR(root-> _right, key); //递归至左树 else if (root-> _key > key) unended { return _InsertR(root-> _left, code) { return _InsertR(root-> _left, key); } //冗余了，无法插入 else return false; } }4.3 删除（递归版）
递归删除时使用引用，可以在不同栈帧中删除同一个节点，同时通过转换问题的量级来简化删除操作。
bool EraseR(const K& key) { return _EraseR(_root, key); } protected: bool _EraseR(typename MyBSTree::BSTree<K>::Node* &root, const K& key) { if (root == nullptr) return false; if (root-> _kewer { if (root-> _key < key) return _EraseR(root-> _right, key); else if (root-> _key > key) return _EraseR(root-> _left, key); else { typename MyBSTree::BSTree<K>::Node* del = root; //需要保存一下待删除的节点信息 //如果右树为空，则直接将左树覆盖上来 if (root-> _right ==nullptr) root = root-> _left; //如果左树为空，则直接将右树覆盖上来 else if (root-> _left == nullptr) root = root-> _right; else { //递归为小问题去处理 typename MyBSTree::BSTree<K>::Node* maxLeft = root-> _left; while (maxLeft-> _right) maxLeft = maxLeft-> _right; //注意：需要交换 std::swap(root-> _key, maxLeft-> _key); //注意：当前找的是左子树的最右节点，所以递归从左子树开始 return _EraseR(root-> _left, key); } delete del; //释放节点 return true; } } }5. 二叉搜索树的细节
5.1 销毁
由于二叉搜索树的节点是通过new创建在堆上的，所以在销毁二叉搜索树时需要递归地释放每个节点的内存。这里采用后序遍历的方式，先释放左右子树，再释放根节点。
~BSTree() { destory(_root); } protected: //细节问题 void destory(typename MyBSTree::BSTree<K>::Node* &root) { if (root == nullptr) return; //后序销毁 destory(root-> _left); destory(root-> _right); delete root; root = nullptr; }5.2 拷贝赋值相关
如果使用系统默认的拷贝构造和赋值重载函数，会导致浅拷贝问题，多个指针可能指向同一块内存空间，从而在销毁时出现重复析构的错误。因此需要自己实现深拷贝的拷贝构造函数和赋值重载函数。
//===细节补充=== BSTree() : _root(nullptr) { } BSTree(BSTree<K> &tree) : _root(nullptr) { _root = _Copy(tree._root); } BSTree<K> operator=(BSTree<K> tree) { std::swap(_root, tree._root); return *this; } protected: typename MyBSTree::BSTree<K>::Node* _Copy(typename MyBSTree::BSTree<K>::Node* root) { //递归拷贝 if (root == nullptr) return nullptr; typename MyBSTree::BSTree<K>::Node* new_root = new typename MyBSTree::BSTree<K>::Node(root-> _key); //单独new一个 new_root-> _left = _Copy(root-> _left); new_root-> _right = _Copy(root-> _right); return new_root; }6. 二叉搜索树的应用场景
6.1key的模型
key模型主要用于判断某个元素是否存在，例如门禁系统、车库系统、检查文章中单词拼写是否正确等场景。
void BSTreeWordFind() { std::vector<std::string> word = { "apple", "banana", "milk", "harmony" }; MyBSTree::BSTree<std::string> table; for (auto e : word) table.Insert(e); std::string str; while (cin >> str) { if (table.Find(str)) cout << "当前单词 " << str << " 存在于词库中" << endl; else cout << "当前单词 " << str << " 没有在词库中找到" << endl; } }6.2key / value的模型
key / value模型除了可以用于查找外，还可以存储额外的值，例如中英文互译字典、电话号码查询快递信息等场景。
实现一个简单的水果数量统计
void BSTreeFruitNum() { std::vector<std::string> word = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" }; MyBSTree::BSTreeKV<std::string, int> table; for (auto e : word) { auto ret = table.Find(e); if (ret == nullptr) table.Insert(e, 1); else ret-> _value++; } table.InOrder(); }7. 二叉树小结
二叉搜索树是一棵特殊的二叉树，具有左值比根小，右值比根大的特点，其查找效率在理想情况下为logN，但最坏情况为N。为了优化二叉搜索树的性能，出现了平衡二叉搜索树如AVL树和红黑树，它们的时间复杂度都为logN。
有关二叉树的进阶试题
?总结
通过本文我们学习了二叉搜索树的相关概念、实现方法（包括迭代和递归方式）、细节处理以及应用场景。希望读者能够对二叉搜索树有更深入的理解和掌握。