给定一组结点及对应的权值,创建一棵哈夫曼树,输出每个结点的哈夫曼编码,和整棵树的WPL值。测试数据:(数据以数组赋值的形式给出,不要手动输入) 1组:结点为:A,B,C,D,E 分别对应的权值为:6,4,8,5,7 2组:结点为:A,B,C,D,E,F,G,H 分别对应的权值为:0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10
时间: 2023-06-13 08:03:03 浏览: 146
哈夫曼树的创建
1. 对于第一组数据,我们可以按照权值从小到大排序,得到B、D、E、A、C的顺序。然后,我们先将B和D合并,得到一个新的结点BD,权值为9;再将E和A合并,得到一个新的结点EA,权值为13;最后将EA和BD合并,得到根结点,权值为22。构建的哈夫曼树如下图所示:
```
22
/ \
13 9
/ \ / \
E A B D
```
对于每个结点,我们可以从根结点开始往下走,如果走左子树就标记0,走右子树就标记1,最终得到每个结点的哈夫曼编码:
A:0
B:10
C:111
D:110
E:11
整棵树的WPL值为(6*1 + 4*2 + 8*2 + 5*2 + 7*2) = 60。
2. 对于第二组数据,我们按照权值从小到大排序,得到C、F、D、H、A、B、G、E的顺序。然后,我们先将C和F合并,得到一个新的结点CF,权值为0.05;再将D和H合并,得到一个新的结点DH,权值为0.16;接着将CF和DH合并,得到一个新的结点CFDH,权值为0.21;再将E和G合并,得到一个新的结点EG,权值为0.11;接着将B和A合并,得到一个新的结点BA,权值为0.26;最后将BA和EG合并,得到一个新的根结点,权值为0.57。构建的哈夫曼树如下图所示:
```
0.57
/ \
0.26 EG
/ \ / \
BA A B CFDH
/ \ / \
G E C DH
/ \
H F
```
对于每个结点,我们可以从根结点开始往下走,如果走左子树就标记0,走右子树就标记1,最终得到每个结点的哈夫曼编码:
A:1110
B:1111
C:10
D:011
E:110
F:0101
G:1100
H:0100
整棵树的WPL值为(0.07*4 + 0.19*4 + 0.02*5 + 0.06*4 + 0.32*3 + 0.03*5 + 0.21*3 + 0.10*4) = 3.46。
阅读全文