二叉树之哈夫曼树定义-构造-哈夫曼编码

• • • • 1.带权路径长度
      • 2.哈夫曼树的构造过程
      • 3.哈夫曼树的性质
      • 4.哈夫曼树的应用：哈夫曼编码，可以用于数据的压缩。

节点的权：有某种现实意义的数值
节点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上的权值的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL，Wighted Path Length）

哈夫曼树的定义：在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也成最优二叉树。

给定n个权值分别为 w 1 , w 2 , . . . w n w_{1},w_{2},...w_{n} w1​,w2​,...wn​的节点，通过以下步骤构造哈夫曼树。

1. 将n个结点分别作为仅含有一个节点的二叉树，构成森林 F F F。
2. 构造一个新节点，从 F F F中选取两棵根结点权值最小的树作为新节点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从F中删除刚才选出的两棵树，同时将新得到的树加入到 F F F中。
4. 重复2,3直至F中近剩一棵树为止。

1. 每个初始节点都会成为叶结点，且权值越小的节点到根结点的路径长度越大。
2. 总共 n n n个结点需要合并 n − 1 n-1 n−1次，增加 n − 1 n-1 n−1个结点，所以哈夫曼树的结点总数为 2 n − 1 2n-1 2n−1.
3. 哈夫曼树中不存在度为1的结点。
4. 哈夫曼树并不唯一，但 W P L WPL WPL必然相同并且为最优。

可变长度编码：允许对不同字符用不等长的二进制位表示。
前缀编码：没有一个编码是另一个编码的前缀。
哈夫曼树转哈夫曼编码：字符集中的每个字符作为一个叶子节点，各个字符出现的频度作为结点的权值，构造哈夫曼二叉树。