哈夫曼樹
哈夫曼樹也叫最優二叉樹（哈夫曼樹）
問題：什麼是哈夫曼樹？
例：将學生的百分制成績轉換為五分制成績：≥90 分: a，80～89分: b，70～79分: c，60～69分: d，＜60分: e。
判别樹：用于描述分類過程的二叉樹。
如果每次輸入量都很大，那麼應該考慮程式運作的時間
如果學生的總成績資料有10000條，則5％的資料需 1 次比較，15％的資料需 2 次比較，40％的資料需 3 次比較，40％的資料需 4 次比較，是以 10000 個資料比較的
次數為： 10000 (5％＋2×15％＋3×40％＋4×40％)＝31500次
此種形狀的二叉樹，需要的比較次數是：10000 (3×20％＋2×80％)＝22000次，顯然：兩種判别樹的效率是不一樣的。
問題：能不能找到一種效率最高的判别樹呢?
那就是哈夫曼樹
回憶樹的基本概念和術語
路徑：若樹中存在一個結點序列k1,k2,…,kj，使得ki是ki+1的雙親，則稱該結點序列是從k1到kj的一條路徑。
路徑長度：等于路徑上的結點數減1。
結點的權：在許多應用中，常常将樹中的結點賦予一個有意義的數，稱為該結點的權。
結點的帶權路徑長度：是指該結點到樹根之間的路徑長度與該結點上權的乘積。
樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，通常記作：
其中，n表示葉子結點的數目，wi和li分别表示葉子結點ki的權值和樹根結點到葉子結點ki之間的路徑長度。
赫夫曼樹（哈夫曼樹，huffman樹）定義：
在權為w1,w2,…,wn的n個葉子結點的所有二叉樹中，帶權路徑長度wpl最小的二叉樹稱為赫夫曼樹或最優二叉樹。
例：有4 個結點 a, b, c, d，權值分别為 7, 5, 2, 4，試構造以此 4 個結點為葉子結點的二叉樹。
wpl=7´2+5´2+2´2+4´2= 36
wpl=7´3+5´3+2´1+4´2= 46
wpl=7´1+5´2+2´3+4´3= 35
後兩者其實就是最有二叉樹（也就是哈夫曼樹）
哈夫曼樹的構造(哈夫曼算法)
1.根據給定的n個權值{w1,w2,…,wn}構成二叉樹集合f={t1,t2,…,tn},其中每棵二叉樹ti中隻有一個帶權為wi的根結點,其左右子樹為空.
2.在f中選取兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹,且置新的二叉樹的根結點的權值為左右子樹根結點的權值之和.
3.在f中删除這兩棵樹,同時将新的二叉樹加入f中.
4.重複2、3,直到f隻含有一棵樹為止.(得到哈夫曼樹)
例：有4 個結點 a, b, c, d，權值分别為 7, 5, 2, 4，構造哈夫曼樹。
根據給定的n個權值{w1,w2,…,wn}構成二叉樹集合f={t1,t2,…,tn},其中每棵二叉樹ti中隻有一個帶權為wi的根結點,其左右子樹為空.
在f中選取兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹,且置新的二叉樹的根結點的權值為左右子樹根結點的權值之和.
在f中删除這兩棵樹,同時将新的二叉樹加入f中.
重複,直到f隻含有一棵樹為止.(得到哈夫曼樹)
關于哈夫曼樹的注意點：
1、滿二叉樹不一定是哈夫曼樹
2、哈夫曼樹中權越大的葉子離根越近 （很好了解，wpl最小的二叉樹）
3、具有相同帶權結點的哈夫曼樹不惟一
4、哈夫曼樹的結點的度數為 0 或 2， 沒有度為 1 的結點。
5、包含 n 個葉子結點的哈夫曼樹中共有 2n – 1 個結點。
6、包含 n 棵樹的森林要經過 n–1 次合并才能形成哈夫曼樹，共産生 n–1 個新結點
再看一個例子：如權值集合w={7,19,2,6,32,3,21,10 }構造赫夫曼樹的過程。
在f中選取兩棵根結點權值最小的樹
作為左右子樹構造一棵新的二叉樹，置新的二叉樹的根結點的權值為左右子樹根結點的權值之和
構造完畢（哈夫曼樹，最有二叉樹），也就是最佳判定樹
哈夫曼編碼
哈夫曼樹的應用很廣，哈夫曼編碼就是其在電訊通信中的應用之一。廣泛地用于資料檔案壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。在電訊通信業務中，通常用二進制編碼來表示字母或其他字元，并用這樣的編碼來表示字元序列。
例：如果需傳送的電文為 ‘abaccda’，它隻用到四種字元，用兩位二進制編碼便可分辨。假設 a, b, c, d 的編碼分别為 00, 01,10, 11，則上述電文便為 ‘00010010101100’（共 14 位），譯碼員按兩位進行分組譯碼，便可恢複原來的電文。
能否使編碼總長度更短呢？
實際應用中各字元的出現頻度不相同，用短（長）編碼表示頻率大（小）的字元，使得編碼序列的總長度最小，使所需總空間量最少
資料的最小備援編碼問題
在上例中，若假設 a, b, c, d 的編碼分别為 0，00，1，01，則電文 ‘abaccda’ 便為 ‘000011010’（共 9 位），但此編碼存在多義性：可譯為： ‘bbccda’、‘abaccda’、‘aaaaccaca’ 等。
譯碼的惟一性問題
要求任一字元的編碼都不能是另一字元編碼的字首，這種編碼稱為字首編碼（其實是非字首碼）。 在編碼過程要考慮兩個問題，資料的最小備援編碼問題，譯碼的惟一性問題，利用最優二叉樹可以很好地解決上述兩個問題
用二叉樹設計二進制字首編碼
以電文中的字元作為葉子結點構造二叉樹。然後将二叉樹中結點引向其左孩子的分支标 ‘0’，引向其右孩子的分支标 ‘1’； 每個字元的編碼即為從根到每個葉子的路徑上得到的 0, 1 序列。如此得到的即為二進制字首編碼。
編碼： a：0， c：10，b：110，d：111
任意一個葉子結點都不可能在其它葉子結點的路徑中。
用哈夫曼樹設計總長最短的二進制字首編碼
假設各個字元在電文中出現的次數（或頻率）為 wi ，其編碼長度為 li，電文中隻有 n 種字元，則電文編碼總長為：
設計電文總長最短的編碼，設計哈夫曼樹（以 n 種字元出現的頻率作權），
由哈夫曼樹得到的二進制字首編碼稱為哈夫曼編碼
例：如果需傳送的電文為 ‘abaccda’，即：a, b, c, d
的頻率（即權值）分别為 0.43, 0.14, 0.29, 0.14，試構造哈夫曼編碼。
編碼： a：0， c：10， b：110， d：111 。電文 ‘abaccda’ 便為 ‘0110010101110’（共 13 位）。
例：如果需傳送的電文為 ‘abcaccdaeae’，即：a, b, c, d, e 的頻率（即權值）分别為0.36, 0.1, 0.27, 0.1, 0.18，試構造哈夫曼編碼。
編碼： a：11，c：10，e：00，b：010，d：011 ，則電文 ‘abcaccdaeae’ 便為 ‘110101011101001111001100’（共 24 位，比 33 位短）。
譯碼
從哈夫曼樹根開始，對待譯碼電文逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達葉子結點，則譯出一個字元；再重新從根出發，直到電文結束。
電文為 “1101000” ，譯文隻能是“cat”
哈夫曼編碼算法的實作
由于哈夫曼樹中沒有度為1的結點，則一棵有n個葉子的哈夫曼樹共有2×n-1個結點，可以用一個大小為2×n-1 的一維數組存放哈夫曼樹的各個結點。 由于每個結點同時還包含其雙親資訊和孩子結點的資訊，是以構成一個靜态三叉連結清單。
補充：樹的計數
已知先序序列和中序序列可确定一棵唯一的二叉樹；
已知後序序列和中序序列可确定一棵唯一的二叉樹；
已知先序序列和後序序列不能确定一棵唯一的二叉樹。
辛苦的勞動，轉載請注明出處，謝謝……http://www.cnblogs.com/kubixuesheng/p/4397798.html