浙江大學-數據結構-選講Huffman Codes-7.4.2

02-25

上一節分析了Huffman樹的特點，那麼確定了核心演算法就分兩步，第一要驗證它的長度是不是等於最優編碼的長度，第二就來檢查它是不是沒有歧義的前綴碼，那麼首先我們就得先計算出標準答案，最優編碼的長度到底是多少？這個計算應該是比較簡單的，前面的課程中已經給過了哈夫曼的代碼，就是如何去建立一棵哈夫曼樹，那麼在這我們就申明一棵哈夫曼樹，然後用哈夫曼演算法去生成它。

那要注意到，在調用哈夫曼演算法的時候，就必須要有一個最小堆，所以呢，在前面我先得申明一個最小堆，然後我調用現成的CreateHeap去創建一個空的，容量為N的最小堆

然後接下來呢，我們要做的事情就是把讀進來的頻率讀到堆的數組裡面去，為後面建立一個最小堆來做好準備，建立最小堆這件事情，是在哈夫曼演算法裡面完成的，

大家回憶一下，哈夫曼演算法裡面先建立一個最小堆，然後每次從裡面彈出兩個最小的結點，然後生成一棵新的樹，再把它壓回去，諸如此類，那麼調用完了哈夫曼之後，我們就生成了一棵哈夫曼樹，但是並不等於說我們就得到了最優的編碼長度，這棵樹是有了，編碼長度還是要我們另外去算一下的，需要我們另外去寫一個函數，比如說取名叫WPL,

返回的CodeLen就應該是整個這棵哈夫曼樹所對應的最優編碼的總長度，這個WPL要怎麼個寫法呢？明顯傳進去是傳進去樹的樹根，這邊這個0是怎麼回事呢？我們先來看隨便一棵樹的例子，

整個這棵樹我要計算最優編碼的總長度的話，也就是說，我需要去訪問它一個一個的葉子結點，當我訪問到它的某一個葉子結點的時候，我應該知道這個葉子結點所處的深度是多少，就是從根結點到葉子結點路徑的長度，得到深度以後呢，我就可以用深度乘以它的頻率，我就得到了這一條編碼的它的WPL,那麼我要做的整個的事情，就是把所有葉子結點WPL整個求和就對了，如果你習慣用遞歸的思想去考慮問題的話，很簡單的，一棵樹的總的WPL,就是它左子樹的WPL,加上它右子樹的WPL,我們需要的就是在遞歸調用左邊，遞歸調用右邊的時候，把一個正確的深度傳進去，所謂深度就是我傳進去的每一棵子樹的根結點它當前的深度是多少，那麼我們是從整棵樹的根結點開始的，當前這個根的深度是0，所以我從0開始，這就解釋了WPL(T,0),

那麼接下來的事情就很簡單，實際上是一個遞歸的先序遍歷的過程，我們傳進來一個哈夫曼樹的根結點，以及這個根結點T當前的深度，如果T沒有左孩子，並且沒有右孩子，就意味著如果當前這個T結點是一個葉子結點的話，那麼我們就開始計算了，就是用它當前的深度乘以它的權重，然後返回這個結果，如果它不是根節點的話，如果我們在這生成的哈夫曼樹(HuffmanTree T = Huffman(H))是正確的話，那麼它一定有兩個孩子(度為2，特性),於是我們就去遞歸的解決左邊的問題，然後加上遞歸的解決它右邊的問題，然後返回兩邊的和就對了。

那麼在遞歸解決左右問題的時候，注意到結點的深度，是要加1的。