我要招人

去企业版

首页 > 试题广场 >

若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则

[单选题]

若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。

```
24
```
```
30
```
```
53
```
```
69
```

查看答案及解析

推荐

eagle

构造方法是每次取最小的两个数，合并成一个数，然后循环这种做法，直到只剩一个点为止。构造的树是

17 13

8 9 6 7

4 5

所以带权路径长度是（除根节点外其它节点的和？）69

编辑于 2015-01-12 18:04:08 回复(4)

牛客-007

答案：D
树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和。
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
构造哈夫曼树后，
4,5的编码长度为3,
6,7,8的编码长度为2
（4+5）*3+（6+7+8）*2=27+42=69

发表于 2015-01-28 16:28:20 回复(0)

牛客1465584号

我猜很多选30的人估计只是把哈夫曼树构造出来了，但是忘了其带权路径长度的定义了。

路径长度就是从树根到每一结点的路径长度之和

带权路径长度就是叶子节点的权重乘以路径长度的累加和。

发表于 2018-12-06 12:44:11 回复(0)

羁士

带权路径长度是指叶子节点的带权路径长度之和

发表于 2017-06-15 11:00:56 回复(0)

thfeng

哈夫曼树为：

。

。。

8 。 6 7

4 5

发表于 2016-07-28 17:11:20 回复(0)

已注销

发表于 2016-10-31 13:47:58 回复(5)

rs勿忘初心

全程手敲的，只为理解这个过程。

以学生成绩为例进行分析，正常的学生成绩的分布范围如下：

下面的图是普通的学生成绩判断，粗略的看什么问题，可是通常都认为，一张好的考卷应该是让学生的 成绩大部分处于中等或良好的范围 ，优秀和不及格都应该比较少才对。而这个判断方式，就使得所有的成绩都需要先判断是否及格，再逐级比较而上得到结果。输入量很大时，其实算法是有效率问题的。

有没有好一些的办法呢？仔细观察发现，中等成绩（70-79之间）比例最高，其次是良好成绩，不及格的所占比例最少。我们把上图这棵二叉树重新进行分配，改成如下的判断。

从图中感觉效率要高一些，到底高多少呢?这样的二叉树又是如何设计出来的呢？这就是下面要说的赫夫曼定义及原理。

我们先把这两棵二叉树简化成 叶子结点带权 的二叉树（树结点间的边相关的数叫做权Weight），分别如下图所示，其中A表示不及格、B表示及格、C表示中等、Db表示良好、E表示优秀。每个叶子的分支线上的数字就是刚才我们提高的五级分制的成绩所占百分百。

赫夫曼说：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为 路径长 度。 树的路径长度 就是从树根到每一结点的路径长度。二叉树a的路径长度为20，二叉树b的树路径长度就为16。

如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。 带权路径长度WPL最小的二叉树称为赫夫曼树 。

二叉树a的WPL=5*1+15*2+40*3+30*4+10*4=315

二叉树b的WPL=5*3+15*3+40*2+30*2+10*2=220

说明了什么？如果现在有10000个学生的百分制成绩需要计算五分制成绩，用二叉树a的判断方法，需要做31500次的比较，而二叉树b的判断方法，只需要比较22000次的比较，差不多少了三分之一量，在性能上不止提升一点点。

那么问题来了，如何构造出b这样的树呢？这样的树是不是最优的赫夫曼树呢？

赫夫曼树构造步骤：

1、先把有权值的叶子结点按照从小到大的顺序排序成一个有序序列，即：A5、E10、B15、D30、C40。

2、取头两个权值最小的结点作为一个新节点N1的两个子节点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子，新节点的权值为两个叶子节点权值的和5+10=15。

3、将N1替换A与E，插入有序序列中，保持从小到大排序。即：N115，B15，D30，C40。

4、重复步骤2。将N1与B作为一个新结点N2的两个子节点，如下图所示。N2的权值=15+15=30。

5、重复上述步骤，直到剩余结点数为1。即完成了赫夫曼树的构造。

此时的二叉树的带权路径长度WPL=40*1+30*2+15*3+10*4+5*4=205。比刚开始构造出来的b二叉树的少15，显然此时构造出来的二叉树才是最优的赫夫曼树。不过显示总是比理想要复杂得多，上图虽然是赫夫曼树，但由于每次判断都要比较两次（如根节点就是a<80&&a>=70,两次比较才能得到y或n的结果），所以总体性能上，反而不如二叉树b的性能高。

发表于 2017-07-08 16:46:10 回复(2)

Cris_Lee

感觉这篇博客写的很清晰，系统~供大家参考！

http://www.cnblogs.com/mcgrady/p/3329825.html

发表于 2018-08-28 10:33:30 回复(0)

Ctrl+F5

路径：一个节点到另一个节点之间的分支构成路径

路径长度：节点到节点之间分支的数目

树的路径长度：根节点到每个节点路径长度之和

节点的带权路径长度：如果某个节点附带一个权值，则该节点到树根的路径长度和权值的积称为该节点的带权路径长度

树的带权路径长度：每个叶子节点的带权路径长度之和

发表于 2017-03-30 10:01:02 回复(0)

尐短腿

有人得76吗？？？

发表于 2016-05-26 16:34:13 回复(5)

提交观点

问题信息

树

来自：4399游戏2015校...

上传者：小牧魔法袋

难度：

10条回答 759收藏 43549浏览

若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则

问题信息

热门推荐

相关试题