哈夫曼树（定义，构造，哈夫曼编码）

定义，构造，哈夫曼编码）"/>

哈夫曼树（定义，构造，哈夫曼编码）

目录

• 1.带权路径长度
• 2.哈夫曼树的定义
• 3.哈夫曼树的构造
• • 1.哈夫曼树的特性
• 4.哈夫曼编码
• • 1.编码方式
  • 2.应用

1.带权路径长度

①结点的权:有某种现实含义的数值（如:表示结点的重要性等)
②结点的带权路径长度:从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。
③树的带权路径长度:树中所有叶结点的带权路径长度之和 (WPL, Weighted Path Length)
W P L = ∑ i = 1 n w i l i WPL=\sum\limits_{i=1}^{n}w_il_i WPL=i=1∑n​wi​li​

2.哈夫曼树的定义

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

3.哈夫曼树的构造

给定n个权值分别为w1, w2,…, wn,的结点，构造哈夫曼树的算法描述如下:
①将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
②构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
③从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
④重复步骤②和③，直至F中只剩下一棵树为止。
例如：

1.哈夫曼树的特性

①每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
②哈夫曼树的结点总数为2n-1
③哈夫曼树中不存在度为1的结点。
④哈夫曼树并不唯一，但WPL必然相同且为最优。

4.哈夫曼编码

1.编码方式

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

由哈夫曼树得到哈夫曼编码――字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树.
哈夫曼树不唯一，因此哈夫曼编码不唯一。
例如：

2.应用

将字符频次作为字符结点权值，构造哈夫曼树，即可得哈夫曼编码，可用于数据压缩.