首页 > 试题广场 >

有以下5个叶子节点1,1,3,2,5构成的哈夫曼树的带权路径

[单选题]
有以下5个叶子节点1,1,3,2,5构成的哈夫曼树的带权路径长度为（） 
  • 24
  • 26
  • 23
  • 25
查看答案及解析
添加回答
唐子玄头像 唐子玄
  • 结点带权路径长度=该结点到根的路径长度×该结点权
  • 哈夫曼树:给定叶子权值和叶子数 可以构造出不同结构的二叉树 其中带权路径长度最小的二叉树称为最优二叉树 哈夫曼树是一种最优二叉树
  • 哈夫曼树算法
  1. 根据n个权值构造具有n棵二叉树的森林---森林中的每颗二叉树都只有一个根结点 结点的数据域为一个权值 该结点左右子树都是空
  2. 在森林中选出2棵根结点权值最小的树A B(这样的树不止2棵---任选2棵)---创建一个新结点作为A B的根结点 A B分别作为根结点的左右孩子(权值小的在左边大的在右边 这样规定 哈夫曼树就唯一了)---将A B的权值相加作为根结点的权值---森林中产生一颗新树C(:~有左右孩子各1)
  3. 在森林中继续选出2棵根结点权值最小的树(2.中产生的C也在选择范围内)---重复2.的过程 直到将森林中所有的数合并成一颗二叉树---这颗二叉树就是哈夫曼树
按照上述算法可以得到如下哈夫曼树 其带权路径长度= 5*1+3*2+2*3+(1+1)*4 =25 选D

发表于 2015-11-30 18:18:10 回复(0)
scanf_cin头像 scanf_cin
先从数组中选出两个最小的数1,1作为两个路径的权值，然后将这两个数相加放到数组中就是2,3,2,5，然后在从中选出最小的两个数2,2作为两个路径的权值。再将这两个数相加放到数组中得到4,3,5.然后在选出两个最小的数4,3作为两个路径的权值。在将这两个数的和放到数组中，得到7,5这就是最后的两个权值。将这些权值全部加起来就是1+1+2+2+4+3+7+5=25，这就是整个路径的长度，所以选d
发表于 2015-11-30 15:15:31 回复(0)
shizheng头像 shizheng
一定要注意哈夫曼树的带权路径长度只需要计算叶子节点的带权路径长度之和
发表于 2016-03-20 15:46:23 回复(0)
蓝波aiku头像 蓝波aiku
结点带权路径长度=该结点到根的路径长度*该结点的权
发表于 2018-03-20 14:30:00 回复(0)
我是程序员小贱头像 我是程序员小贱
一定要注意哈夫曼树的带权路径长度只需要计算叶子节点的带权路径长度之和，画出图以后就是1*4+1*4+2*3+3*2+5*1=25
发表于 2019-05-29 15:18:46 回复(0)
鸣酱头像 鸣酱
我这道题算到了，哈夫曼树是没有度为1的节点的所以在构造完哈夫曼时要注意否则又错了
发表于 2019-04-09 08:31:54 回复(0)
卤五花头像 卤五花
根据如图的快速求解哈夫曼编码的方法可以得出带权路径长度为5*1+3*2+2*3+1*4+1*4=25
发表于 2019-03-12 21:11:08 回复(0)
GaloisGalois头像 GaloisGalois
每次选出两个最小的数 加起来求和之后放回去继续选出两个最小的数 直到最后只有两个数 也选出来 将所有选出的数加起来求和即为结果。
发表于 2018-10-25 17:17:22 回复(0)
josan头像 josan
真想知道这种题目有没有什么快速解决的方法，每次画图，然后求解，好烦···
发表于 2017-07-09 13:06:06 回复(0)
提交观点

问题信息

树
来自：迅雷2016研发工程师笔试题
上传者：SunburstRun
难度：
9条回答 14202浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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