1、哈夫曼树

带权路径最小的二叉树，构造方法：n个节点带有权值，看成n棵树，取权值最小的两个合并，新树权值为子树和，直到合并为一棵树。

2、哈夫曼编码

权值是字符出现的概率，概率越低，哈夫曼编码是为了降低编码长度，比如n种符号，最差编码方式为2^n个bit编码一个符号，哈夫曼编码考虑了字符出现的概率，字符在哈夫曼树的层数越深，编码越长，哈夫曼编码是不失真的最优编码，比起失真的压缩算法压缩率还是很低的，并且要存储这棵树，对概率接近的文本，反而不划算

3、最小生成树及其算法

最小生成树：无向带权路径图中，用最短的路径连接起来的图，此图必定无环，因而为一棵树，实际例子：n个村庄分布，用一条最短的公路将所有村庄连接起来

Prim算法：任意顶点出发，找到最近的点加入树，将此点、两点之间的边加入树，寻找距离树最近的新点，点、边加入树，直到所有点加入。

Kruskal算法：从最短的边出发，将两个顶点和边加入集合，寻找下一个最短的边，若边的两个顶点如果已经属于同一个集合，寻找下一个最短的边，否则，将边以及边两头的集合合并为同一个集合，直到只剩下一个集合。