【C++】——二叉树搜索树

二叉搜索树的概念

1. 左子树上所有节点的值都小于等于根节点的值，
   右子树上所有节点的值都大于等于根节点的值
2. 左右子树也分别为二叉树
3. 二叉搜索树中可以插入相等的值也可以插入不相等的值，具体看使用场景定义

二叉搜索树基本操作

1. 插入节点

1. 新节点和根节点进行比较
2. 如果要插入的值小于当前节点的值，则移动到左子节点
   如果要插入的值大于当前节点的值，则移动到右子节点
3. 重复上述过程，直到找到一个空位置，然后在该位置插入新节点

2. 查找节点

1. 从根节点开始比较要查找的值和当前值
2. 如果要查找的值小于当前节点的值，则移动到当前节点的左子节点
   如果要查找的值大于当前节点的值，则移动到当前节点的右子节点
3. 重复上述过程， 如果要查找的值等于当前节点的值，则返回当前节点，查找成功

3. 删除节点

1. 删除的节点是叶子节点：直接删除该节点
2. 删除的节点只有一个子节点：将其子节点替换到当前该节点
3. 删除的节点有两个子节点：找到该节点右子树中的最小节点（或左子树中的最大节点），将其值替换到该节点的位置，然后删除该最小节点

二叉搜索树的实现

emplate<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};template<class K>
class BSTree
{//typedef BSTNode<K> Node;using Node = BSTNode<K>;
public:bool Insert(const K& key){if (_root == nullptr) // 如果数为空，直接插入{_root = new Node(key);return true;}Node* parent = nullptr; // 记录父亲，等会才知道插入位置Node* cur = _root; // 从头结点开始对比while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(key);if (key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}elsereturn true;}return false;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur) // 先遍历找到要删除的节点{if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else  {// 删除的节点只有一个子节点if (cur->_left == nullptr) // 左子树为空{if (cur == _root) // 如果左子树空并且要删除的节点就是根节点，那么右子树就成为新的根 {_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if(cur->_right == nullptr)// 右子树为空{if (cur == _root) // 如果右子树为空并且要删除的节点就是根节点，那么左子树就成为新的根{_root = cur->_left;}else{if (parent->_left = cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else // 左右子树都不为空(找到该节点右子树中的最小节点（或左子树中的最大节点），将其值替换到该节点的位置，然后删除该最小节点){Node* replaceparent = cur;Node* replace = cur->_right;while (replace->_left) {replaceparent = replace;replace = replace->_left;}cur->_key = replace->_key;if(replaceparent->_left == replace) // 如果被替换的是左节点replaceparent->_left = replace->_right;elsereplaceparent->_right = replace->_right; // 如果被替换的是右节点，例如：删除的是根，并且根的右节点没有左节点了delete replace;}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);}Node* _root = nullptr;
};

二叉搜索树key和key/value

namespace key_value
{template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};// Binary Search Tree// Key/valuetemplate<class K, class V>class BSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K, V>;public:// 强制生成构造BSTree() = default;BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree tmp){swap(_root, tmp._root);return *this;}~BSTree(){Destroy(_root);_root = nullptr;}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 (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{// 右为空if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}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 << ":" << root->_value << endl;_InOrder(root->_right);}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, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};
}