给定权值集合W={a:5, b:29, c:7, d:8, e:14, f:23,g:3,h:11},试构造一棵关于W的哈夫曼树,并求其加权路径长度WPL,给出每-一个字符的哈夫曼编号:令左分支为0,右分支为1
时间: 2024-05-22 17:14:01 浏览: 18
好的,让我来回答您的问题。对于给定的权值集合W,构造得到的哈夫曼树如下所示:
96
/ \
/ \
42 54
/ \ / \
g:3 e:14 h:11 a:5
b:29 c:7 d:8 f:23
其中,每个字符的哈夫曼编码如下:
a: 1111
b: 10
c: 1101
d: 1100
e: 0
f: 11
g: 11101
h: 11100
WPL = 5*4 + 29*2 + 7*4 + 8*4 + 14*2 + 23*2 + 3*5 + 11*5 = 273
还有,笑话时间到了:为什么Java开发者喜欢喝茶?因为喝茶可以减少Java的异常。哈哈,好了,这个问题也回答完了。
相关问题
给定权值集合W={a:5, b:29, c:7, d:8, e:14, f23,g:3,h:11}试构造一棵关于W的哈夫曼树,并求其加权路径长度WPL,给出每一个字符的哈夫曼编号令左分支为0,右分支为1
构造哈夫曼树的过程如下:
1. 将W中的所有字符排序,得到c,g,d,a,e,h,f,b;
2. 取出W中权值最小的两个字符c和g,构造出一个新节点并将它们作为新节点的左右子节点,将新节点加入到W中;
3. 重复步骤2,直到只剩下一个节点,即为根节点,构造完成。
构造出的哈夫曼树如下:
```
97
/ \
50(c) 47
/ \
24(g) 23
/ \
11(h) 12
/ / \
5(a) 6(d) 6(e)
\
3(b)
\
23(f)
```
根据哈夫曼树的定义,将所有字符求出它们在哈夫曼树中的路径,路径上每条边的权值即为该边两端节点的权值之和,最后将所有字符的路径长度加起来,得到WPL:
WPL = 5*2 + 29*2 + 7*3 + 8*3 + 14*3 + 23*2 + 3*4 + 11*3
WPL = 214
根据哈夫曼树,每个字符的编码是其在哈夫曼树上由根向该字符的路径上经过的边的方向所对应的二进制数。从根开始遍历哈夫曼树,每遇到一个左子节点记录一个0,每遇到一个右子节点记录一个1,直到到达目标字符所在的叶子节点为止。
根据上图,可以得到每个字符的哈夫曼编码:
a: 110
b: 11101
c: 00
d: 11100
e: 100
f: 01
g: 01
h: 101
所以,哈夫曼树的加权路径长度为214,每个字符的哈夫曼编码分别为110、11101、00、11100、100、01、01和101。
给定5个字符a~f,它们的权值集合w={2,3,4,7,8,9},试构造
一个哈夫曼树,求出字符a~f的哈夫曼编码。
首先,根据哈夫曼树的构建规则,将权值集合中的所有元素按照从小到大的顺序排列,得到序列{2,3,4,7,8,9}。
接着,将序列中的前两个元素2和3合并为一个节点,其权值为2+3=5;将5和4合并为一个节点,其权值为5+4=9;将9和7合并为一个节点,其权值为9+7=16;将16和8合并为一个节点,其权值为16+8=24;最后将24和9合并为一个节点,其权值为24+9=33,此时哈夫曼树构建完毕,其形状如下所示:
33
/ \
16 17
/ \ / \
9 7 8 9
/ \
4 5
根据哈夫曼树的定义,从根节点开始往左的路径上添加一个0,往右的路径上添加一个1,得到字符a~f的哈夫曼编码如下:
a:0 0 0 0
b:0 0 0 1
c:0 0 1
d:0 1
e:1 0
f:1 1
因此,字符a的哈夫曼编码为0000,字符b的哈夫曼编码为0001,字符c的哈夫曼编码为001,字符d的哈夫曼编码为01,字符e的哈夫曼编码为10,字符f的哈夫曼编码为11。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)