哈夫曼树？哈夫曼编码简单例题图

一、哈夫曼树是唯一的吗

不可以。因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。哈夫曼树（霍夫曼树）又称为最优树.1、路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。

若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。2、结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。3、树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

二、赫夫曼树和哈夫曼树一样吗

赫夫曼树和哈夫曼树一样。不管赫夫曼、哈夫曼还是霍夫曼，都是来自于Huffman，不过是不同的音译。

哈夫曼树是一种带权路径长度最短的二叉树，又称最优二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度。哈夫曼树的意义就是根据字符出现的概率来构造平均长度最短的编码。

三、如何建立哈夫曼树

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为k1、k2、…、kn，则哈夫曼树的构造规则为：

(1)将k1、k2、…，kn看成是有n棵树的森林(每棵树仅有一个结点)；

(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。哈夫曼静态编码：它对需要编码的数据进行两遍扫描：

第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；

第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。

编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。