首页 > 试题广场 >

由权值为3,6,7,2,5,1的叶子结点生成一棵哈夫曼树，它

[单选题]

由权值为3,6,7,2,5,1的叶子结点生成一棵哈夫曼树，它的带权路径长度为： 

  • 57
  • 72
  • 61
  • 48
添加回答
推荐
冰诺头像 冰诺
带路径长度为：7*2+6*2+5*2+3*3+2*4+1*4 = 57，哈弗曼树为：
编辑于 2016-05-07 15:54:55 回复(5)
大胞头像 大胞
构造哈夫曼树步骤是，选择两个权值最小的点构造树，新树根权值为左右子树权值之和，新的权值放回到序列中，继续按照上述不走构造树，直到只有一颗树为止。 树带权路径长度 就是每个叶子结点的权值*高度之和。所以 （5+ 6+ 7）*2+3*3+（1+2）*4=57
发表于 2015-08-09 19:47:16 回复(0)
牛客142721号头像 牛客142721号
答案为61的忽略了一点，要把新合成的值放回序列，再在序列中找最小的两个数
发表于 2017-04-06 11:45:59 回复(1)
BackWit头像 BackWit
这题好，之前没看清楚赫夫曼树的构造过程。
排序
1 2 3 5 6 7
1 2->3
3 3 5 6 7
3 3-> 6
5 6 6 7
5 6-> 11
6 7 11
6 7->13
11 13->25
这样就构成了 上面 冰诺 答案中的图。

发表于 2016-08-23 16:51:27 回复(1)
信明天头像 信明天
发表于 2017-03-30 18:18:25 回复(3)
爱吃青菜皮卷面的byr头像 爱吃青菜皮卷面的byr
本题的关键是如何构建哈夫曼树：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为W1,W2.。。。。Wn 。则哈夫曼树的构造规则为：
1.将W1,W2.....Wn看成是有n颗树的森林
2.在森林中选出两个根节点的权值最小的树合并，作为一棵树的左右子树，且新树的根节点权值为其左右子树 根节点权值之和
3.从森林中删除选取的两颗树，并将新树加入森林
4.重复2.3

发表于 2017-02-16 15:35:14 回复(0)
baruch_cheng头像 baruch_cheng
答案为A？（5+ 6+ 7）*2+3*3+（1+2）*4=57
发表于 2015-08-07 17:10:46 回复(0)
Seaworth头像 Seaworth
发表于 2020-01-07 15:30:58 回复(0)
牛客4934058号头像 牛客4934058号 
快速画出哈夫曼树/霍夫曼树/最优树。这个很好理解。
https://jingyan.baidu.com/article/a501d80c16dfa0ec620f5e70.html
发表于 2017-03-20 17:39:15 回复(0)
FriedaEndora头像 FriedaEndora
答案C  7*1+6*2+5*3+3*4+（1+2）*5=61
发表于 2015-08-08 10:10:02 回复(9)
牛客218196695号头像 牛客218196695号

1 构造哈弗曼树
2 带权路径长度 就是每个叶子结点的权值高度之和。所以 （5+ 6+ 7）2+33+（1+2）4=57

发表于 2020-05-16 10:21:38 回复(0)
Amaterasu.Z头像 Amaterasu.Z

能否有人告知一下，树的形状是否不唯一？
当序列为6,7,5,6（生成的）时，应该选择哪一个6呢？如果选择的是生成的6，就得到上一种树，如果选题目中给的叶子节点6，得到的就是下面
发表于 2018-04-06 10:35:38 回复(1)
kaze头像 kaze
按haffman编码的画法画一遍……
发表于 2016-09-05 09:45:49 回复(0)
白子画头像 白子画
答案A。
发表于 2015-08-22 14:04:50 回复(0)
Yano_nankai头像 Yano_nankai
牛客上的答案怎么老变啊……

我上次看的时候，选的不是61，错了；
这次选了61，错了。
发表于 2015-08-19 09:40:03 回复(1)
Prokias头像 Prokias
（5+6+7）*2 + 3*3 + （1+2）*4 = 57
发表于 2015-08-07 17:35:54 回复(0)
提交观点

问题信息

树
来自：360公司2015软件...
上传者：小小
难度：
16条回答 21193浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号