数据结构_树_图_总结
数据结构 - 树、图 总结
数据结构：树（Tree）
二叉树
二叉树第 i 层的节点数目最多为2 ^ (i - 1) ( i >=1)
深度为 k 的二叉树最多有（2 ^ k）- 1个节点 （k >= 1）
在任意一个二叉树中 N0 表示 度数为0的节点个数， N2 表示度数为2的节点个数， 则有 N0 = N2 + 1
满二叉树：一个填满的二叉树
完全二叉树：满二叉树数完全二叉树， 完全二叉树不一定是满二叉树。
二叉树的遍历：先序，中序，后序 树的遍历和代码实现
线索二叉树 线索二叉树
树与二叉树的转换
哈弗曼树、编码
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度
平衡二叉树
参考自： 平衡二叉树（树的旋转) 以下是节选内容
数据结构：图（Graph）
紧接矩阵与邻接表
参考自： 数据结构：图（Graph） , 以下是节选部分内容
邻接表
在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。比如，如果顶点A 有一条边到B、C和D，那么A的列表中会有3条边
邻接列表只描述了指向外部的边。A 有一条边到B，但是B没有边到A，所以 A没有出现在B的邻接列表中。查找两个顶点之间的边或者权重会比较费时，因为遍历邻接列表直到找到为止。
邻接矩阵
在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如，如果从顶点A到顶点B有一条权重为 5.6 的边，那么矩阵中第A行第B列的位置的元素值应该是5.6：
往这个图中添加顶点的成本非常昂贵，因为新的矩阵结果必须重新按照新的行/列创建，然后将已有的数据复制到新的矩阵中。
所以使用哪一个呢？大多数时候，选择邻接列表是正确的。下面是两种实现方法更详细的比较。
假设 V 表示图中顶点的个数，E 表示边的个数。
| 操作 | 邻接列表 | 邻接矩阵 |
|---|---|---|
| 存储空间 | O(V + E) | O(V^2) |
| 添加顶点 | O(1) | O(V^2) |
| 添加边 | O(1) | O(1) |
| 检查相邻性 | O(V) | O(1) |
“检查相邻性” 是指对于给定的顶点，尝试确定它是否是另一个顶点的邻居。在邻接列表中检查相邻性的时间复杂度是O(V)，因为最坏的情况是一个顶点与每一个顶点都相连。
在 稀疏图的情况下，每一个顶点都只会和少数几个顶点相连，这种情况下相邻列表是最佳选择。如果这个图比较密集，每一个顶点都和大多数其他顶点相连，那么相邻矩阵更合适。
最小生成树
参考自： 最小生成树的两种方法（Kruskal算法和Prim算法） ，以下是节选部分内容
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树
Kruskal算法
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
- 把图中的所有边按代价从小到大排序；
- 把图中的n个顶点看成独立的n棵树组成的森林；
- 按权值从小到大选择边，所选的边连接的两个顶点ui,vi ui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
- 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
Prim算法
此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。
- 图的所有顶点集合为VV；初始令集合u={s},v=V?uu={s},v=V?u;
- 在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
- 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。
由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息，：
最短路径
请观看视频讲解 这个视频对于原理讲解得已近足够清除。
关键路径
参考博客 ?数据结构 图之关键路径