哈夫曼树

相关名词

• 路径与路径长度: 从树中一个节点到另一个节点之间的分支构成了两个节点之间的路径，路径上的分支数目称作路径长度。若规定根节点位于第一层，则根节点到第H层的节点的路径长度为H-1。如到40 的路径长度为1；30的路径长度为2；20的路径长度为3。
• 节点的权: 将树中的节点赋予一个某种含义的数值作为该节点的权值，该值称为节点的权；
• 带权路径长度: 从根节点到某个节点之间的路径长度与该节点的权的乘积。例如上图节点10的路径长度为3,它的带权路径长度为10 * 3 = 30；
• 树的带权路径长度: 树的带权路径长度为所有叶子节点的带权路径长度之和，称为WPL。上图的WPL = 1x40+2x30+3x10+3x20 = 190，而哈夫曼树就是树的带权路径最小的二叉树。

具有最小带权路径长度的二叉树称为哈夫曼树（也称最优树）

构造哈夫曼树的原则：

• 权越大的叶节点越靠近根节点
• 权值越小的叶节点原理根节点

构造过程

1. 给定的n个权值，构造n颗只有一个叶节点的二叉树，从而得到一个二叉树集合F={T1，T2，Tn}
2. 在F中选取根节点的权值最小和和次小的俩颗树作为左，右子树根节点权之和
3. 在集合F中删除作为左右子树的俩颗二叉树，并将新建立的二叉树加入到集合F中
4. 重复2,3俩步，当F中只剩下一颗二叉树时，这颗二叉树便是所要建立的哈夫曼树

哈夫曼编码

规定哈夫曼树中的左分支为0，右分支为1，则从根节点到每个叶节点所经过的分支对应0和1组成的序列便为该节点对应字符的编码这样的编码称为哈夫曼编码

权值越大的字符编码越短，反值越长

在一组字符的哈夫曼编码中，不可能出现前一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀

哈夫曼编码也称为前缀编码