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

文章目录

二叉搜索树的概念
二叉搜索树基本操作
- 1. 插入节点
- 2. 查找节点
- 3. 删除节点
二叉搜索树的实现
二叉搜索树key和key/value

二叉搜索树的概念

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

二叉搜索树基本操作

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;};
}