若以{4,7,8,10,12}作为叶子节点的权值构造哈弗曼树

[单选题]

若以{4,7,8,10,12}作为叶子节点的权值构造哈弗曼树，则其带权路径长度是（）

查看正确选项

Restaring

一.哈弗曼树的构建

每次在所有的数值中选择最小的两个值,相加后作为新的值放入原来的集合中,重复该过程

{4,7,8,10,12}构建的哈弗曼树如下图

23 18

12 11 8 10

4 7

二.带权路径

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

三.本题的计算

WPL = 12*2 + 4*3 +7*3 + 8*2 + 10*2 =93

发表于 2019-07-29 16:52:31 回复(0)

提交观点

问题信息

小米集团算法工程师树 2019

来自：小米2019秋招算法笔...

上传者：小小

难度：

1条回答 175收藏 3736浏览

扫一扫，把题目装进口袋