查找操作（递归）
因为查找操作也是需要用到根节点的，所以递归的查找操作也是采用子函数的方式来实现。
public: bool FindR(const K& key) { return _FindR(_root, key); } private: bool _FindR(Node* root, const K& key) { if (root == nullptr) return false; if (root->_key < key) // 当前节点的值比要查找的值小,则到右子树中找 return _FindR(root->_right, key); else if (root->_key > key) // 当前节点的值比要查找的值大,则到左子树中找 return _FindR(root->_left, key); else return true; }
插入操作（递归）
public: bool InsertR(const K& key) { return _InsertR(_root, key); } private: bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) return _InsertR(root->_right, key); else if (root->_key > key) return _InsertR(root->_left, key); else return false; }
注：_InsertR 函数的Node*&在插入节点时起作用，root是其父亲的左指针或者右指针的别名，所以root = new Node(key)就可以实现将新插入节点和父节点链接起来。当树为空时，上面的代码也能实现插入节点。
删除操作（递归）
public: bool EraseR(const K& key) { return _EraseR(_root, key); } private: bool _EraseR(Node*& root, const K& key) { if (root == nullptr) return false; // 删除失败 if (root->_key < key) return _EraseR(root->_right, key); else if(root->_key > key) return _EraseR(root->_left, key); else { Node* del = root; // 记录要删除的节点 // 此时root是左指针或者右指针的别名 if (root->_left == nullptr) root = root->_right; else if (root->_right == nullptr) root = root->_left; else { // 找右子树的最左节点进行替换删除 Node* min = root->_right; while (min->_left) { min = min->_left; } swap(min->_key, root->_key); //return Erase(key); // 错的,因为树的结构已经该变了 return _EraseR(root->_right, key); //调用自己进行删除 } delete del; return true; } }
注：引用在删除时才会起作用，因为此时root是其父节点左指针或者右指针的别名，root = root->_left或者root = root->_right就可以改变父节点左指针或右指针的指向。当要删除的节点有左右孩子时，需要找到右子树的最左节点（注：也可以找左子树的最右节点）。找到后，进行值交换将替换节点的值改为key，最后调用_EraseR(root->_right, key)删除替换节点即可完成删除。以上代码对于删除节点为根节点且没有左子树或者右子树的特殊情况，也能完成删除。
递归插入删除操作演示
析构函数
树的销毁是通过后序遍历的顺序来销毁的，因为不能先销毁根节点。
public: ~BSTree() { _Destory(_root); } private: void _Destory(Node*& root) { if (root == nullptr) return; _Destory(root->_left); _Destory(root->_right); delete root; root = nullptr; }
拷贝构造
public: // 构造函数会走初始化列表,将根节点初始化为nullptr BSTree() {} // C++11的用法:强制编译器生成默认的构造 // BSTree() = default; BSTree(const BSTree<K>& t) { _root = _Copy(t._root); } private: Node* _Copy(Node* root) { if (root == nullptr) return nullptr; // 前序遍历拷贝二叉搜索树 Node* copyRoot = new Node(root->_key); // 先构造根 copyRoot->_left = _Copy(root->_left); // 再构造左子树 copyRoot->_right = _Copy(root->_right); // 最后构造右子树 return copyRoot; } Node* _Copy(Node* root) { if (root == nullptr) return nullptr; // 后序遍历拷贝二叉搜索树 Node* left = _Copy(root->_left); // 先构造左子树 Node* right = _Copy(root->_right); // 再构造右子树 Node* copyRoot = new Node(root->_key); // 最后构造根 copyRoot->_left = left; copyRoot->_right = right; return copyRoot; } private: Node* _root = nullptr;
赋值运算符重载
BSTree<K>& operator=(BSTree<K> t) { swap(_root, t._root); return *this; }
因为传值传参会存在拷贝构造，所以只需要交换两个二叉搜索树的根节点即可。
拷贝构造和赋值运算符重载测试
完整代码
#pragma once template <class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) : _left(nullptr) , _right(nullptr) , _key(key) {} }; //class BinarySearchTree template <class K> class BSTree { public: typedef BSTreeNode<K> Node; BSTree() {} BSTree(const BSTree<K>& t) { _root = _Copy(t._root); } BSTree<K>& operator=(BSTree<K> t) { swap(_root, t._root); return *this; } ~BSTree() { _Destory(_root); } bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr; 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 Node(key); // 判断从哪边插入节点 if (parent->_key < key) // 从右边插入节点 parent->_right = cur; else parent->_left = cur; return true; // 插入成功 } bool InsertR(const K& key) { return _InsertR(_root, key); } bool Find(const K& key) { if (_root == nullptr) return false; 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; // 没找到 } bool FindR(const K& key) { return _FindR(_root, key); } bool Erase(const K& key) { Node* parent = nullptr; 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->_left == nullptr) // 待删除节点没有左孩子 { if (cur == _root) // 待删除节点为根节点 { _root = cur->_right; } else { if (cur == parent->_left) // 删除节点在父节点的左边 parent->_left = cur->_right; else // 删除节点在父节点的右边 parent->_right = cur->_right; } delete cur; cur = nullptr; // 可不写 } 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* minParent = cur; // minParent不能设置为nullptr Node* min = cur->_right; while (min->_left) { minParent = min; min = min->_left; } swap(cur->_key, min->_key); // 因为替换节点是右子树的最小节点,没有左孩子 if (minParent->_left == min) // 替换节点在父节点的左边 minParent->_left = min->_right; else minParent->_right = min->_right; delete min; } return true; } } return false; // 删除失败 } bool EraseR(const K& key) { return _EraseR(_root, key); } void Inorder() { _Inorder(_root); cout << endl; } private: Node* _root = nullptr; void _Inorder(Node* root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_key << " "; _Inorder(root->_right); } bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) return _InsertR(root->_right, key); else if (root->_key > key) return _InsertR(root->_left, key); else return false; } bool _FindR(Node* root, const K& key) { if (root == nullptr) return false; if (root->_key < key) // 当前节点的值比要查找的值小,则到右子树中找 return _FindR(root->_right, key); else if (root->_key > key) // 当前节点的值比要查找的值大,则到左子树中找 return _FindR(root->_left, key); else return true; } bool _EraseR(Node*& root, const K& key) { if (root == nullptr) return false; // 删除失败 if (root->_key < key) return _EraseR(root->_right, key); else if (root->_key > key) return _EraseR(root->_left, key); else { Node* del = root; // 记录要删除的节点 // 此时root是左指针或者右指针的别名 if (root->_left == nullptr) root = root->_right; else if (root->_right == nullptr) root = root->_left; else { // 找右子树的最左节点进行替换删除 Node* min = root->_right; while (min->_left) { min = min->_left; } swap(min->_key, root->_key); //return Erase(key); // 错的,因为树的结构已经该变了 return _EraseR(root->_right, key); } delete del; return true; } } void _Destory(Node*& root) { if (root == nullptr) return; _Destory(root->_left); _Destory(root->_right); delete root; root = nullptr; } Node* _Copy(Node* root) { if (root == nullptr) return nullptr; // 前序遍历拷贝二叉搜索树 Node* copyRoot = new Node(root->_key); copyRoot->_left = _Copy(root->_left); copyRoot->_right = _Copy(root->_right); return copyRoot; } //Node* _Copy(Node* root) //{ // if (root == nullptr) // return nullptr; // // 后序遍历拷贝二叉搜索树 // Node* left = _Copy(root->_left); // Node* right = _Copy(root->_right); // Node* copyRoot = new Node(root->_key); // copyRoot->_left = left; // copyRoot->_right = right; // return copyRoot; //} };
👉二叉搜索树的性能分析👈
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
二叉搜索树的增删查的时间复杂度为O(h)，h为树的高低。最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为log N \log NlogN。最差情况下，二叉搜索树退化为单支树(或者类似单支)，此时h == N，N为节点的个数。
如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的 AVL 树和红黑树就可以上场了。
👉二叉搜索树的应用👈
Key 模型：Key 模型即只有 Key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值。
- 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为 Key，构建一棵二叉搜索树。
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
KV模型：每一个关键码 Key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文 <word, chinese> 就构成一种键值对；
再比如统计水果次数，统计成功后，给定水果名就可快速找到其出现的次数，水果与其出现次数就是 <fruit, count> 就构成一种键值对。
KeyValue 模型
namespace KeyValue { template<class K, class V> struct BSTreeNode { BSTreeNode<K, V>* _left; BSTreeNode<K, V>* _right; K _key; V _value; BSTreeNode(const K& key, const V& value) :_left(nullptr) , _right(nullptr) , _key(key) , _value(value) {} }; template<class K, class V> class BSTree { typedef BSTreeNode<K, V> Node; public: bool Insert(const K& key, const V& value) { if (_root == nullptr) { _root = new Node(key, value); return true; } Node* parent = nullptr; 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 Node(key, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur; } } return nullptr; } void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << ":" << root->_value << endl; _InOrder(root->_right); } private: Node* _root = nullptr; }; }
注：KeyValue 模型中的 Valuer 是可以修改的，其余的操作和和 Key 模型一样。
英译中实例演示
水果出现次数实例演示
OJ 题中的应用
👉总结👈
本篇博客主要讲解了什么是搜索二叉树、模拟实现二叉搜索树、二叉搜索树的性能分析以及二叉搜索树的应用场景等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
