【C++】二叉树进阶之二叉搜索树（上） https://developer.aliyun.com/article/1565578
🌙二叉搜索树应用场景
1.K模型：K模型即只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值。
比如： 给一个单词 word，判断该单词是否拼写正确，具体方法如下：
- 以词库中所有单词集合中的每个单词作为key，构造一棵二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2.KV模型：每一个关键码 key ，都有与之对应的值 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; } 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->_right) { parent->_right = cur->_right; } else { parent->_left = cur->_right; } } delete cur; return true; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_right) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } delete cur; return true; } else { // 替换法 Node* rightMinParent = cur; Node* rightMin = cur->_right; while (rightMin->_left) { rightMinParent = rightMin; rightMin = rightMin->_left; } cur->_key = rightMin->_key; if (rightMin == rightMinParent->_left) rightMinParent->_left = rightMin->_right; else rightMinParent->_right = rightMin->_right; delete rightMin; return true; } } } return false; } void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } private: Node* _root = nullptr; };
🌙全部代码
namespace lyk { // 对每个结点初始化 template<class K> struct BSTreeNode { typedef BSTreeNode<K> Node; // 重命名 Node* _left; // 左子树 Node* _right; // 右子树 K _key; // 二叉搜索树节点元素的值 BSTreeNode(const K& key) // 初始化列表，成员变量初始化 :_left(nullptr) ,_right(nullptr) ,_key(key) {} }; / // 二叉搜索树功能基本实现 template<class K> class BSTree { typedef BSTreeNode<K> Node; // 重命名 public: // 强制生成默认构造函数 BSTree() = default; // 拷贝构造 BSTree(const BSTree<K>& t) { _root = Copy(t.root); // 调用拷贝构造 } // 赋值运算重载 BSTree<K>& operator=(BSTree<K> t) { swap(_root, t._root); return *this; } // 析构函数 ~BSTree() { Destroy(_root); // 调用析构函数 } // 插入结点 bool Insert(const K& key) { if (_root == nullptr) // 如果没有结点 { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) // 开始插入 { if (cur->_key < key) // 比它小走左子树 { parent = cur; cut = cur->_left; } 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 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 true; } } return false; } // 删除节点 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->_right) { parent->_right = cur->_right; } else { parent->_left = cur->_right; } } delete cur; return true; } else if (cur->_right == nullptr) // 第二种情况 { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_right) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } delete cur; return true; } else // 第三种情况 { // 替换法 Node* rightMinParent = cur; Node* rightMin = cur->_right; while (rightMin->_left) { rightMinParent = rightMin; rightMin = rightMin->_left; } cur->_key = rightMin->_key; if (rightMin == rightMinParent->_left) rightMinParent->_left = rightMin->_right; else rightMinParent->_right = rightMin->_right; delete rightMin; return true; } } } return false; } void InOrder() { _InOrder(_root); cout << endl; } // 这样方便调用 bool FindR(const K& key) { return _FindR(_root, key); } bool InsertR(const K& key) { return _InsertR(_root, key); } bool EraseR(const K& key) { return _EraseR(_root, key); } private: // 析构函数 void Destroy(Node* root) // 采用递归的形式 { if (root == nullptr) return; Destroy(root->_left); Destroy(root->right); delete root; } // 拷贝构造 Node* Copy(Node* root) { if (root == nullptr) return nullptr; Node* newRoot = new Node(root->_key); // 创建一个节点 newRoot->_left = Copy(root->left); // 拷贝左子树 newRoot->_right = Copy(root->_right); // 拷贝右子树 return newRoot; // 返回根 } // 递归版本 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; if (root->_right == nullptr) { root = root->_left; } else if (root->_left == nullptr) { root = root->_right; } else { Node* rightMin = root->_right; while (rightMin->_left) { rightMin = rightMin->_left; } swap(root->_key, rightMin->_key); return _EraseR(root->_right, key); } delete del; return true; } } // 递归版本 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; } } // 中序遍历 void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } private: Node* _root = nullptr }; } namespace key_value { template<class K, class V> struct BSTreeNode { typedef BSTreeNode<K, V> Node; Node* _left; Node* _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; } 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->_right) { parent->_right = cur->_right; } else { parent->_left = cur->_right; } } delete cur; return true; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_right) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } delete cur; return true; } else { // 替换法 Node* rightMinParent = cur; Node* rightMin = cur->_right; while (rightMin->_left) { rightMinParent = rightMin; rightMin = rightMin->_left; } cur->_key = rightMin->_key; if (rightMin == rightMinParent->_left) rightMinParent->_left = rightMin->_right; else rightMinParent->_right = rightMin->_right; delete rightMin; return true; } } } return false; } void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } private: Node* _root = nullptr; }; }
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
