【数据结构】二叉搜索树

✨✨欢迎大家来到Celia的博客✨✨

🎉🎉创作不易，请点赞关注，多多支持哦🎉🎉

所属专栏：数据结构

个人主页：Celia's blog~

一、二叉搜索树

1.1 二叉搜索树的定义

1.2 为什么要用二叉搜索树

二、实现二叉搜索树

2.1 节点结构定义

2.2 插入函数Insert

2.3 查找函数Find

2.4 删除函数Enrase

2.4.1 特殊情况处理

2.5 遍历二叉搜索树

三、源码

一、二叉搜索树

1.1 二叉搜索树的定义

二叉搜索树是一颗二叉树，但是这颗二叉树的左右节点具有一定的要求：左子树所有的值要小于根节点的值，右子树所有的值要大于根节点的值。这样一来，当查找一个值的时候，如果比当前节点的值小，就向左遍历；如果比当前节点的值大，就向右遍历。这样的搜索模式最好的时间复杂度为logN。

1.2 为什么要用二叉搜索树

二叉搜索树的遍历方式类似于二分查找，但是二分查找的应用有三个致命的缺点：

存储数据的底层结构必须是数组。
如果有插入、删除等操作，数组需要大量挪动数据。
数组元素必须有序。

想要弥补这些缺点，就可以用到二叉搜索树，解决了存储结构的限制，插入、删除操作相对便捷，插入每一个元素时，按照一定的规则插入即可。

二、实现二叉搜索树

2.1 节点结构定义

template<class K>
class BSTNode    //每个节点的定义
{
public:K val;BSTNode<K>* left;BSTNode<K>* right;BSTNode(const K& val):val(val),left(nullptr),right(nullptr){}
};template<class K>
class BSTree    //树
{
public:typedef BSTNode<K> Node;//成员函数...
private:Node* root = nullptr;
};

2.2 插入函数Insert

在树中插入一个节点，主要分为两类：

插入的节点是第一个节点（根节点）。
插入的节点不是根节点。

我们对于第一种情况，只需要做出简单的判断即可。对于第二种情况，则需要再分为两种情况：

插入的元素如果大于当前节点，向右遍历。
插入的元素如果小于当前节点，向左遍历。

直到遍历到叶子节点后，判断插入的元素与当前叶子节点的值的大小，比节点值大，插入在右边；比节点值小，插入在左边。

//在BSTree类中：
bool Insert(const K& data)
{Node* newnode = new Node(data);if (root == nullptr){//插入的节点是根节点root = newnode;}else{//插入的节点不是根节点Node* cur = root;Node* parent = nullptr;while (cur != nullptr){if (data < cur->val){//如果小于当前节点，向左遍历parent = cur;cur = cur->left;}else if (data > cur->val){//如果大于当前节点，向右遍历parent = cur;cur = cur->right;}else{//与当前节点值相等，不做处理，当作插入失败cout << "Insert fail!" << endl;return false;}}//跳出循环时，cur的指向为空，实际上要在其父节点上插入新的节点，故需要记录父节点//重新比较父节点与新节点的值的大小关系if (data < parent->val){parent->left = newnode;}else{parent->right = newnode;}}cout << "Insert success!" << endl;return true;
}

2.3 查找函数Find

查找函数与插入函数中寻找插入节点的过程类似，只不过这次若是没有比当前节点的值大，也没有比当前节点的值小，就说明已经找到了。若是正常跳出循环，则说明没有找到。

//在BSTree类中：
bool Find(const K& data)
{if (root == nullptr){cout << "Find fail!" << endl;return false;}else{Node* cur = root;while (cur != nullptr){if (data < cur->val){cur = cur->left;}else if (data > cur->val){cur = cur->right;}else{//找到了cout << "Find success! The value is " << cur->val << endl;return true;}}//跳出循环说明没找到cout << "Find fail!" << endl;return false;}
}

2.4 删除函数Enrase

删除函数比较复杂，主要分为四类：

节点的左右孩子都为空，直接删除该节点。
节点的左孩子为空，右孩子不为空，把该节点的右孩子赋值给该节点的父节点。删除该节点。
节点的左孩子不为空，右孩子为空，把该节点的左孩子赋值给该节点的父节点。删除该节点。
节点的左右孩子都不为空，这个时候不能直接删除节点，因为该节点的左右孩子没有位置移动。这种情况下，需要特殊处理。

找到当前节点的，左子树最大值，或者右子树最小值的节点replace。
把replace节点的值赋值给当前节点。
再连接replace父节点与replace子节点。
删除replace节点。

其中，1、2、3情况可以当作一种情况处理。

图解：

2.4.1 特殊情况处理

假设找的是右子树的最小值replace，这种时候需要记录replace的父节点replaceParent。如果初始化父节点为nullptr，这种情况就会出现空指针访问错误（由于需要判断replaceParent和replace的位置关系)，所以父节点应该初始化为cur（寻找到的节点）而不是nullptr。

//在BSTree类中：
bool Enrase(const K& data)
{if (root == nullptr){cout << "Enrase fail!" << endl;return false;}else{//第1、2、3种情况当作一种处理//先寻找到该节点Node* cur = root;Node* parent = nullptr;while (cur != nullptr){if (data < cur->val){parent = cur;cur = cur->left;}else if (data > cur->val){parent = cur;cur = cur->right;}else{//找到了，分情况讨论if (cur->left == nullptr){//左边为空的情况if (parent == nullptr){//说明没有更新节点，删除的是头节点root = cur->right; //移动根指针K v = cur->val;delete cur;cout << "Enrase success! The val is " << v << endl;return true;}//这里判断的是parent和cur的关系，cur在parent的哪边//链接cur孩子节点就链接在parent的哪边if (parent->left == cur){parent->left = cur->right;}else if (parent->right == cur){parent->right = cur->right;}K v = cur->val;delete cur;cout << "Enrase success! The val is " << v << endl;return true;}else if (cur->right == nullptr){//右边为空的情况if (parent == nullptr){//说明没有更新节点，删除的是头节点root = cur->left; //移动根指针K v = cur->val;delete cur;cout << "Enrase success! The val is " << v << endl;return true;}//这里判断的是parent和cur的关系，cur在parent的哪边//链接cur孩子节点就链接在parent的哪边if (parent->left == cur){parent->left = cur->left;}else if (parent->right == cur){parent->right = cur->left;}K v = cur->val;delete cur;cout << "Enrase success! The val is " << v << endl;return true;}else{//两边都不为空的情况//先找到当前节点左子树的最大值，或者右子树的最小值//左子树最大值，左子树一直往右走//右子树最小值，右子树一直往左走Node* replace = cur->right;Node* replaceParent = cur;while (replace->left != nullptr){replaceParent = replace;replace = replace->left;}//这个时候，replace已经指向了右子树的最小值，进行赋值K v = cur->val;cur->val = replace->val;//接下来链接replace父节点和replace孩子节点//之所以分类讨论是因为有可能删除的是头节点，这种时候replaceParent//是没有刷新值的，为了避免空指针，replaceParent初始化值为cur的值//由于链接需要判断：replaceParent和replace的位置关系，决定replace//的孩子节点链接到replaceParent的哪个节点上（left / right）//需要分类讨论if (replaceParent->left == replace){replaceParent->left = replace->right;}else if (replaceParent->right == replace){replaceParent->right = replace->right;}delete replace;cout << "Enrase success! The value is " << v << endl;return true;}}}//走到这里说明没找到，无法删除cout << "Enrase fail!" << endl;return false;}
}

2.5 遍历二叉搜索树

二叉搜索树由于左子树的值都小于根节点的值，右子树都大于根节点的值，所以需要用中序遍历来打印。

public：
void InOrder()  //由于root根节点私有，外面拿不到，所以多套一层，在类中就能拿到了
{InOrder(root);cout << endl;
}
private：
void InOrder(Node* root)
{if (root == nullptr){return;}InOrder(root->left);cout << root->val << ' ';InOrder(root->right);
}

三、源码

#include<iostream>
using namespace std;template<class K>
class BSTNode
{
public:K val;BSTNode<K>* left;BSTNode<K>* right;BSTNode(const K& val):val(val),left(nullptr),right(nullptr){}
};template<class K>
class BSTree
{
public:typedef BSTNode<K> Node;bool Insert(const K& data){Node* newnode = new Node(data);if (root == nullptr){//插入的节点是根节点root = newnode;}else{//插入的节点不是根节点Node* cur = root;Node* parent = nullptr;while (cur != nullptr){if (data < cur->val){//如果小于当前节点，向左遍历parent = cur;cur = cur->left;}else if (data > cur->val){//如果大于当前节点，向右遍历parent = cur;cur = cur->right;}else{//与当前节点值相等，不做处理，当作插入失败cout << "Insert fail!" << endl;return false;}}//跳出循环时，cur的指向为空，实际上要在其父节点上插入新的节点，故需要记录父节点//重新比较父节点与新节点的值的大小关系if (data < parent->val){parent->left = newnode;}else{parent->right = newnode;}}cout << "Insert success!" << endl;return true;}bool Find(const K& data){if (root == nullptr){cout << "Find fail!" << endl;return false;}else{Node* cur = root;while (cur != nullptr){if (data < cur->val){cur = cur->left;}else if (data > cur->val){cur = cur->right;}else{//找到了cout << "Find success! The value is " << cur->val << endl;return true;}}//跳出循环说明没找到cout << "Find fail!" << endl;return false;}}bool Enrase(const K& data){if (root == nullptr){cout << "Enrase fail!" << endl;return false;}else{//第1、2、3种情况当作一种处理//先寻找到该节点Node* cur = root;Node* parent = nullptr;while (cur != nullptr){if (data < cur->val){parent = cur;cur = cur->left;}else if (data > cur->val){parent = cur;cur = cur->right;}else{//找到了，分情况讨论if (cur->left == nullptr){//左边为空的情况if (parent == nullptr){//说明没有更新节点，删除的是头节点root = cur->right; //移动根指针K v = cur->val;delete cur;cout << "Enrase success! The val is " << v << endl;return true;}//这里判断的是parent和cur的关系，cur在parent的哪边//链接cur孩子节点就链接在parent的哪边if (parent->left == cur){parent->left = cur->right;}else if (parent->right == cur){parent->right = cur->right;}K v = cur->val;delete cur;cout << "Enrase success! The val is " << v << endl;return true;}else if (cur->right == nullptr){//右边为空的情况if (parent == nullptr){//说明没有更新节点，删除的是头节点root = cur->left; //移动根指针K v = cur->val;delete cur;cout << "Enrase success! The val is " << v << endl;return true;}//这里判断的是parent和cur的关系，cur在parent的哪边//链接cur孩子节点就链接在parent的哪边if (parent->left == cur){parent->left = cur->left;}else if (parent->right == cur){parent->right = cur->left;}K v = cur->val;delete cur;cout << "Enrase success! The val is " << v << endl;return true;}else{//两边都不为空的情况//先找到当前节点左子树的最大值，或者右子树的最小值//左子树最大值，左子树一直往右走//右子树最小值，右子树一直往左走Node* replace = cur->right;Node* replaceParent = cur;while (replace->left != nullptr){replaceParent = replace;replace = replace->left;}//这个时候，replace已经指向了右子树的最小值，进行赋值K v = cur->val;cur->val = replace->val;//接下来链接replace父节点和replace孩子节点//之所以分类讨论是因为有可能删除的是头节点，这种时候replaceParent//是没有刷新值的，为了避免空指针，replaceParent初始化值为cur的值//由于链接需要判断：replaceParent和replace的位置关系，决定replace//的孩子节点链接到replaceParent的哪个节点上（left / right）//需要分类讨论if (replaceParent->left == replace){replaceParent->left = replace->right;}else if (replaceParent->right == replace){replaceParent->right = replace->right;}delete replace;cout << "Enrase success! The value is " << v << endl;return true;}}}//走到这里说明没找到，无法删除cout << "Enrase fail!" << endl;return false;}}void InOrder(){InOrder(root);cout << endl;}
private:void InOrder(Node* root){if (root == nullptr){return;}InOrder(root->left);cout << root->val << ' ';InOrder(root->right);}Node* root = nullptr;
};