树，同时将新得到的树加入 F 中；

④ 重复②、③，直到 F 只含一颗树为止。

构造 Huffman 树时，为了规范，规定 F{T1,T2, ??6??8 ,Tn}中权值小的二叉树作为新构造的二叉树

的左子树，权值大的二叉树作为新构造的二叉树的右子树；在取值相等时，深度小的二叉树

作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。

图是权值集合 W{8, 3, 4, 6, 5, 5}构造 Huffman 树的过程。所构造的 Huffman 树的 WPL

是： WPL6×2+3×3+4×3+8×2+5×3+5×3 79。

3、Huffman 编码方法

由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个

字符的 Huffman 编码不可能是另一个字符的 Huffman 编码的前缀。

若字符集 C{a, b, c, d, e, f}所对应的权值集合为 W{8, 3, 4, 6, 5, 5}，如图所示，则字符

a,b, c,d, e,f 所对应的 Huffman 编码分别是：10，010，011，00 ，110，111。

以字符集 C 作为叶子结点，次数或频度集 W 作为结点的权值来构造 Huffman 树。规定

Huffman 树中左分支代表“0”，右分支代表“1” 。

从根结点到每个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结

点所对应的编码，称之为 Huffman 编码。

()

。