数据结构——五分钟搞定哈夫曼树，会求WPL值，不会你打我

[低配 简单 好抄]借用up主，写一下笔记：

可以解决放哪边和放哪层的问题

一样的题目：

19，21，2，3，6，7，10，32

第一步：从小到大排序

2，3，6，7，10，19，21，32

在草稿纸可以斜着排序出来

然后开始挑前三个对比(2 3 6)，较小的两个相加(2 3)，并将结果插入未计算顺序序列

序列(5 6 7 10 19 21 32)

然后重复进行对比，取较小的两个相加(5 6)

然后接着重复(把结果放到未计算的序列中进行排序、较小的相加)，不管结果是否为最大最小，只管把较小的两个相加(7 10)

序列（7 10 17 19 21 32）

重复，挑较小的两个相加（因为之前的已经排序过，所以不会出错）

序列（11 17 19 21 32）

序列（19 21 28 32）

重复排序，然后较小的两个相加

序列（28 32 40）

最后剩下的两个排序(40 60)，相加，得到完整树

然后一歪头，树就出来了

计算WPL：

其实可以理解成黄金矿工，越深价值越大（严格说就是越深就越长，计算机实现代价越大，但是又要考虑到其本身的值，所以为什么要追求哈夫曼与WPL最小）

其实常见的大多数两派，一些老师是根据层数计算，一些老师是根据边个数进行计算：

1.up主的每深一层就是加1，根节点为0层。

2.左边长值为0，右边长值为1

其实两个意思都是一样的，从第0层下到第一层肯定是一条边就能实现，两层两条。所以如题值32的节点，是在第2层所以23*2，换一种思路它离根节点也就是0层就是32→60→100两条边，所以计算结果亦是32*2

总结步骤：

从小到大排序→挑最小的两个相加，剩下的是未计算序列→把结果顺序插入序列→挑最小的两个相加→......→最后剩下俩相加。树就成了

注意：如果有良好的习惯，在每次相加的时候按照相加的两个节点左右大小排序，那么最后两个相加后抓着根节点往上一提就出来了。如果忘了也可以先提起来然后一层一层的排序，排序时需要把排序节点下面的子节点打包一起排序。

这个方法可以不用考虑例如题中值7与值10相加后放哪的问题，因为在两个节点相加的时候已经进行排序了

可能当时7和10放在了左边，但是下一步11与17比较排序时还是会放回正确的位置的。

忘了放哪一层也不用考虑，因为到最后把树一提的时候7和10上面最短永远是3条边7/10→17→28→60→100，所以一定是在第五层

实际草稿纸计算过程：

如有错误请指正，谢谢。