数据结构期末复习总结（后章）
作者的话
作为一名计算机类的学生，我深知数据结构的重要性。在期末复习前，我希望通过这篇博客给大家一些复习建议。希望能帮助大家夯实数据结构的基础知识，并能够更好地掌握数据结构和算法的应用。
一、树与二叉树
1.基本概念
树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法
1.1 二叉树的性质
性质1 在二叉树的第i层上至多有
个节点(i>=1)
性质2深度为k的二叉树至多有
个节点（k>=1）
性质3，在任何一棵二叉树中，终端节点（即度为0的节点）的数量与度为2的节点数量相差1
性质4具有n个结点的完全二叉树的深度为⌊log2n⌋+1
利用二叉链表存储树，则根结点的右指针是 空的解释
当使用二叉链表来表示一棵树时，每个节点通常都有三个指针，分别指向其左孩子节点、右孩子节点和父节点。但是对于根节点而言，它没有父节点，因此其父节点指针为空。
另外，由于根节点是树的最上层节点，它没有兄弟节点，因此其右孩子节点为空。因此，在用二叉链表表示一棵树时，通常将根节点的右孩子指针置为空。
1.2二叉树的遍历
前序遍历：按照“根左右”的顺序遍历二叉树。即先访问根节点，然后递归访问左子树，最后递归访问右子树。
中序遍历：按照“左根右”的顺序遍历二叉树。即先递归访问左子树，然后访问根节点，最后递归访问右子树。
后序遍历：按照“左右根”的顺序遍历二叉树。即先递归访问左子树，然后递归访问右子树，最后访问根节点。
层次遍历: 它按照层次顺序逐层遍历二叉树的所有节点。具体实现方式为从二叉树的根节点开始，按照从上到下、从左到右的顺序依次遍历每一层的节点。
1.3二叉树的线索化
线索化的基本思路是在二叉树的每个节点上增加两个特殊的指针：一个指向该节点的前驱节点，一个指向该节点的后继节点。对于叶子节点来说，它的左右子节点都指向它的前驱节点和后继节点。对于非叶子节点来说，它的左右子节点如果存在，则分别指向它的前驱节点和后继节点。
找缺腿，缺啥腿，补啥腿
2. 树和森林与二叉树的相互转换
2.1 树转换为二叉树
- 将同一结点的个孩子结点用线连起来
- 将每个结点的分支结点从左往右除了第一个意外，其余的都减掉
2.2 二叉树转换为树
- 从左上到右下分为若干层，并调整至水平方向
- 找到每一层结点在其上一层的父结点
- 将每一层的结点与其父结点相连，且删除每一层结点之间的连接
2.3 森林转换为二叉树
- 先将森林中的所有树转换为二叉树
- 将第n+1棵二叉树作为第n棵二叉树的右子树
2.4 二叉树转换为森林
- 将有右孩子的二叉树的而孩子全部断开，直到不存在根节点有右孩子的二叉树为止
- 将每棵二叉树转换为树
2.5树和森林的遍历
树的遍历
树的遍历操作就是按照某种方式访问树中的每个结点，且仅访问一次。树的遍历操作主要有先根遍历和后根遍历两种方式，此外还有层次遍历。
树的先根遍历
树的先根遍历的思想：若树为空，则先访问根结点，再按从左到右的顺序遍历根结点的每棵子树。
其访问顺序与这棵树相应二叉树的先序遍历顺序相同。
对于下面这棵树，按照其先根遍历的思想，其先根遍历序列为：A B E F C D G .
其中这棵树对应的二叉树为：
按照二叉树的先序遍历思想，这棵二叉树的先序遍历序列为：A B E F C D G .
树的后根遍历
树的后根遍历思想：若树非空，则按从左往右的顺序遍历根结点的每棵子树，之后再访问根结点。
其访问顺序与这棵树的相应二叉树的中序遍历顺序相同。
还是同样上面这棵树，其后根遍历序列为： E F B C G D A .
其对应的二叉树还是：
根据二叉树的中序遍历思想，这棵二叉树的中序遍历序列为：E F B C G D A .
森林的遍历
森林的遍历方法主要有先序遍历和中序遍历两种。
森林的先序遍历
若森林为非空，则按如下规则进行遍历：
<1> 访问森林中第一棵树的根结点；
<2> 先序遍历第一棵树中根结点的子树森林；
<3> 先序遍历除去第一课树之后剩余的树构成的森林。
其访问顺序与森林相应二叉树的先序遍历顺序相同。
森林先序遍历的实例：
根据森林的先序遍历思想，可得到这个森林的先序遍历序列为： A B C D E F G H K L I J .
其相应的二叉树为：
根据二叉树的先序遍历思想，可得这个二叉树的先序遍历序列为： A B C D E F G H K L I J .
森林的中序遍历
若森林非空，则按如下规则进行遍历：
<1> 中序遍历森林中第一颗树的根结点的子树森林；
<2> 访问第一棵树的根结点；
<3> 中序遍历除去第一棵树之后剩余的树构成的森林。
其访问顺序与森林相应二叉树的中序遍历顺序相同。
还是上面那个森林：
根据森林的中序遍历思想，这个森林的中序遍历序列为： B C A F E D K L H I J G .
其对应的二叉树为：
按照二叉树的中序遍历思想，其中序遍历序列为：B C A F E D K L H I J G .
2.5赫夫曼树
基本概念
- 路径：从一个结点到另一个结点的分支所构成的路线
- 路径长度：路径上的分支数目
- 树的路径长度：从根到每个结点的路径长度之和
- 带权路径长度：从根到该结点之间的路径长度乘以该结点的权值
- 树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和
赫夫曼树的构造方法（给定n个权值）
- 将这n个权值分别看作只有根节点的n棵二叉树，这些二叉树构成的集合记为F
- 从F中选出两棵根节点的权值最小的树作为左、右子树，构成一棵新的二叉树，新的二叉树的根节点的权值为左、右子树根节点权值之和
- 重复上述步骤，直到F中只有一棵树为止
赫夫曼树的特点
- 权值越大的结点离根节点越近
- 树中没有度为1的结点
- 树的带权路径最短
二、图
2.1基本概念
完全图：任意两个顶点都有边相连
有向完全图：n个顶点，n(n-1)条边
无向完全图：n个顶点，n(n-1)/2条边
路径长度：路径上边的个数
简单路径：序列中顶点不重复出现
回路：起点顶点和终点顶点相同的路径
连通：两个顶点之间有路径
连通图（无向图）：任意两个顶点之间连通从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图
连通分量：极大连通子图
强连通图（有向图）：任意两个顶点之间都有路径
强连通分量：极大强联通子图
无向图顶点度数之和 = 边数目的2倍
2.存储结构
2.1 邻接矩阵（顺序存储）
表示顶点之间的关系
设邻接矩阵A，Am中非零元素A[i][j]代表从i到j且路径长度为m的路径条数
- A[i][j] = 1 表示顶点i与顶点j邻接（i与j之间存在边/弧）
- A[i][j] = 0 表示顶点i与顶点j不邻接
2.2 邻接表（链式存储）
2.3 邻接多重表
2.4.图的遍历
2.4.1 深度优先搜索（栈 先序遍历）
任取一个顶点，访问，再检查这个顶点的所有邻接顶点，递归访问其中未被访问过的顶点
2.4.2 广度优先搜索（队列 层次遍历）
先访问起始节点v，然后选取与v邻接的所有顶点w1…wn，再依次访问与w1…wn邻接的全部顶点，以此类推，直到所有顶点被访问
任取图中一个顶点访问，入队，并将这个顶点标记为已访问
当队列不空是执行循环：出队，一次检查出队的所有邻接顶点，访问没有访问过的邻接顶点，并将其入队
队列为空时跳出循环
以图表形式
以邻接矩阵形式
以邻接表形式
对于一些特殊的图，比如只有一个顶点的图，其 BFS 生成树的树高和 DFS 生 成树的树高相等。一般的图，根据图的 BFS 生成树和 DFS 树的算法思想，BFS 生成树的树 高比 DFS 生成树的树高小。
2.5最小生成树
Prim 算法适合构造一个稠密图 G 的最小生成树，Kruskal 算法适合构造一个稀疏 图 G 的最小生成树。
2.5.1 Prim算法
将v0到其他顶点的所有边当作候选边
从候选边中挑选出权值最小的边输出，并将与该边另一端相接的顶点v并入生成树中
考察剩余所有顶点vi，如果(v, vi)的权值比lowcost[vi]小，则用(v, vi)的权值更新lowcost[vi]
重复2、3步n-1次，使得其他n-1个顶点被并入至生成树中
2.5.2 Kruskal算法
每次找出候选边中权值最小的边，就将该边并入生成树中。重复此过程直到所有边都被检测完为止
- 将图中边按权值大小排序，然后从最小边开始扫描各边，并检测当前边是否为候选边，即是否该边的并入会产生回路，若不构成回路，则将该边并入当前生成树中，直到所有的边都被检测完为止。
2.6.最短路径
2.6.1 Dijkstra算法
2.6.2Floyd算法
Floyd:不断基于对角线上元素画“十字”计算的过程
1.从第一个对角线元素开始不断画十字
2.十字和它∞部分对应的行列值不变
3.更新值与路径，取下一个对角线元素继续重复
注:值比原来元素小才更新
2.7拓扑排序（AOV网）
活动在顶点上的网(Activity On Vertex network, AOV)
- 顶点表示活动
- 边表示活动的先后次序
- 没有回路
过程：
- 从有向图中选择一个没有前驱的顶点输出
- 删除该顶点，并删除从该顶点发出的所有边
- 重复以上两步，直到剩余的图中不存在没有前驱的顶点为止
2.8.关键路径（AOE网）
活动在边上的网（Activity On Edge network, AOE）
- 边表示活动，权值代表活动的持续时间
- 顶点表示时间，时间是图中新活动开始或旧活动结束的标志
- 源点：入度为0的点，表示整个工程的开始
- 汇点：出度为0的点，表示整个工程的结束
- 关键路径：
- 从源点到汇点中具有最大路径长度的路径
- 关键路径的长度所代表的的时间就是完成整个工期的最短时间
- 关键活动：关键路径上的活动
相关概念
最早开始时间是取最大值，而最晚开始时间是取最小值，因为最早要求不能比它早否则之前的工作干不完，最晚要求不能比它晚否则耽误之后的工作。早头晚尾
三、查找
3.1折半查找
折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
折半查找的判定树深度为 log2 n+ 1
3.2分块查找
分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块， 就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进 行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找
3.3二叉排序树
3.4平衡二叉树
它具有以下特点：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树。
对于任意节点，它的左右两个子树的高度差不超过1。
在平衡二叉树中，所有节点的左右子树的高度差都不超过1，这保证了平衡二叉树的查找、插入、删除等操作的时间复杂度为O(logN)，其中N为节点数。
3.5B-树
3.5.1 B-树的插入（创建）
3.5.2B树的删除
插入的逆过程
3.6哈希表
四、排序
1.冒泡排序
- 算法思想：
两两比较，经过一系列交换，直到最大的到最后- 时间复杂度：O(n2)
- 稳定
2.直接插入排序
- 算法思想:
每趟讲一个待排序的关键字按其值的大小插入到已经拍好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列中为止- 时间复杂度：O(n2)
- 稳定
3.希尔排序
- 算法思想:
通过不断缩小的增量分组，组内进行排序- 时间复杂度：
- 不稳定
4. 快速排序
- 算法思想:
每次选择一个基准数，比他小的放在左边，比他大的放在右边- 时间复杂度：O(nlog2n)
- 不稳定
5.选择排序
- 算法思想:
- 每次选出一个最小值放在最前面
- 时间复杂度：O(n2)
- 不稳定
6.堆排序
- 算法思想:
调整为大根堆后，跟最后一个结点交换，再将其余的调整为大根堆- 时间复杂度：O(nlog2n)
- 不稳定
7.归并排序
- 算法思想:
分治思想，先分，后合- 时间复杂度：O(n2)
- 稳定
8.基数排序
- 算法思想:
根据位数依次排序- 时间复杂度：O(d(n+rd))
- 稳定
总结
插入排序：
最好情况：O(n)，比较n-1次，交换0次
最坏情况：O(n2)，比较n(n-1)/2次，交换(n+4)(n-1)/2次
平均情况：O(n2)
2.折半插入
比较次数与序列初始状态无关，为log2(n!)次
移动次数与直接插入排序相同
3.希尔排序
不稳定，对规模较大的序列效率高
全部正序比较n(log2n - 1)+1次
全部逆序比较n(3log2n - 4)/2+2次，移动105nlog2n次
4.冒泡排序
最好情况：O(n)，比较n-1次，交换0次
最坏情况：O(n2)，比较n(n-1)/2次，交换3n(n-1)/2次
平均情况：O(n2)
5.快速排序
不稳定
最好情况：O(nlog2n)，空间复杂度O(log2n)
最坏情况：O(n2)，比较n(n-1)/2次，移动2(n-1)次，空间复杂度O(n)
平均情况：O(nlog2n)
递归次数与每次划分后得到的分区的处理顺序无关
每次分区后先处理较短部分可以减少递归深度
6.选择排序
选择排序的比较次数与元素的初始排列无关，为n(n-1)/2次
最坏情况下移动次数为3(n-1)
O(n2)
7.堆排序
从根结点到叶结点最多筛选⌊log2n⌋次
O(nlog2n)
高度为n的堆最多容纳2h-1个元素，最少容纳2h-1个元素
8.锦标赛排序
O(nlog2n)，空间复杂度O(n)，稳定
9.归并排序
比较次数和移动次数为O(nlog2n)
空间复杂度O(n)
n个元素做m路归并排序需要⌈log2n⌉趟
两个长度为n的有序表合并时最少比较n次，最多比较2n-1次
对n个互异的数进行排序，需要比较log2(n!)次
- 最好情况下：直接插入和冒泡排序最快
- 最坏情况下：堆排序和归并排序最快