1 搜索二叉树的定义
在二叉树的定义的基础上，在加上以下两种特征的树就叫做二叉搜索树：
1️⃣任何一棵子树的左节点的值都要大于根节点的值
2️⃣任何一棵子树的右节点都要小于根节点的值
所以二叉搜索树的中序遍历一定是有序的！
2 搜索二叉树的实现
我们需要一个节点，以下是节点模块
template<class K> struct BSTreeNode { typedef BSTreeNode<K> Node; K _val; Node* _left; Node* _right; BSTreeNode(const K& val = K()) :_val(val) ,_left(nullptr) ,_right(nullptr) {} };
我们再来定义一个二叉搜索树的类
template<class K> class BinarysearchTree { public: typedef BSTreeNode<K> Node; bool FindK(const K& key)(); //插入 bool Insert(const K& key)(); //删除 bool erase(const K& key)(); private: Node* _root = nullptr; };
2.1 查找函数
bool FindK(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_val) { cur = cur->_right; } else if (key < cur->_val) { cur = cur->_left; } else { return true; } } return false; }
2.2 插入操作
//插入 bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (key > cur->_val) { parent = cur; cur = cur->_right; } else if (key < cur->_val) { parent = cur; cur = cur->_left; } else { return false; } } if (key > parent->_val) { parent->_right = new Node(key); } else { parent->_left = new Node(key); } return true; }
2.3 删除操作
和查找一样，首先就是要找到所要删除节点的位置！
2.3.1 左为空
如果删除的节点是左为空的节点，此时就会有以下三种示意图的情况
2.3.2 右为空
如果删除的节点是右为空的节点，此时也会有三种情况，如下图所示：
2.3.3 左右都不为空
如果删除的节点是左右都不为空的节点，此时就需要去右子树中寻找到最小值（也可以去左子树中找到最大值），进行交换，然后进行删除
完整的实现代码如下：
//删除 bool erase(const K& key) { Node* cur = _root; Node* curParent = cur; while (cur) { if (key > cur->_val) { curParent = cur; cur = cur->_right; } else if (key < cur->_val) { curParent = cur; cur = cur->_left; } else { if (cur->_left == nullptr) { if (_root->_left == nullptr) { _root = _root->_right; return true; } if (cur == curParent->_left) { curParent->_left = cur->_right; } else { curParent->_right = cur->_right; } delete cur; return true; } else if (cur->_right == nullptr) { if (_root->_right == nullptr) { _root = _root->_left; return true; } if (cur == curParent->_left) { curParent->_left = cur->_left; } else { curParent->_right = cur->_left; } delete cur; return true; } else { Node* curNext= cur->_right; curParent = cur; while (curNext->_left) { cur = curNext; curNext = curNext->_left; } curParent->_val = curNext->_val; if (cur->_right == curNext) { cur->_right = curNext->_right; } else { cur->_left = curNext->_right; } delete curNext; return true; } } } return false; }
