建设在线购物网站,无需登录网页小游戏网站,视觉差网站制作,网站制作代引言#xff1a;
上次我们结束了类和对象的收尾#xff0c;之后我们就要学习一些高级的数据结构#xff0c;今天我们先来看一个数据结构-- 二叉搜索树。
一#xff1a; 二叉搜索树的概念(性质)
二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是…引言
上次我们结束了类和对象的收尾之后我们就要学习一些高级的数据结构今天我们先来看一个数据结构-- 二叉搜索树。
一 二叉搜索树的概念(性质)
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有结点的值都小于等于根结点的值。若它的右子树不为空则右子树上所有结点的值都大于等于根结点的值。它的左右子树也分别为二叉搜索树。二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树其中map/set不支持插入相等值multimap/multiset支持插入相等值。
左图就是map不支持插入相同的数据。 右图就是multimap支持插入相同的数据。
二二叉搜索树的性能分析
最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其高度为 log2N。 最差情况下二叉搜索树退化为单支树(或者类似单支)其高度为N。 所以综合而言二叉搜索树增删查改时间复杂度为O(N)。 那么这样的效率显然是无法满足我们需求的我们后续会接着学习二叉搜索树的变形平衡二叉搜索树AVL树和红黑树才能适用于我们在内存中存储和搜索数据。 另外需要说明的是二分查找也可以实现o(log2N)级别的查找效率但是二分查找有两大缺陷
需要存储在支持下标随机访问的结构中并且有序。插入和删除数据效率很低因为存储在下标随机访问的结构中插入和删除数据一般需要挪动数据。 因此这里也就体现出了平衡二叉搜索树的价值。
三模拟实现二叉搜索树
1. 基本框架
因为二叉搜索树是二叉树衍生而来的因此其基本结构和二叉树差不多因此这里我们就不细讲
2. 插入数据
1插入原则
插入的具体过程如下
树为空则直接新增结点赋值给root指针。树不空按二叉搜索树性质插入值比当前结点大往右走插入值比当前结点小往左走找到空位置插入新结点。如果支持插入相等的值插入值跟当前结点相等的值可以往右走也可以往左走找到空位置插入新结点。要注意的是要保持逻辑一致性插入相等的值不要一会往右走一会往左走但是这里我们实现的是不支持插入相同数据的
2思路分析 3补充
注由于插入数据的时候牵扯到数据的申请因此这里的节点结构要提供对于的构造函数来生成节点。
4代码实现 5测试
注这里为了测试插入数据因此我们再实现一个中序遍历。
中序遍历实现 可以看到测试结果没有问题。
3. 查找数据
1查找原则
从根开始比较查找xx比根的值大则往右边走查找x比根值小则往左边走查找。 2. 最多查找高度次走到空还没找到这个值不存在。 3. 如果不支持插入相等的值找到x即可返回。 4. 如果支持插入相等的值意味着有多个x存在一般要求查找中序的第一个x。如下图查找3要找到1的右孩子的那个3返回。 2思路分析
查找的逻辑和插入的逻辑基本上一样就不再具体分析。
3 代码实现 4测试: 测试没问题。
4. 删除数据
相较于插入数据删除数据就比较复杂了需要考虑各种情况下面我们来一点点分析 首先查找元素是否在二叉搜索树中如果不存在则返回false。 如果查找元素存在则分以下四种情况分别处理假设要删除的结点为N
要删除结点N左右孩子均为空。要删除的结点N左孩子位空右孩子结点不为空。要删除的结点N右孩子位空左孩子结点不为空。要删除的结点N左右孩子结点均不为空。 对应以上四种情况的解决方案把N结点的父亲对应孩子指针指向空直接删除N结点情况1可以当成2或者3处理效果是一样的把N结点的父亲对应孩子指针指向N的右孩子直接删除N结点。把N结点的父亲对应孩子指针指向N的左孩子直接删除N结点。无法直接删除N结点因为N的两个孩子无处安放只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N因为这两个结点中任意一个放到N的位置都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换转而变成删除R结点R结点符合情况2或情况3可以直接删除。
1 思路分析 2代码实现 (3) 测试: 5. 销毁
1思路分析
跟之前我们的二叉树销毁一样只需要后序遍历来销毁即可。
2 代码实现 6. 拷贝构造函数
这里跟之前二叉树的构建一样只需要一边遍历一边构建即可。
2代码实现 3测试 7. 赋值运算符重载
1思路分析
这里的赋值运算符重载和之前差不多还是复用拷贝构造函数。
2代码实现 3测试 完结
