已知某字符串s中共有8种字符(a,b,c,d,e,f,g,h)各种字符分别出现2次,1次,4次,5次,7次,3次,4次,9次。试把它们作为叶子结点的权值构造一棵哈夫曼树,并求出其带权路径长度(WPL)。

admin2014-10-20  20

问题 已知某字符串s中共有8种字符(a,b,c,d,e,f,g,h)各种字符分别出现2次,1次,4次,5次,7次,3次,4次,9次。试把它们作为叶子结点的权值构造一棵哈夫曼树,并求出其带权路径长度(WPL)。

选项

答案设权值ω=(1,2,3,4,4,5,7,9),Huffman树中叶子结点的数目n=8,则构造完成后,该Huffman树共有结点数为:2*n一1=15。构造的哈夫曼树如下: [*] 带权路径长度(WPL):2*(7+9)+3*(4+4+5)+4*3+5*(1+2)=98。

解析
转载请注明原文地址:https://kaotiyun.com/show/HvvR777K
0

最新回复(0)