在数据压缩编码的应用中,Huffman算法可以用来构造具有(53)的二叉树,这是一种采用了(54)的算法。(4

Question

在数据压缩编码的应用中，Huffman算法可以用来构造具有(53)的二叉树，这是一种采用了(54)的算法。

(48)

A．前缀码

B．最优前缀码

C．后缀码

D．最优后缀码

Answer 1

正确答案：B
解析：Huffman树是指权值为w1、w2、…、Wn的n个叶予节点的二叉树中带权路径长度最小的二叉树。
  构造Huffman树的算法如下：
  . 给定n个节点的集合，每个节点都带权值；
  . 选两个权值最小的节点构造一棵新的二叉树，新的二叉树的根节点的权值就是两个子节点权值之和：
  . 从n个节点中删除刚才使用的两个节点，同时将新产生的二叉树的根节点放在节点集合中；
  . 重复(b)(c)，直到只有一棵树为止。
  Huffman编码，在编码过程中要考虑两个问题，一是数据的最小冗余编码问题，而是译码的唯一性问题，在实际的应用中，各个编码的字符的出现频率不同，希望用最短的编码来表示出现频率大的字符而用较长的编码来表示出现频率较少的字符，从而使整个编码序列的总长度最小，这就是最小冗余编码问题，Huffman编码就解决了这个问题，根据权值或概率的大小来构建Huffman树，然后左分支用0表示而右分支用1表示，就形成了编码序列。