二叉搜索树的实现（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); } else return; } } 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; } else return 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; } else break; } if (!cur) return; //进行删除 if (!cur->_left && !cur->_right)//没有孩子 { if (cur == _root)//若删除根节点 { delete _root; _root = nullptr; } else { if (parent->_left == cur) parent->_left = nullptr; else parent->_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//有两个孩子 { //寻找左子树最大值（或右子树最小值）来替换cur Node* 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; else Replacep->_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; };