给定6个字符a~f,它们的权值集合W={2,3,4,7,8,9},试构造关于W的一棵哈夫曼树,求其带权路径长度WPL和各个字符的哈夫曼编码。
时间: 2023-06-27 08:05:51 浏览: 577
十套数据结构模拟题1
首先,我们需要按照权值从小到大的顺序对字符进行排序,得到a=2,b=3,c=4,d=7,e=8,f=9。
接下来,我们需要构造哈夫曼树。哈夫曼树的构造过程如下:
1. 将所有字符看作一个森林,每个森林只有一个节点。
2. 在森林中选取两个权值最小的树进行合并,形成一棵新树,其根节点的权值为两棵树的根节点权值之和。
3. 将新树插入森林中,删除原来的两棵树。
4. 重复步骤2和3,直到森林中只剩下一棵树为止。
按照上述步骤,我们可以得到如下的哈夫曼树:
```
33
/ \
a 45
/ \
19 26
/ \ / \
b c d ef
```
其中,根节点的权值为所有字符的权值之和,即2+3+4+7+8+9=33。每个字符的哈夫曼编码可以通过从根节点到该字符所在节点的路径上的左右方向来判断,向左走表示编码为0,向右走表示编码为1。例如,字符a的编码为00,字符b的编码为010,字符c的编码为011,以此类推。
根据上述哈夫曼树,每个字符的哈夫曼编码如下:
```
a: 00
b: 010
c: 011
d: 10
e: 110
f: 111
```
带权路径长度WPL为各个字符的权值乘以其对应的哈夫曼编码的位数之和,即:
WPL = 2×2 + 3×3 + 4×3 + 7×2 + 8×3 + 9×3 = 89
因此,该哈夫曼树的带权路径长度为89。
阅读全文