[低配 簡(jiǎn)單 好抄]借用up主，寫(xiě)一下筆記：

可以解決放哪邊和放哪層的問(wèn)題

一樣的題目：

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

第一步：從小到大排序

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

在草稿紙可以斜著排序出來(lái)

然后開(kāi)始挑前三個(gè)對(duì)比(2 3 6)，較小的兩個(gè)相加(2 3)，并將結(jié)果插入未計(jì)算順序序列

序列(5 6 7 10 19 21 32)

然后重復(fù)進(jìn)行對(duì)比，取較小的兩個(gè)相加(5 6)

然后接著重復(fù)(把結(jié)果放到未計(jì)算的序列中進(jìn)行排序、較小的相加)，不管結(jié)果是否為最大最小，只管把較小的兩個(gè)相加(7 10)

序列（7 10 17 19 21 32）

重復(fù)，挑較小的兩個(gè)相加（因?yàn)橹暗囊呀?jīng)排序過(guò)，所以不會(huì)出錯(cuò)）

序列（11 17 19 21 32）

序列（19 21 28 32）

重復(fù)排序，然后較小的兩個(gè)相加

序列（28 32 40）

最后剩下的兩個(gè)排序(40 60)，相加，得到完整樹(shù)

然后一歪頭，樹(shù)就出來(lái)了

計(jì)算WPL：

其實(shí)可以理解成黃金礦工，越深價(jià)值越大（嚴(yán)格說(shuō)就是越深就越長(zhǎng)，計(jì)算機(jī)實(shí)現(xiàn)代價(jià)越大，但是又要考慮到其本身的值，所以為什么要追求哈夫曼與WPL最?。?/p>

其實(shí)常見(jiàn)的大多數(shù)兩派，一些老師是根據(jù)層數(shù)計(jì)算，一些老師是根據(jù)邊個(gè)數(shù)進(jìn)行計(jì)算：

1.up主的每深一層就是加1，根節(jié)點(diǎn)為0層。

2.左邊長(zhǎng)值為0，右邊長(zhǎng)值為1

其實(shí)兩個(gè)意思都是一樣的，從第0層下到第一層肯定是一條邊就能實(shí)現(xiàn)，兩層兩條。所以如題值32的節(jié)點(diǎn)，是在第2層所以23*2，換一種思路它離根節(jié)點(diǎn)也就是0層就是32→60→100兩條邊，所以計(jì)算結(jié)果亦是32*2

總結(jié)步驟：

從小到大排序→挑最小的兩個(gè)相加，剩下的是未計(jì)算序列→把結(jié)果順序插入序列→挑最小的兩個(gè)相加→......→最后剩下倆相加。樹(shù)就成了

注意：如果有良好的習(xí)慣，在每次相加的時(shí)候按照相加的兩個(gè)節(jié)點(diǎn)左右大小排序，那么最后兩個(gè)相加后抓著根節(jié)點(diǎn)往上一提就出來(lái)了。如果忘了也可以先提起來(lái)然后一層一層的排序，排序時(shí)需要把排序節(jié)點(diǎn)下面的子節(jié)點(diǎn)打包一起排序。

這個(gè)方法可以不用考慮例如題中值7與值10相加后放哪的問(wèn)題，因?yàn)樵趦蓚€(gè)節(jié)點(diǎn)相加的時(shí)候已經(jīng)進(jìn)行排序了

可能當(dāng)時(shí)7和10放在了左邊，但是下一步11與17比較排序時(shí)還是會(huì)放回正確的位置的。

忘了放哪一層也不用考慮，因?yàn)榈阶詈蟀褬?shù)一提的時(shí)候7和10上面最短永遠(yuǎn)是3條邊7/10→17→28→60→100，所以一定是在第五層

實(shí)際草稿紙計(jì)算過(guò)程：

如有錯(cuò)誤請(qǐng)指正，謝謝。