首页 > 试题广场 >

以数据集{1,6,8,2,9,4}为权值构造一棵赫夫曼树，其

[填空题]
以数据集{1,6,8,2,9,4}为权值构造一棵赫夫曼树，其带权路径长度为1
查看正确选项
添加回答
百度内推官_Flyer头像 百度内推官_Flyer
构造后的赫夫曼树如下：

                    30
       13                    17
6              7          8        9            --------------  2
          3        4                             --------------- 3
       1   2                                     --------------- 4

所以带权路径长度 length =  (6 + 8 + 9) * 2 + 4 * 3 + (1 + 2) * 4
发表于 2019-08-09 09:38:59 回复(7)
陌陌内推官头像 陌陌内推官

构造出哈夫曼树，有两种计算方式。

一：带权路径长度=叶子节点权值×（高度-1）之和

二：带权路径长度=非叶子节点权值之和

发表于 2019-08-11 22:05:18 回复(0)
_老地方头像 _老地方
70
发表于 2019-11-14 23:51:53 回复(0)
小小趴菜头像 小小趴菜
看到评论里很多问为什么这样构造树的，我觉得可能是因为这些同学没有好好看哈夫曼树的构成方法。
哈夫曼树的构造步骤如下：
用给定的n个权值{w1,w2,…wn}对应的n个节点构成n个二叉树的森林F={T1,T2,…Tn}，将F中的数按权值从小到大排列；取T1和T2合并组成一棵树，使其根节点的权值T=T1+T2，再按大小插入到F，反复此过程，直到只有一棵树为止。
发表于 2019-09-10 11:42:19 回复(0)
lifan96头像 lifan96
带权路径长度为叶子节点*到根节点的距离，相加之和
发表于 2019-08-20 20:54:55 回复(0)
尼根的猜想头像 尼根的猜想
16+18+12+12+10=46+22=68
发表于 2019-12-03 22:22:28 回复(0)
卖女孩的小火柴20181211163556头像 卖女孩的小火柴20181211163556

30

/ \

13 17

/ \ / \

7 6 8 9

/ \

3 4

/ \

1 2

(1+2)×4+4×3+(6+8+9)×2=70


发表于 2019-10-18 12:50:47 回复(0)
漠景头像 漠景
70
发表于 2019-09-10 23:36:20 回复(0)
KINGChAinz头像 KINGChAinz
70
发表于 2019-09-07 15:23:34 回复(0)
头发最多的程序媛头像 头发最多的程序媛

47

发表于 2019-08-30 16:16:26 回复(0)
让我留在成都就好头像 让我留在成都就好
为什么不是49？
               24
         9            15
                    8        7
                          4       3
                                 1     2             
发表于 2019-08-20 20:06:12 回复(2)
提交观点

问题信息

C++工程师 瓜子二手车 树 2019 Java工程师
上传者：小小
难度：
11条回答 4338浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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