數據結構之最優二叉樹

基本術語

　　路徑（Path）和路徑長度從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑路徑上的分支數目稱做路徑長度
　　樹的路徑長度從樹根到每一結點的路徑長度之和
　　樹的帶權路徑長度（Weighted Path Length of Tree）樹中所有葉結點的帶權路徑長度之和記作

　　Huffman樹又稱最優二叉樹它是n個帶樹葉子結點構成的所有二叉樹中帶權路徑長度WPL最小的二叉樹

構造Huffman樹

　　Huffman算法
　　() 根據給定的n個權值{ww…wn}構成n棵二叉樹的集合F={TT…Tn}其中每棵二叉樹Ti中只有一個帶權為wi的根結點其左右子樹均空
　　() 在F中選取兩棵根結點的權值最小的樹作為左右子樹構成一棵新的二叉樹且置新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和
　　() 在F中刪除這兩棵樹同時將新得到的二叉樹加入F中
　　() 重復()和()直到F只含一棵樹為止這棵樹便是
　　Huffman樹
　　Huffman樹的存儲結構

　　
　　實現Huffman算法

From:http://tw.wingwit.com/Article/program/sjjg/201311/22685.html