三、数据结构3.4 树形结构1. 概念1节点组成树形结构的元素2特性只能有一个前驱但可以有多个后继每个节点在树形结构中的路径都是唯一的根节点没有前驱只有后继的顶层节点分支节点有前驱也有后继叶子节点只有前驱没有后继的节点称为叶子节点3层根节点所在层数为1后继每过一个节点层数14节点高度从叶子节点出发到达根节点的节点个数5节点深度从根节点出发到指定节点的节点个数树的高度 树的深度 树的层数6子树树形结构可以看做是由很多子树构成7多个子树构成的属性结构称为森林2. 二叉树1概念树形结构中所有节点最多有2个后继节点称为二叉树2节点类型1. 根节点2. 叶子节点3. 分支节点只有左孩子只有右孩子左孩子右孩子都有3完全二叉树将二叉树编码后展开编号连续的称为完全二叉树4满二叉树二叉树所有的叶子节点都在同一层每一层上的节点都是满的5特性二叉树第k层最 2^k-1 个节点满二叉树前k层有 2^k -1 个节点6. 二叉树的遍历深度优先遍历DFS前序遍历根左右中序遍历左根右后续遍历左右根广度优先遍历BFS:逐层从左到右遍历3.5 哈希表1. 哈希一种算法通过哈希算法将数据映射成键值根据键值来存取数据以降低查找数据时的时间复杂度2. 哈希冲突多个数据通过哈希算法映射成相同的键值就会产生哈希冲突3.6排序和查找1. 冒泡排序相邻两个元素比较大的向后走小的向前走逐渐将最大值放入最末尾循环将前面元素排序即可时间复杂度:O(n^2)稳定性稳定2. 选择排序假设前面的元素为最小值将最小值与后续元素比较最终获得当前最小值与前面元素交换到对应的位置时间复杂度:O(n^2)稳定性不稳定3. 插入排序将前面元素看成有序数列将后续元素插入有序数列中称为新的有序数列时间复杂度:O(n^2)稳定性稳定4. 希尔排序将数组根据步长拆分成若干个小数组依次对每个小数组进行插入排序将数据变成大致有序最后再完成一次插入排序时间复杂度:O(nlogn)稳定性不稳定5. 快速排序选取第一个元素作为键值从后面找比键值小的放前面从前面找比键值大的放后面最终键值放中间如果左侧有元素递归快速排序如果右侧有元素递归快速排序时间复杂度:O(nlogn)稳定性不稳定