轉(zhuǎn)自：http://blog.csdn.net/hikvision_java_gyh/article/details/8952596
哈夫曼樹(shù)又稱最優(yōu)二叉樹(shù)掰派，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)剂习。所謂樹(shù)的帶權(quán)路徑長(zhǎng)度，就是樹(shù)中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層拆祈，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹(shù)的帶權(quán)路徑長(zhǎng)度記為WPL=(W1L1+W2L2+W3L3+...+ WnLn)长赞，N個(gè)權(quán)值Wi(i=1,2,...n)構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹(shù)声怔，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i(i=1,2,...n)回懦。可以證明哈夫曼樹(shù)的WPL是最小的曾我》叟拢【例】給定4個(gè)葉子結(jié)點(diǎn)a，b抒巢，c和d贫贝，分別帶權(quán)7，5蛉谜，2和4稚晚。構(gòu)造如下圖所示的三棵二叉樹(shù)(還有許多棵)，它們的帶權(quán)路徑長(zhǎng)度分別為: (a)WPL=72+52+22+42=36 (b)WPL=73+53+21+42=46 (c)WPL=71+52+23+43=35其中(c)樹(shù)的WPL最小型诚，可以驗(yàn)證客燕，它就是哈夫曼樹(shù)。

構(gòu)造哈夫曼樹(shù)的算法如下： 1）對(duì)給定的n個(gè)權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹(shù)的初始集合F={T1,T2,T3,...,Ti,..., Tn}狰贯，其中每棵二叉樹(shù)Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)也搓，它的左右子樹(shù)均為空。 2）在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為新構(gòu)造的二叉樹(shù)的左右子樹(shù)涵紊，新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)的根結(jié)點(diǎn)的權(quán)值之和傍妒。 3）從F中刪除這兩棵樹(shù)，并把這棵新的二叉樹(shù)同樣以升序排列加入到集合F中摸柄。 4）重復(fù)2）和3）颤练，直到集合F中只有一棵二叉樹(shù)為止。 例如驱负，對(duì)于4個(gè)權(quán)值為1嗦玖、3、5跃脊、7的節(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)宇挫，其構(gòu)造過(guò)程如下圖所示：

可以計(jì)算得到該哈夫曼樹(shù)的路徑長(zhǎng)度WPL＝(1+3)3+25+1*7=26。
哈夫曼編碼應(yīng)用 大數(shù)據(jù)量的圖像信息會(huì)給存儲(chǔ)器的存儲(chǔ)容量酪术，通信干線信道的帶寬捞稿，以及計(jì)算機(jī)的處理速度增加極大的壓力。單純靠增加存儲(chǔ)器容量拼缝，提高信道帶寬以及計(jì)算機(jī)的處理速度等方法來(lái)解決這個(gè)問(wèn)題是不現(xiàn)實(shí)的娱局，這時(shí)就要考慮壓縮。壓縮的關(guān)鍵在于編碼咧七，如果在對(duì)數(shù)據(jù)進(jìn)行編碼時(shí)衰齐，對(duì)于常見(jiàn)的數(shù)據(jù)，編碼器輸出較短的碼字继阻；而對(duì)于少見(jiàn)的數(shù)據(jù)則用較長(zhǎng)的碼字表示耻涛，就能夠?qū)崿F(xiàn)壓縮废酷。【例】：假設(shè)一個(gè)文件中出現(xiàn)了8種符號(hào)S0抹缕，SQ澈蟆，S2，S3卓研，S4趴俘，S5，S6奏赘，S7寥闪，那么每種符號(hào)要編碼，至少需要3bit磨淌。假設(shè)編碼成 000疲憋，001， 010梁只，011缚柳，100，101搪锣，110喂击，111。那么符號(hào)序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成 000001111000001110010010011100101000000001淤翔，共用了42bit。我們發(fā)現(xiàn)S0佩谷，S1旁壮，S2這3個(gè)符號(hào)出現(xiàn)的頻率比較大，其它符號(hào)出現(xiàn)的頻率比較小谐檀，我們采用這樣的編碼方案：S0到S7的碼遼分別01抡谐，11，101桐猬，0000麦撵，0001，0010溃肪，0011免胃， 100，那么上述符號(hào)序列變成011110001110011101101000000010010010111惫撰，共用了39bit羔沙。盡管有些碼字如 S3，S4厨钻，S5扼雏，S6變長(zhǎng)了(由3位變成4位)坚嗜，但使用頻繁的幾個(gè)碼字如S0，S1變短了诗充，所以實(shí)現(xiàn)了壓縮苍蔬。對(duì)于上述的編碼可能導(dǎo)致解碼出現(xiàn)非單值性：比如說(shuō)，如果S0的碼字為01蝴蜓，S2的碼字為011碟绑，那么當(dāng)序列中出現(xiàn)011時(shí)，你不知道是S0的碼字后面跟了個(gè)1励翼，還是完整的一個(gè)S2的碼字蜈敢。因此，編碼必須保證較短的編碼決不能是較長(zhǎng)編碼的前綴汽抚。符合這種要求的編碼稱之為前綴編碼抓狭。要構(gòu)造符合這樣的二進(jìn)制編碼體系，可以通過(guò)二叉樹(shù)來(lái)實(shí)現(xiàn)造烁。以下是哈夫曼樹(shù)的Java實(shí)現(xiàn)：
[java] view plain copy

// 二叉樹(shù)節(jié)點(diǎn)
public class Node implements Comparable { private int value; private Node leftChild; private Node rightChild; public Node(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } public int compareTo(Object o) { Node that = (Node) o; double result = this.value - that.value; return result > 0 ? 1 : result == 0 ? 0 : -1; } }

• 哈夫曼樹(shù)構(gòu)造類(lèi)：
  public class HuffmanTreeBuilder { public static void main(String[] args) { List<Node> nodes = Arrays.asList( new Node(1), new Node(3), new Node(5), new Node(7) ); Node node = HuffmanTreeBuilder.build(nodes); PrintTree(node); }
  /**
• 構(gòu)造哈夫曼樹(shù)
• @param nodes 結(jié)點(diǎn)集合
• @return 構(gòu)造出來(lái)的樹(shù)的根結(jié)點(diǎn)
  */

private static Node build(List<Node> nodes) {
nodes = new ArrayList<Node>(nodes);
sortList(nodes);
while (nodes.size() > 1) {
createAndReplace(nodes);
}
return nodes.get(0);
}

/**

• 組合兩個(gè)權(quán)值最小結(jié)點(diǎn)否过，并在結(jié)點(diǎn)列表中用它們的父結(jié)點(diǎn)替換它們
• @param nodes 結(jié)點(diǎn)集合
  */
  private static void createAndReplace(List<Node> nodes) {
  Node left = nodes.get(0);
  Node right = nodes.get(1);
  Node parent = new Node(left.getValue() + right.getValue());
  parent.setLeftChild(left);
  parent.setRightChild(right);
  nodes.remove(0);
  nodes.remove(0);
  nodes.add(parent);
  sortList(nodes);
  }

/**

• 將結(jié)點(diǎn)集合由大到小排序
  */

private static void sortList(List<Node> nodes) {
Collections.sort(nodes);
}

`
/**

• 打印樹(shù)結(jié)構(gòu)，顯示的格式是node(left,right)
• @param node
  */
  public static void PrintTree(Node node)
  {
  Node left = null;
  Node right = null;
  if(node!=null)
  {
  System.out.print(node.getValue());
  left = node.getLeftChild();
  right = node.getRightChild();
  System.out.println("("+(left!=null?left.getValue():" ") +","+ (right!= null?right.getValue():" ")+")");
  }
  if(left!=null)
  PrintTree(left);
  if(right!=null)
  PrintTree(right);
  }
  }
  `