构造哈夫曼树:以数据集(3,4,5,8,11,18,20,30)为结点,构造一棵哈夫曼数,并求其带权路径长度.
人气:465 ℃ 时间:2020-06-02 14:21:51
解答
构建哈夫曼树的步骤:
1,选取结点(node)中最小的两个,相加,构成一个新结点
2,重复第一步,直至所有结点都在同一个树型里面.
所以,大概构成后就是这样
.81
.0/ \1
./ \
.31 50
.0/ \1 0/\1
./ \ / \
.18 13 20 30
.0/ \1 0/ \1
./ \ / \
.7 11 5 8
.0/ \1
./ \
.3 4
从最下面向上读,node3和node4是初始数据里面最小的两个,
它们组成一个新结点7,
然后再重复相同的步骤,在新数据里面,7和11是最小,他们组成18,
原始数据里面的18可以消去.
重复步骤直至所有结点在同一个树型里面
现在看看
3的哈夫曼编码就是0000,而数字最大的30编码就是11
推荐
- 给定一组权值W=(14.15.7.3.20.4)请构造出相应的哈夫曼树,并计算其带权的路径长度WPL?
- 有七个带权节点,其权值分别是3 7 8 2 6 10 14,以他们的叶子为结点构造哈夫曼树,计算带权路径长度
- 由分别带权为9,2,5,7的4个叶节点构造一棵哈夫曼树,该树的带权路径长度为()?
- 数据结构与算法:以数据集{4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树,其带权路径长度为?
- 根据集合(3,6,11,9,5,15,18)构造哈夫曼树的带权路径长度!
- 《水浒传》一书中,除言忠义而外,亦教人以“孝”,其中写得最明显的是以下哪组?( ) A王进、李逵、宋江、公孙胜 B武松、李逵、宋江、公孙胜 C王进、李逵、宋江、武松 D林冲、李逵、宋江、公孙胜
- 在Rt△ABC中,∠BAC=90°,AB=AC=2,以AC为一边,在△ABC外部作等腰Rt△ACD,求线段BD的长
- 210/15-210/42用简便计算方法
猜你喜欢