给定权值集合{1, 3, 6, 7, 11, 12, 16},构造相应的哈夫曼树并计算带权路径长度
作者&投稿:弘金 (若有异议请与网页底部的电邮联系)
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。
n个权值分别设为
w1、w2、…、wn,则哈夫曼树的构造规则为:
(1)
将w1、w2、…,wn看成是有n
棵树的森林(每棵树仅有一个结点);
(2)
在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止
根据上述方法,得到的哈夫曼树,先选1
3
得到4,新的森林即
4
5
6
7
8,选择4
5
得到9,新的森林变为6
7
8
9,选择6
7
得到13,森林变为8
9
13,选择8
9得到17
变为
13
17,选择13
17得到30,只剩最后一个课树。
[30]
/
\
[17]
[13]
/
\
/
\
(8)
[9]
(6)
(7)
/
\
[4]
(5)
/
\
(1)
(3)
图片上传不了,按照上述方式弄了一下,()表示叶节点,到时候你用圈就行,[]表示是其下面左右子树的根。
树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为wpl
wpl=
1*4
+3*4
+5*3
+
8*2
+
6*2
+
7*2
=
73
蔡嵇板蓝: 手机发的,画不了图,看得见吗?树的画法:取最小的两个数3,6做孩子,小的在左边,3+6=9,9为父结点.在剩下的数中包括9,取最小的两个来画树,即7,8.重复直到画完.平均长度=3的长度*3%+6的长度*6%+.....长度从根结点往下数.
西沙群岛17033343152: 给定一组权值3.3.7.7.11,13.17试构造一棵哈夫曼树并计算出带权路径长度 - ?
蔡嵇板蓝:[答案] 哈夫曼树是: 61 / \ 26 35 / \ / \ 13 13 17 18 / \ / \ 6 7 7 11 / \3 3树带权路径长度 = 3 * 4 + 3 * 4 + 7*3 + 13 * 2 ...
西沙群岛17033343152: 设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树 - ?
蔡嵇板蓝: 设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树 夫曼树的构造: (1)根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn},其中Ti中只有一个权值为wi的根结点,左右子树为空; (2)在F中...
西沙群岛17033343152: 给定权值(15,3,14,2,6,9,16,17),构造相应的哈夫曼树 - ?
蔡嵇板蓝:[答案] Huffman 编码 一、实验目的 熟悉Huffman编码方法. 了解并弄懂Huffman编码实现信息的无损压缩原理. 二、实验要求 熟悉C... 1.根据给定的n个权值(w1,w2,…,wn)构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带树为Ti的根结...
西沙群岛17033343152: 给定一组权值3.3.7.7.11.13.17试构造一颗哈夫曼树,并计算出带权路径长度 - ?
蔡嵇板蓝: 七个权值3 3 7 7 11 13 17
西沙群岛17033343152: 给定一组权值(5,9,11,2,7,16),试设计相应的哈夫曼树,并求出该二叉树的带权路 - ?
蔡嵇板蓝: for(int i = 0; i
西沙群岛17033343152: 设给定一个权值集合W=(3,5,7,9,11), - ?
蔡嵇板蓝: 7835/ \ 20/ \15 9 11/ \8 7/ \ 3 5 wpl=27*2+8*3=78
西沙群岛17033343152: 急急 有悬赏 哥定权值集合11.3.14.2.7.9.16构造相应的huffman树,计算他的带权路径长度WPL - ?
蔡嵇板蓝: 你可以自行构造一下huffman树,huffman树构造:一、对给定的n个权值构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空.二、在F中选取两棵根结点权值最小的树作为新...
西沙群岛17033343152: 给定叶子权值 135678并构造哈弗曼树并计算其代权路径长度? - ?
蔡嵇板蓝: 恩,首先, 选择(1,3,5,6,7,8)中最最小的两个, 构成树;即 1,3 (a) 4 | | 1 3 然后 就变成了(4,5,6,7,8),选两个最小的,即4,5 (b) 9 | | 4 5 | | 1 3, 于是就变成了(9,6,7,8),重复,选两个最小的,即是6,7, 即: (c) 13 | | 6...
西沙群岛17033343152: 给定权值(7,18,3,32,5,26,12,8),构造相应的哈夫曼树. - ?
蔡嵇板蓝: 按权值大小排列后 3 5 7 8 12 18 26 32 只要按照将最小的两个合并, 合并后的值再入列中(最小的两个出列), 至到列中只有一个值.按上面要求构造哈夫曼树如下: /////树列完后, 可取左树编码 为0, 右为 1, (左为 1, 右为 0 亦可)[3]````...