二叉搜索树(超详细+通俗易懂)

二叉搜索树定义:

二叉搜索树又被称为二叉排序树/二叉搜索树，为什么会被起这样的名字呢？我们先来看一张二叉搜索树的图片
在这里插入图片描述
这张图片里面的树就是二叉搜素树，那么二叉树有什么性质呢？我们从图中可以发现，每一个子树都是左节点<根节点<右节点，所以对于二叉搜索树的每一个节点来说，若它的左子树不为空，则它的左子树所有节点的值都小于根节点的值，若它的右子树不为空，则它的右子树所有节点的值都大于根节点的值。它的左右子树也满足二叉搜索树的性质。

二叉搜索树实现

1.创建和初始化:

我们看了上面二叉搜索树的图片后，我们知道二叉树需要有指向左右子树的结点，还有val值，初始化我们需要先把指向左右子树的指针指向空，再给个值。

//1.结点是公有的
template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;//构造函数BSTreeNode(const K& key):_left(nullptr): _right(nullptr): _key(key){};
};

2.插入(二叉搜索树插入结点时，不能破坏二叉搜索树的性质)

插入结点有两种情况:
1.二叉搜索树为空，插入的结点直接为根结点
在这里插入图片描述
2.二叉搜索树不为空，如果需要插入结点，那么需要先查找到需要插入的位置，再插入新结点。

template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://二叉搜索树的插入bool Insert(const K& key){//如果树为空，就先new出一个新的结点//再把这个结点给根结点//返回trueif (_root == nullptr){_root = new Node(key);return true;}//如果树不为空//parent结点是为了寻找cur的父亲结点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;}//在需要插入的位置new出一个结点cur = new Node(key);//再把parent和cur结点链接起来//比较插入的值和根结点的值if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}}
private://创建一个指向根结点的指针Node* _root = nullptr;
};

3.查找：

在这里插入图片描述

//二叉搜索树的查找
bool Find(const K& key)
{//从根结点开始查找Node* cur = _root;while (cur){//如果需要查找的结点大于根结点，那么就往根结点的右子树查找if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn true;}//找不到return false;
}

4.删除(二叉搜索树删除结点时，不能破坏二叉搜索树的性质)

如果需要删除的结点不在树中，那么就无需删除，如果需要删除的结点在树中，那么需要分为以下四种情况讨论
(1)没有左右结点的结点的删除(可以归类到左子树为空/右子树为空的情况)

(2)有左子节点没有右子节点的结点的删除
在这里插入图片描述

(3)有右子节点没有左子节点的结点的删除
在这里插入图片描述

(4)有左右结点的结点的删除

在这里插入图片描述

//4.二叉搜索树结点的删除
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;//先查找需要删除的结点的位置while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{//开始删除//1.当cur的右子结点为空if (cur->_left == nullptr){//如果是根结点//直接指向空if (cur == _root)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;}//2.当cur的左子结点为空else if (cur->_left == nullptr){if (cur == _root)_root = cur->_left;else{if (cur == parent->_right)parent->_right = cur->_right;elseparent->_left = cur->_right;}}//3.当cur的左右结点不为空else{//有右子树的最小结点和根结点互换Node* rightMin = _root->_right;Node* rightMinParent = cur;//先找到右子树最小结点while (rightMin->_left){rightMinParent = rightMin;//不断往左寻找rightMin = rightMin->_left;}//覆盖掉根结点cur->_key = rightMin->_key;//删除rightMin结点//rightMin结点的右子结点可能不为空if (parent->_left = rightMin)parent->_left = rightMin->_right;elseparent->_right = rightMin->_right;//再删除掉rightMindelete rightMin;}return true;}}//找不到return false;
}

总结

#include <iostream>
using namespace std;
//1.结点是公有的
template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;//构造函数BSTreeNode(const K& key):_left(nullptr): _right(nullptr): _key(key){};
};
template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://二叉搜索树的插入bool Insert(const K& key){//如果树为空，就先new出一个新的结点//再把这个结点给根结点//返回trueif (_root == nullptr){_root = new Node(key);return true;}//如果树不为空//parent结点是为了寻找cur的父亲结点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;}//在需要插入的位置new出一个结点cur = new Node(key);//再把parent和cur结点链接起来//比较插入的值和根结点的值if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}}//二叉搜索树的查找bool Find(const K& key){//从根结点开始查找Node* cur = _root;while (cur){//如果需要查找的结点大于根结点，那么就往根结点的右子树查找if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn true;}//找不到return false;}//4.二叉搜索树结点的删除bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;//先查找需要删除的结点的位置while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{//开始删除//1.当cur的右子结点为空if (cur->_left == nullptr){//如果是根结点//直接指向空if (cur == _root)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;}//2.当cur的左子结点为空else if (cur->_left == nullptr){if (cur == _root)_root = cur->_left;else{if (cur == parent->_right)parent->_right = cur->_right;elseparent->_left = cur->_right;}}//3.当cur的左右结点不为空else{//有右子树的最小结点和根结点互换Node* rightMin = _root->_right;Node* rightMinParent = cur;//先找到右子树最小结点while (rightMin->_left){rightMinParent = rightMin;//不断往左寻找rightMin = rightMin->_left;}//覆盖掉根结点cur->_key = rightMin->_key;//删除rightMin结点//rightMin结点的右子结点可能不为空if (parent->_left = rightMin)parent->_left = rightMin->_right;elseparent->_right = rightMin->_right;//再删除掉rightMindelete rightMin;}return true;}}//找不到return false;}
private://创建一个指向根结点的指针Node* _root = nullptr;
};