🌈个人主页：羽晨同学
💫个人格言:“成为自己未来的主人~”
二叉搜索树
二叉搜索树又称二叉排序树，它或者是一颗空树，或者是具有以下性质的树
- 若它的左子树不为空，则左子树上的所有节点的值都小于根节点的值。
- 若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值。
- 它的左右字数也分别为二叉搜索树。
二叉树在我们之前讲数据结构的时候完成过二叉树的实现，在二叉树中，每个节点都会指向它的左右节点，所以，我们可以先初步实现二叉搜索树当中的每个节点。
template<class K>
class 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;
public:bool Insert(const K& key);bool Find(const K& key);bool Erase(const K& key);void Inorder();
private:void _Inorder(Node* root);
private:Node* _root = nullptr;
};接下来，让我们逐步分析一下每个功能的具体实现方式。
查找
因为二叉搜索树实现插入功能需要用的查找功能，所以，我们先来实现查找这个函数。
- 从根开始查找，比根大去右边，比根小去左边
- 找到的话，返回true，找不到，返回false
bool 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 true;}}return false;}插入
- 树为空，则直接新增节点，赋值给root指针
- 树不为空，则查找插入的位置，插入新节点。
bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}在这个当中，我们要记得定义一个父亲节点，便于找到后进行插入操作。
删除
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{//删除//0-1个孩子的情况if (cur->_left = nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}elseparent->_right = cur->right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}elseparent->_left = cur->_left;}delete cur;return true;}else{//两个孩子的情况//右子树的最小节点作为替代节点Node* rightMinp = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinp = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinp->_left = rightMin)rightMinp->_left = rightMin->_right;elserightMinp->_right - rightMin->_right;delete rightMin;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);}好了，本次的文章就到这里了，我们下次再见。
