当前位置：首页 > news >正文

[c++高阶]二叉搜索树深度剖析

news 2024/10/31 18:53:04

1.前言

从二叉搜索树开始，后面慢慢学的AVL树，红黑树，map,set，哈希表等等都会慢慢的变得更难了，也更加难以理解了。希望大家能够坚持下去，只要坚持，就是胜利。

本章重点

着重讲解什么是二叉搜索树，二叉搜索树的定义、性质以及二叉搜索树的正删查的模拟实现。

2.二叉搜索树的概念

二叉搜索树：从中序遍历来看就是一颗有序树，即左边比我大，右边比我小。并且左子树也符合这个要求，右子树也符合这个要求。

也可以称二叉搜索树为二叉查找树，并且他也可以是一棵空树

例：如果这棵树不为空的话

由于左子树中10的右边5比10小，所以这不是一颗二叉搜索树

30的左边15比30小，15作为左子树，没有左右孩子，天然是一棵二叉搜索树，而30的右边全都比30大，且右子树以41为根的左边比其小，右边比其大。所以这棵树是一棵二叉搜索树

3.二叉搜索树的定义及性质

如何定义一棵二叉树呢？

代入如下：

//创建节点
template <class T>
struct BstreeNode
{BstreeNode<T>* left;BstreeNode<T>* right;T  val;//构造函数BstreeNode(const T& key):left(nullptr),right(nullptr),val(key){}
};

解释：二叉树由一个一个的节点组成，所以只需要定义出来了节点，再把不同的节点链接起来，那么就组成了一棵二叉树

二叉树的性质：

1.二叉搜索树在用中序遍历时，得到的值就是一个已经排好序的序列了。

例：

用中序遍历可得：1 3 4 6 7 8 10 13 14

2.二叉搜索树只支持增加，删除，查找，不支持修改。

这是因为如果一旦改动了二叉搜索树里面的某一个值，那么这棵二叉搜索树就有可能不是二叉搜索树了，只是一棵普通的二叉树。

3.二叉搜索树的时间复杂度是0(N)

如果二叉树一旦出现最坏的情况，那么就是所有的值都比根小。

例：

由于这个原因，二叉搜索树是不稳定的，所以后续很少用到二叉搜索树，更多的是使用AVL树，和红黑树。

PS：二叉搜索树中是不能够出现相同的值的，如果出现了相同的值，就默认他不是一棵二叉搜索树

4.二叉树的模拟实现

先构造地基，把基本的框架搞出来

//先构造单节点
template <class T>
struct BstreeNode
{BstreeNode<T>* left;BstreeNode<T>* right;T  val;//构造函数BstreeNode(const T& key):left(nullptr),right(nullptr),val(key){}
};//这里模拟实现二叉搜索树
template <class T>
class Bstree
{
public:typedef BstreeNode<T> Node;
private:Node* _root;
}

4.1 二叉搜索树的查找

例：

要在这一棵二叉搜索树中查找到7，查找代码如下。

迭代版本：

	bool Find(const T& key){Node* cur = _root;while (cur){if (cur->val < key)cur = cur->right;else if (cur->val > key)cur = cur->left;else if (cur->val == key)return true;}return false;}

递归版本：

bool FindR(const T& key)
{if (_FindR(_root, key)) return true;else return false;
}bool _FindR(Node* root, const T& key)
{if (root == nullptr) return false;if (root->val > key) return _FindR(root->left, key);else if (root->val < key) return _FindR(root->right, key);else return true;
}

简单来说就是总结成一句话：如果当前值比我小，我就去右子树里面找，如果当前值比我大，那我就去左子树里面找。最后的结果要么就是找到了，要么就是这棵二叉搜索树里面根本没有这个值。

4.2 二叉搜索树的插入

1.当树为空的时候，那么直接插入即可

2.如果树不为空，那么就需要先找到是具体插入在哪一个位置的后面，然后再进行插入。

例：

如果要插入一个2

代码如下：

bool Insert(const T& key)
{if (_root == nullptr){_root = new Node(key);return true;}//先找到要插入的位置Node* prev = nullptr;Node* cur = _root;while (cur){if (cur->val > key){prev = cur;cur = cur->left;}else if (cur->val < key){prev = cur;cur = cur->right;}else return false;}//到这就找到了要插入的位置cur = new Node(key);if (prev->val > key)prev->left = cur;else if (prev->val < key)prev->right = cur;return true;
}

PS：这里在找的时候，也记录了要插入的位置的前一个节点，这是因为你需要把插入的值链接到前一个节点的左边或者右边，形成一棵二叉搜索树。

4.3 二叉搜索树的删除

先判断要删除的节点是否在二叉搜索树里面，如果不在，那就返回。如果在的话，那么就有以下四种情况

1.要删除的节点左为空

2.要删除的节点右为空

3.要删除的节点左右都为空(这种情况包含在1.2两种情况里面)

4.要删除的节点左右都不为空。（这种情况就需要进行特殊处理了，找出左子树的最右值，即最大值，然后与删除的节点值进行交换，那么就转换成了删除这个左子树的最右值所在的节点的位置了。或者找出右子树的最左值，即最小值。）

代码如下：

bool Erase(const T& key)
{//1.在删除之前要先找到Node* prev = nullptr;Node* cur = _root;while (cur){if (cur->val > key){prev = cur;cur = cur->left;}else if (cur->val < key){prev = cur;cur = cur->right;}else{//找到了--三种情况--左为空，右为空，左右均不为空//1.左为空if (cur->left == nullptr){//1.先判断是不是根节点if (_root == cur)_root = cur->right;else{//不是根节点--那么就是链接的问题了if (cur == prev->left)prev->left = cur->right;else if (cur == prev->right)prev->right = cur->right;}delete cur;cur = nullptr;return true;}//2.右为空else if (cur->right == nullptr){//1.先判断是不是根节点if (_root == cur)_root = cur->left;else{//不是根节点--那么就是链接的问题了if (cur == prev->left)prev->left = cur->left;else if (cur == prev->right)prev->right = cur->left;}delete cur;cur = nullptr;return true;}else{//左右均不为空--那么找左子树的最右，或者右子树的最左来进行替换Node* prev = cur;Node* minleft = cur->right;while (1){if (minleft->left != nullptr){prev = minleft;minleft = minleft->left;}elsebreak;}//找到了右子树的最左为minleftcur->val = minleft->val;//还是分两种情况--左为空或者右为空if (minleft->left == nullptr){if (prev == cur)prev->right = minleft->right;elseprev->left = minleft->right;}else if (minleft->right == nullptr){//右为空，那么左右一定是空的，因为minleft就是最左了if (prev == cur)prev->right = nullptr;elseprev->left = nullptr;}delete minleft;minleft = nullptr;return true;}}}return false;
}