集训5

树：类型 公式 哈夫曼

二叉树：子节点不多于两个

满二叉树：每一层节点都是满的二叉树（中国，以中国为准）

       每个节点要么是叶子结点，要么是度为2的节点，是满二叉树（外国）

完全二叉树：最后一层所有节点靠左的二叉树，其他层是满的

二叉搜索树：从根结点开始，所有左子都比根小，所有右子都比根大的树

   通常用来搜索，或排序，也叫二叉排序树（中序遍历有序）

哈夫曼树，符合哈夫曼编码的树

-----

公式：默认把二叉树中，叶子结点记为a0，度为1和2的结点记为a1，a2

在任意一种二叉树中，a2+1=a0

   假设一共有N个结点，N=a0+a1+a2

   N=1+（a0*0+a1*1+a2*2）所有子结点

满二叉树：高度是h，N=2^h-1

完全二叉树：高h，总结点N的取值范围：2^(h-1)<N<=2^h-1

完全二叉树：从根结点开始，按照层序遍历编号：

       从1开始编号，对于任意一点x，父节点：x/2，左子：2x，右子：2x+1

       从0开始，对于x，父节点：(x-1)/2，左子：2x+1，右子：2x+2

哈夫曼编码：目的数据压缩，压缩过程中，利用了贪心思想

发送：abaccabad     72bit

1、统计频率/次数：a4 b2 c2 d1

2、保持：从小到大排序

3、每次拿出两个最小的合并再放回，反复，直到只剩一个

4、构造成树，左0右1编码

5、计算压缩后大小：编码位*频率（次数）相加

图：

   链表：一对一，树：一对多

   图：多对多

表示图：G（V，E） G：graph图，v：结点的数量，e：边的数量

G（5，8）

边：无向边（正反都可以走），有向边（只能朝箭头方向走）

   有向图，无向图

度数：该结点连接的边数

   有向图中，入度：指向该结点的边数，出度：从该结点出发指向其他点的边数

路径：从一个点到另一个点的连续边的集合，

如果从起点出发，经过n个点还能回到起点，叫做环

图的连通性：

   在无向图中，如果任意两点间都存在路径，这个图是联通图

   在有向图中，如果任意两点间都存在路径，这个图是强联通图

   在有向图中，如果去掉方向后，任意两点间都存在路径，这个图是弱联通图

边的长度，叫做权重，有权重的图，叫做带权图

存图方式，邻接矩阵，邻接表

子图，生成树，最小生成树（以大权边删除优先），图的遍历（深度优先搜索dfs，广度优先搜索bfs，泛洪搜索）

简单图：没有自环，没有重边的图

完全图：无向图中，每一对顶点都存在一条边

二分图：顶点分成两个互不相交的集合，使得图中每一条边都只链接两个不同集合的顶点

算法：解决问题的方法

算法的好坏：复杂度

   时间：

       常数级时间复杂度：O(1)不受输入影响

       对数时间复杂度：O(logn) 二分查找

       线性时间复杂度：O(n) 一层根据数据量而定的循环

       对数线性：O(nlogn) 归并排序，快速排序

       平方时间复杂度：O(n^2) 双重循环，二维数组，99乘法表，星阵，冒泡、选择、插入

       指数时间复杂度：O(2^n) O(3^n) .... 递归（一分多的情况）

       其他：O(n!)

   空间：O(1),O(n),O(logn)..【程序运行时，占用的空间，目前已此为准】【程序运行时，额外占用的空间】