二叉搜索树的实现（C++）

前言

        二叉搜索树（搜索二叉树，Binary search tree）是一种特殊的二叉树。其规则为：左子树的值一定小于等于根，右子树的值一定大于等于根，并且左右子树也为搜索二叉树。

二叉搜索树的插入

        1.若树为空，插入的数据为根节点的数据

        2.若树不为空，按照二叉搜索树的性质，判断节点的值与插入值的大小关系。若大于节点的值则往右边走。若小于节点的值则往左边走

二叉搜索树的搜索

        1.从根节点开始查找，小于节点值则往左边，大于节点值则往右边。找到就返回

        2.若遍历完都没有找到，即返回找不到

二叉搜索树的删除（重点）

        1.删除叶子节点（既没有左右孩子），直接删除然后将其父亲节点的指针赋值为nullptr

        2.删除只有一个孩子的节点，直接删除然后将孩子连接至父亲节点

        3.删除有两个孩子的节点，不能直接删除。从这个节点出发寻找左子树的最大值（既最右节点）或者右子树的最小值（既最左节点）。将找到的值的赋值给要删除的节点，然后删除我们找到的节点，这样就能保证不会破坏二叉搜索树的性质。

        补充：若删除根节点的话，要单独处理一下

代码实现

template<class K>
struct BSNode
{K _val;BSNode<K>* _left;BSNode<K>* _right;BSNode(const K& key):_val(key), _left(nullptr), _right(nullptr){ }
};template<class K>
class BSTree
{//typedef BSNode<K> Node;using Node = BSNode<K>;//新的重命名方式
public:void Insert(const K& key)//搜索二叉树的插入(不允许冗余){Node* cur = _root;if (!cur){_root = new Node(key);}else{Node* parent = cur;while (cur){if (cur->_val < key){parent = cur;cur = cur->_right;}else{parent = cur;cur = cur->_left;}}if (parent->_val < key){parent->_right = new Node(key);}else if (parent->_val > key){parent->_left = new Node(key);}elsereturn;}}bool Search(const K& key)//查找{Node* cur = _root;while (cur){if (cur->_val < key){cur = cur->_right;}else if (cur->_val > key){cur = cur->_left;}elsereturn true;}return false;}//搜索二叉树的删除void Erase(const K& key){Node* cur = _root;Node* parent = cur;//先找到相应位置while (cur){if (cur->_val < key){parent = cur;cur = cur->_right;}else if (cur->_val > key){parent = cur;cur = cur->_left;}elsebreak;}if (!cur)return;//进行删除if (!cur->_left && !cur->_right)//没有孩子{if (cur == _root)//若删除根节点{delete _root;_root = nullptr;}else{if (parent->_left == cur)parent->_left = nullptr;elseparent->_right = nullptr;delete cur;cur = nullptr;  // 显式置空}}else if (!cur->_left || !cur->_right)//有一个孩子{if (cur == _root)//若删除根节点{if (cur->_left){_root = cur->_left;delete cur;cur = nullptr;  // 显式置空}else{_root = cur->_right;delete cur;cur = nullptr;  // 显式置空}}else{if (!cur->_left){if (parent->_left == cur){parent->_left = cur->_right;delete cur;cur = nullptr;  // 显式置空}else{parent->_right = cur->_right;delete cur;cur = nullptr;  // 显式置空}}else{if (parent->_left == cur){parent->_left = cur->_left;delete cur;cur = nullptr;  // 显式置空}else{parent->_right = cur->_left;delete cur;cur = nullptr;  // 显式置空}}}}else//有两个孩子{//寻找左子树最大值（或右子树最小值）来替换curNode* Replace = cur->_left;Node* Replacep = cur;while (Replace->_right){Replacep = Replace;Replace = Replace->_right;}swap(Replace->_val, cur->_val);if(Replacep->_right == Replace)Replacep->_right = Replace->_left;elseReplacep->_left = Replace->_left;delete Replace;}}void Inorder()//中序遍历{_Inorder(_root);cout << endl;}private:void _Inorder(Node* root)//中序遍历{if (!root)return;_Inorder(root->_left);cout << root->_val<<" ";_Inorder(root->_right);}Node* _root = nullptr;
};