哈夫曼樹

最優(yōu)二叉樹也稱哈夫曼樹，講的直白點就是每個結(jié)點都帶權(quán)值，我們讓大的值離根近、小的值離根遠，實現(xiàn)整體權(quán)值（帶權(quán)路徑長度）最小化。

哈夫曼算法的思想我認為就是上面講的，而它的算法實現(xiàn)思路是這樣的：
從根結(jié)點中抽出權(quán)值最小的兩個（涉及排序，但是我這個實現(xiàn)代碼沒做嚴格的排序，只有比較）合并出新的根結(jié)點重新加入排序（被抽出來的兩個自然是變成非根結(jié)點了啊），就這樣循環(huán)下去，直到合并完成，我們得到一顆最優(yōu)二叉樹——哈夫曼樹。

說明：

哈夫曼樹有n個葉子結(jié)點，則我們可以推出其有n-1個分支結(jié)點。因此我在定義名為huffmanTree的HuffmanNode類型數(shù)組時定義長度為2*n-1。

這里排序相關(guān)沒有做得很好，只是為了實現(xiàn)而實現(xiàn)，以后慢慢完善。

理論上講哈夫曼樹應(yīng)該是不僅僅局限于數(shù)值，能compare就行，但這里只用int表示。

定義哈夫曼樹結(jié)點

public class HuffmanNode {private int weight =

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】哈夫曼树的Java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。