|
|
|
|
|
Huffman树又称为最优二叉树，是一类带权路径长度最短的树。Huffman树是指权值为w1, w2, …, wn的n个叶子节点的二叉树中带权路径长度最小的二叉树。
|
|
|
|
|
|
（1）路径是指从树中一个节点到另一个节点之间的分支构成的这两个节点之间的路径，路径上的分支数目就称为路径长度。
|
|
|
|
（2）树的路径长度是从树根到每一个叶子之间的路径长度之和。
|
|
|
（3）节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。树的路径长度为树中所有节点的带权路径长度之和，记为 ，其中n为带权叶子节点数目；wk为叶子节点的权值；1k为叶子节点到根的路径长度。
|
|
|
|
|
|
|
|
（2）选两个权值最小的节点构造一棵新的二叉树，新的二叉树的根节点的权值就是两个子节点权值之和。
|
|
|
|
（3）从n个节点中删除刚才使用的两个节点，同时将新产生的二叉树的根节点放在节点集合中。
|
|
|
|
（4）重复步骤（2）、步骤（3），直到只有一棵树为止。
|
|
|
|
|
|
Huffman树的应用是Huffman编码，在编码过程中要考虑两个问题，一是数据的最小冗余编码问题，二是译码的唯一性问题。在实际应用中，各个编码字符的出现频率不同，希望用最短的编码来表示出现频率大的字符，而用较长的编码表示出现频率较小的字符，从而使整个编码序列的总长度最小，这就是最小冗余编码问题。Huffman编码就解决了这个问题，根据权值或概率的大小来构建Huffman树，然后左分支用0表示，而右分支用1表示，这样就形成了编码序列。
|
|
|
