[c++高阶]二叉搜索树深度剖析
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;
}
5.总结
二叉树的模拟实现肯定不只是单单的这么简单,而模拟实现他的目的只是为了更好的理解他的相关操作,以及理解增删查代码的相关写法。我们不是为了造轮子,而是为了更好的理解这个轮子是如何造出来的。
此外:本次只给出来查找函数的迭代写法和递归写法,插入函数和删除函数的递归写法还没有给出,有兴趣的小伙伴参考以下链接。
二叉搜索树的增删改模拟实现 · e87b2ae · 青酒余成/初识数据结构 - Gitee.com