度更新网站,企业网站建设 阿里云,网站建设开发实训报告总结,苏州网站建设设计公司前面学习的栈、队列等等都是线性表结构。树是一种非线性表结构#xff0c;比线性表的数据结构要复杂。
1-树tree “树”这种数据结构类似我们现实生活中的“树”#xff0c;这里面每个元素我们叫作“节点”#xff1b;用来连线相邻节点之间的关系#xff0c;我们叫作“父子… 前面学习的栈、队列等等都是线性表结构。树是一种非线性表结构比线性表的数据结构要复杂。
1-树tree “树”这种数据结构类似我们现实生活中的“树”这里面每个元素我们叫作“节点”用来连线相邻节点之间的关系我们叫作“父子关系”。如下图 A节点就是B节点的父节点B节点是A节点的子节点。B、C、D这三个节点的父节点是同一个节点所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点也就是图中的节点E。我们把没有子节点的节点叫作叶子节点或者叶节点比如图中的G、H、I、J、K、L都是叶子节点。
节点的高度节点到叶子节点的最长路径边数 节点的深度根节点到这个节点所经历的边的个数 节点的层数节点的深度1 树的高度根节点的高度。 “高度”这个概念其实就是从下往上度量比如我们要度量第10层楼的高度、第13层楼的高度起点都是地面。所以树这种数据结构的高度也是一样从最底层开始计数并且计数的起点是0。 “深度”这个概念在生活中是从上往下度量的比如水中鱼的深度是从水平面开始度量的。所以树这种数据结构的深度也是类似的从根结点开始度量并且计数起点也是0。 “层数”跟深度的计算类似不过计数起点是1也就是说根节点的位于第1层。
2-二叉树Binary Tree 二叉树顾名思义每个节点最多有两个“叉”也就是两个子节点分别是左子节点和右子节点。不过二叉树并不要求每个节点都有两个子节点有的节点只有左子节点有的节点只有右子节点。我们重点看下以下两个二叉树满二叉树和完全二叉树。 叶子节点全都在最底层除了叶子节点之外每个节点都有左右两个子节点这种二叉树就叫作满二叉树。 叶子节点都在最底下两层最后一层的叶子节点都靠左排列并且除了最后一层其他层的节点个数都要达到最大这种二叉树叫作完全二叉树。 3-二叉树的存储和表示方式 想要存储一棵二叉树我们有两种方法一种是基于指针或者引用的二叉链式存储法一种是基于数组的顺序存储法。 链式存储法每个节点有三个字段其中一个存储数据另外两个是指向左右子节点的指针。我们只要拎住根节点就可以通过左右子节点的指针把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。 基于数组的顺序存储法。我们把根节点存储在下标i 1的位置那左子节点存储在下标2 * i 2的位置右子节点存储在2 * i 1 3的位置。以此类推B节点的左子节点存储在2 * i 2 * 2 4的位置右子节点存储在2 * i 1 2 * 2 1 5的位置。 如果节点X存储在数组中下标为i的位置下标为2 * i 的位置存储的就是左子节点下标为2 * i 1的位置存储的就是右子节点。反过来下标为i/2的位置存储就是它的父节点。通过这种方式我们只要知道根节点存储的位置一般情况下为了方便计算子节点根节点会存储在下标为1的位置这样就可以通过下标计算把整棵树都串起来。一棵完全二叉树所以仅仅“浪费”了一个下标为0的存储位置。如果是非完全二叉树其实会浪费比较多的数组存储空间。 所以如果某棵二叉树是一棵完全二叉树那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
4-二叉树的遍历 经典的方法有三种前序遍历、中序遍历和后序遍历。其中前、中、后序表示的是节点与它的左右子树节点遍历打印的先后顺序。 前序遍历是指对于树中的任意节点来说先打印这个节点然后再打印它的左子树最后打印它的右子树。根-左-右 中序遍历是指对于树中的任意节点来说先打印它的左子树然后再打印它本身最后打印它的右子树。左-根-右 后序遍历是指对于树中的任意节点来说先打印它的左子树然后再打印它的右子树最后打印这个节点本身。左-右-根 前、中、后序遍历的顺序图可以看出来每个节点最多会被访问两次所以遍历操作的时间复杂度跟节点的个数n成正比也就是说二叉树遍历的时间复杂度是O(n)。
5-二叉查找树Binary Search Tree 二叉查找树是二叉树中最常用的一种类型也叫二叉搜索树。顾名思义二叉查找树是为了实现快速查找而生的。不过它不仅仅支持快速查找一个数据还支持快速插入、删除一个数据。 二叉查找树要求在树中的任意一个节点其左子树中的每个节点的值都要小于这个节点的值而右子树节点的值都大于这个节点的值。
查找先取根节点如果它等于我们要查找的数据那就返回。如果要查找的数据比根节点的值小那就在左子树中递归查找如果要查找的数据比根节点的值大那就在右子树中递归查找。
插入新插入的数据一般都是在叶子节点上所以我们只需要从根节点开始依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大并且节点的右子树为空就将新数据直接插到右子节点的位置如果不为空就再递归遍历右子树查找插入位置。同理如果要插入的数据比节点数值小并且节点的左子树为空就将新数据插入到左子节点的位置如果不为空就再递归遍历左子树查找插入位置。
删除删除的情况比较复杂分情况讨论。 第一种情况是如果要删除的节点没有子节点我们只需要直接将父节点中指向要删除节点的指针置为null。比如删除下图的节点55 第二种情况是如果要删除的节点只有一个子节点只有左子节点或者右子节点我们只需要更新父节点中指向要删除节点的指针让它指向要删除节点的子节点就可以了。比如删除下图的节点13 第三种情况是如果要删除的节点有两个子节点这就比较复杂了。我们需要找到这个节点的右子树中的最小节点把它替换到要删除的节点上。然后再删除掉这个最小节点因为最小节点肯定没有左子节点如果有左子结点那就不是最小节点了所以我们可以应用上面两条规则来删除这个最小节点。比如删除下图的节点18 删除后 实际上关于二叉查找树的删除操作还有个非常简单、取巧的方法就是单纯将要删除的节点标记为“已删除”但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中比较浪费内存空间但是删除操作就变得简单了很多。而且这种处理方法也并没有增加插入、查找操作代码实现的难度。
6-二叉查找树的时间复杂度 不管操作是插入、删除还是查找时间复杂度其实都跟树的高度成正比也就是O(height)。完全二叉树的高度小于等于logn(以2为底的对数)。二叉查找树在比较平衡的情况下插入、删除、查找操作时间复杂度才是O(logn)。
7-二叉查找树 vs 散列表 散列表的插入、删除、查找操作的时间复杂度可以做到常量级的O(1)非常高效。而二叉查找树在比较平衡的情况下插入、删除、查找操作时间复杂度才是O(logn)为什么还需要二叉查找树 第一散列表中的数据是无序存储的如果要输出有序的数据需要先进行排序。而对于二叉查找树来说我们只需要中序遍历就可以在O(n)的时间复杂度内输出有序的数据序列。 第二散列表扩容耗时很多而且当遇到散列冲突时性能不稳定尽管二叉查找树的性能不稳定但是在工程中我们最常用的平衡二叉查找树的性能非常稳定时间复杂度稳定在O(logn)。 第三笼统地来说尽管散列表的查找等操作的时间复杂度是常量级的但因为哈希冲突的存在这个常量不一定比logn小所以实际的查找速度可能不一定比O(logn)快。加上哈希函数的耗时也不一定就比平衡二叉查找树的效率高。 第四散列表的构造比二叉查找树要复杂需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题而且这个问题的解决方案比较成熟、固定。 最后为了避免过多的散列冲突散列表装载因子不能太大特别是基于开放寻址法解决冲突的散列表不然会浪费一定的存储空间。
