企业官网建设流程全解析

带权路径长度

• 结点的权：有某种现实含义的数值（如：表示结点的重要性等）

• 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

• 树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL, Weighted Path Length）
  WPL=∑i=1nwili\mathrm{WPL} = \sum_{i=1}^{n} w_{i}l_{i}WPL=i=1∑n​wi​li​

哈夫曼树的定义

在含有nnn个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。

哈夫曼树的构造

给定nnn个权值分别为w1,w2,...,wnw_1, w_2,..., w_nw1​,w2​,...,wn​的结点，构造哈夫曼树的算法描述如下：
1）将这nnn个结点分别作为nnn棵仅含一个结点的二叉树，构成森林FFF。
2）构造一个新结点，从FFF中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3）从FFF中删除刚才选出的两棵树，同时将新得到的树加入FFF中。
4）重复步骤2）和3），直至FFF中只剩下一棵树为止。

哈夫曼编码

固定长度编码——每个字符用相等长度的二进制位表示
可变长度编码——允许对不同字符用不等长的二进制位表示
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

由哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值。

• 可以用于数据的压缩