hdu 1053 Entropy (哈夫曼樹)

（1）建立哈夫曼樹節點結構體

<a></a>

（2）首先我們把讀入的字元串進行預處理，按照字元分别放入對應的節點中，同時記錄其出現頻率，count_num記錄字元出現次數，同時放入哈夫曼節點中

（3）用一個優先權隊列存儲節點，每次取出頻率最小的兩個節點，合并節點并把其合并後的節點放入優先權隊列中，一直合并到隊列中隻剩下最後一個節點，把其作為根節點。（這正是哈夫曼樹建立的關鍵，這個地方一定要了解）

（4）哈夫曼樹建立完之後就是求其編碼長度的問題了，這時候就是周遊該樹的問題了，方法有很多，可以深度周遊，也可以廣度周遊。這裡采用廣度周遊，同時借助于一個queue進行的。

（5）剩下的就很簡單了，不做過多的贅述。

整個題的全部代碼

本文轉自NewPanderKing51CTO部落格，原文連結：http://www.cnblogs.com/newpanderking/archive/2012/11/14/2769367.html ，如需轉載請自行聯系原作者