[已解决]哈夫曼树构造，求助大神！不懂层次的放置问题，是使最后合成有一个根么还是越前越好

dreamlike

附题目：有8个字母组成的电文，这些字母的频率分别是0.07,0.19,0.02,0.06,0.32, 0.03,0.21,0.10,画出哈夫曼树,计算出WPL值，为这8个字母设计哈夫曼编码。
我懵逼的点是当新合成的结点比旧根里的两个都小的话，是要放在和新结点的子节点同一个层次还是和新结点同个层次，大神们可以理解我不懂的点么？我开始画着画着就发现合成不了根结点，然后就改到能合成一个根，脑子转不过来了啊啊，最后我求出的WPL值是2.61，应该没有错误吧

最佳答案

月排行榜 / 总排行榜

Hoiste

2021-5-9 14:35:58

为了避免麻烦我先把小数点去掉吧，按照思路来画。
这8个权从小到大排列是2,3,6,7,10,19,21,32，这是第一步。
其中最小两个权2,3提出来，组成2,3合成5的树，这时候把2，3从上面数组中去掉，替换成5，也就是5,6,7,10,19,21,32.
现在最小的两个权是5,6，同样提出来组成5,6合成11的树，现在就是11,7,10,19,21,32了。
这时候因为7,10都比新合成出来的11值小，所以提取出来两个最小的权是7,10单独变成一个分支合成17，且7和10是和5,6放在同一层次的。
接下来步骤思路就是上面这样子继续下去了。

跳转到最佳答案楼层

Hoiste

这个说有点难，我画一下看看。WPL的话我算了下也是2.61

Hoiste

构造哈夫曼树原则是从小往大进行，每一个层次要求权小的在左，向右看依次增大。明白这个原则的话其实就不会疑惑了。

Hoiste

另外哈夫曼树的结构并没有唯一答案，只要原则上没有错误，应该就不会有问题的。

dreamlike

Hoiste 发表于 2021-5-9 14:14
构造哈夫曼树原则是从小往大进行，每一个层次要求权小的在左，向右看依次增大。明白这个原则的话其实就不会 ...

所以说其实是要尽可能往上进行构造么？我不懂的是层次问题。
另外我翻看了课本，哈夫曼树对同个层次的左、右子树是没有限制要求，可以颠倒的……

Hoiste

dreamlike 发表于 2021-5-9 14:21
所以说其实是要尽可能往上进行构造么？我不懂的是层次问题。
另外我翻看了课本，哈夫曼树对同个层次的左 ...

我感觉刚刚有点答非所问，我整理一下再给你讲讲

Hoiste

为了避免麻烦我先把小数点去掉吧，按照思路来画。
这8个权从小到大排列是2,3,6,7,10,19,21,32，这是第一步。
其中最小两个权2,3提出来，组成2,3合成5的树，这时候把2，3从上面数组中去掉，替换成5，也就是5,6,7,10,19,21,32.
现在最小的两个权是5,6，同样提出来组成5,6合成11的树，现在就是11,7,10,19,21,32了。
这时候因为7,10都比新合成出来的11值小，所以提取出来两个最小的权是7,10单独变成一个分支合成17，且7和10是和5,6放在同一层次的。
接下来步骤思路就是上面这样子继续下去了。

dreamlike

Hoiste 发表于 2021-5-9 14:35
为了避免麻烦我先把小数点去掉吧，按照思路来画。
这8个权从小到大排列是2,3,6,7,10,19,21,32，这是第一步 ...

可以的话，能解释一下后面的19和21为什么不放在和11和17同一层呢？

Hoiste

dreamlike 发表于 2021-5-10 16:48
可以的话，能解释一下后面的19和21为什么不放在和11和17同一层呢？

11和17是合成的节点，只是前面各个小值权的相加，不包含在八个字母频率里面，这意味着我们不应该对11和17进行编码，而19,21是需要进行编码的。如果和19,21这两个需要进行编码的放在同一层，那么11+17合成的28设为1，19+21合成40设为0，就会导致编码的1那端之下的11,17这两个值也进行编码，就浪费了空间了。而如果把19,21放到上一层，那么编码就可以跳过11,17这一层了。不知道这么说能不能明白。

dreamlike

Hoiste 发表于 2021-5-11 10:10
11和17是合成的节点，只是前面各个小值权的相加，不包含在八个字母频率里面，这意味着我们不应该对11和 ...

是我没想到的点，好高深哈哈，不过可不可以单纯想就是为了WPL值最小啊（从哈夫曼树的最小原则出发）

Hoiste

dreamlike 发表于 2021-5-11 20:24
是我没想到的点，好高深哈哈，不过可不可以单纯想就是为了WPL值最小啊（从哈夫曼树的最小原则出发）

可以的

dreamlike

Hoiste 发表于 2021-5-11 20:52
可以的

谢谢大神！