赫夫曼樹又稱最優二叉樹，也就是帶權路徑最短的樹，對於赫夫曼樹，我想大家對它是非常的熟悉，也知道它的應用場景，
但是有沒有自己親手寫過，這個我就不清楚了，不管以前寫沒寫，這一篇我們來玩一把。
一：概念
赫夫曼樹裏面有幾個概念，也是非常簡單的，先來看下面的圖：
1. 基礎概念
<1> 節點的權： 節點中紅色部分就是權，在實際應用中，我們用 “字元” 出現的次數作為權。
<2> 路徑長度：可以理解成該節點到根節點的層數，比如：“A” 到根節點的路徑長度為 3 。
<3> 樹的路徑長度：各個葉子節點到根節點的路徑長度總和，用 WPL 標記。
最後我們要討論的的赫夫曼樹也就是帶權路徑長度最小的一棵樹。
2. 構建
由於要使 WPL 最短，赫夫曼樹的構建採用自低向上的方式，這裏我們採用小根堆來存放當前需要構建的各個節點，我們的方
式是每次從小根堆中取出最小的兩個節點，合併後放入堆中，然後繼續取兩個最小的節點，一直到小根堆為空，最後我們採用
自底向上構建的赫夫曼樹也就完畢了。
好了，赫夫曼樹的典型應用就是在資料壓縮方面，下面我們就要在赫夫曼樹上面放入赫夫曼編碼了，我們知道普通的 ASCII 碼是
採用等長編碼的，即每個字元都採用 2 個位元組，而赫夫曼編碼的思想就是採用不等長的思路，權重高的字元靠近根節點，權重低
的字元遠離根節點，標記方式為左孩子 “0”，右孩子 “1”，如下圖。
從圖中我們可以看到各個字元的赫夫曼編碼了，獲取字元的編碼採用從根往下的方式收集路徑上的 ‘0,1’，如：
A:110 。
B:111 。
C:0 。
D:10 。
最後我們來比較他們的 WPL 的長度： ASCII 碼=10*2+20*2+40*2+80*2=300
赫夫曼碼=10*3+20*3+40*2+80*1=250
可以看到，赫夫曼碼壓縮了 50 個 0,1 字元，太牛逼了，是不是啊。。。
三：程式碼
1. 樹節點
我們採用 7 元節點，其中 parent 方便我們在 DFS 的時候找到從葉子節點到根節點的路徑上的赫夫曼編碼。
1 #region 赫夫曼節點
2 ///
4 ///
5 public class Node
6 {
7 ///
9 ///
10 public Node left;
11
12 ///
14 ///
15 public Node right;
16
17 ///
19 ///
20 public Node parent;
21
22 ///
24 ///
25 public char c;
26
27 ///
29 ///
30 public int weight;
31
32 //赫夫曼 “0″or“1″
33 public char huffmancode;
34
35 ///
37 ///
38 public bool isLeaf;
39 }
40 #endregion
1. 構建赫夫曼樹（Build）
上面也説了，構建赫夫曼編碼樹我們採用小根堆的形式構建，構建完後，我們採用 DFS 的方式統計各個字元的編碼，複雜度為 N*logN 。
關於小根堆（詳細內容可以參考我的系列文章 “優先佇列 “）
1 #region 構建赫夫曼樹
2 ///
4 ///
5 public void Build()
6 {
7 //構建
8 while (queue.Count() > 0)
9 {
10 //如果只有一個節點，則説明已經到根節點了
11 if (queue.Count() == 1)
12 {
13 root = queue.Dequeue().t;
14
15 break;
16 }
17
18 //節點 1
19 var node1 = queue.Dequeue();
20
21 //節點 2
22 var node2 = queue.Dequeue();
23
24 //標記左孩子
25 node1.t.huffmancode = ‘0’;
26
27 //標記為右孩子
28 node2.t.huffmancode = ‘1’;
29
30 //判斷當前節點是否為葉子節點,hufuman 無度為 1 點節點（方便計算 huffman 編碼）
31 if (node1.t.left == null)
32 node1.t.isLeaf = true;
33
34 if (node2.t.left == null)
35 node2.t.isLeaf = true;
36
37 //父節點
38 root = new Node();
39
40 root.left = node1.t;
41
42 root.right = node2.t;
43
44 root.weight = node1.t.weight + node2.t.weight;
45
46 //當前節點為根節點
47 node1.t.parent = node2.t.parent = root;
48
49 //將當前節點的父節點入佇列
50 queue.Eequeue(root, root.weight);
51 }
52
53 //深度優先統計各個字元的編碼
54 DFS(root);
55 }
56 #endregion
2：編碼 (Encode,Decode)
樹構建起來後，我會用字典來儲存字元和” 赫夫曼編碼 “的對應表，然後拿著明文或者密文對著編碼表翻譯就行了， 複雜度 O(N) 。
1 #region 赫夫曼編碼
2 ///
4 ///
5 ///
6 public string Encode()
7 {
8 StringBuilder sb = new StringBuilder();
9
10 foreach (var item in word)
11 {
12 sb.Append(huffmanEncode[item]);
13 }
14
15 return sb.ToString();
16 }
17 #endregion
18
19 #region 赫夫曼解碼
20 ///
22 ///
23 ///
24 public string Decode(string str)
25 {
26 StringBuilder decode = new StringBuilder();
27
28 string temp = string.Empty;
29
30 for (int i = 0; i < str.Length; i++)
31 {
32 temp += str[i].ToString();
33
34 //如果包含 O(N) 時間
35 if (huffmanDecode.ContainsKey(temp))
36 {
37 decode.Append(huffmanDecode[temp]);
38
39 temp = string.Empty;
40 }
41 }
42
43 return decode.ToString();
44 }
45 #endregion
最後我們做個例子，壓縮 9M 的檔案，看看到底能壓縮多少？
1 public static void Main()
2 {
3 StringBuilder sb = new StringBuilder();
4
5 for (int i = 0; i < 1 * 10000; i++)
6 {
7 sb.Append("人民網北京 12 月 8 日電（記者 宋心蕊）北京時間 8 日晚的央視《新聞聯播》節目出現了直播失誤。上一條新聞尚未播放完畢時，播就將畫面切換回了演播間，主播李梓萌開始播報下一條新聞，導致兩條新聞出現了 “混音” 播出。央視新聞官方微博賬號在 21 點 09 分發布了一條致歉微博：【致歉】今晚《新聞聯播》因導播員口令失誤，導致畫面切換錯誤，特此向觀眾朋友表示歉意。央視特約評論員楊禹在個人微博中寫道：今晚《新聞聯播》出了個切換錯誤，@央視新聞 及時做了誠懇道歉。聯播一直奉行 “金標準”，壓力源自全社會的高要求。其實報紙亦都有 “勘誤” 一欄，坦誠糾錯與道歉。《新聞聯播》是中國影響力最大的電視新聞節目。它有不可替代的符號感，它有失誤，更有悄然的進步。新的改進正在或即將發生，不妨期待");
8 }
9
10 File.WriteAllText(Environment.CurrentDirectory + "//1.txt", sb.ToString());
11
12 Huffman huffman = new Huffman(sb.ToString());
13
14 Stopwatch watch = Stopwatch.StartNew();
15
16 huffman.Build();
17
18 watch.Stop();
19
20 Console.WriteLine("構建赫夫曼樹耗費:{0}", watch.ElapsedMilliseconds);
21
22 //將 8 位二進位制轉化為 ascII 碼
23 var s = huffman.Encode();
24
25 var remain = s.Length % 8;
26
27 List
28
29 var start = 0;
30
31 for (int i = 8; i < s.Length; i = i + 8)
32 {
33 list.Add((char)Convert.ToInt32(s.Substring(i - 8, 8), 2));
34
35 start = i;
36 }
37
38 var result = new String(list.ToArray());
39
40 //當字元編碼不足 8 位時， 用 ‘艹'來標記，然後拿出’ 擦 ‘以後的所有 0,1 即可
41 result += "艹" + s.Substring(start);
42
43 File.WriteAllText(Environment.CurrentDirectory + "//2.txt", result);
44
45 Console.WriteLine("壓縮完畢！");
46
47 Console.Read();
48
49 //解碼
50 var str = File.ReadAllText(Environment.CurrentDirectory + "//2.txt");
51
52 sb.Clear();
53
54 for (int i = 0; i < str.Length; i++)
55 {
56 int ua = (int)str[i];
57
58 //説明已經取完畢了 用'艹'來做標記
59 if (ua == 33401)
60 sb.Append(str.Substring(i));
61 else
62 sb.Append(Convert.ToString(ua, 2).PadLeft(8, '0'));
63 }
64
65 var sss = huffman.Decode(sb.ToString());
66
67 Console.Read();
68 }
看看，多帥氣，將 9M 的檔案壓縮到了 4M，同時我也開啓了壓縮後的秘文，相信這些東西是什麼，你懂我懂的。
主程式：
View Code
小根堆：
View Code
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Diagnostics;
6 using System.Threading;
7 using System.IO;
8
9 namespace ConsoleApplication2
10 {
11 public class PriorityQueue
12 {
13 ///
15 ///
16 private List
17
18 #region 堆節點定義
19 ///
21 ///
22 public class HeapNode
23 {
24 ///
26 ///
27 public T t { get; set; }
28
29 ///
31 ///
32 public int level { get; set; }
33
34 public HeapNode(T t, int level)
35 {
36 this.t = t;
37 this.level = level;
38 }
39
40 public HeapNode() { }
41 }
42 #endregion
43
44 #region 新增操作
45 ///
47 ///
48 public void Eequeue(T t, int level = 1)
49 {
50 //將當前節點追加到堆尾
51 nodeList.Add(new HeapNode(t, level));
52
53 //如果只有一個節點，則不需要進行篩操作
54 if (nodeList.Count == 1)
55 return;
56
57 //獲取最後一個非葉子節點
58 int parent = nodeList.Count / 2 – 1;
59
60 //堆調整
61 UpHeapAdjust(nodeList, parent);
62 }
63 #endregion
64
65 #region 對堆進行上濾操作，使得滿足堆性質
66 ///
68 ///
69 ///
70 /// 非葉子節點的之後指標（這裏要注意：我們
71 /// 的篩操作時針對非葉節點的）
72 ///
73 public void UpHeapAdjust(List
74 {
75 while (parent >= 0)
76 {
77 //當前 index 節點的左孩子
78 var left = 2 * parent + 1;
79
80 //當前 index 節點的右孩子
81 var right = left + 1;
82
83 //parent 子節點中最大的孩子節點，方便於 parent 進行比較
84 //預設為 left 節點
85 var min = left;
86
87 //判斷當前節點是否有右孩子
88 if (right < nodeList.Count)
89 {
90 //判斷 parent 要比較的最大子節點
91 min = nodeList[left].level < nodeList[right].level ? left : right;
92 }
93
94 //如果parent節點大於它的某個子節點的話，此時篩操作
95 if (nodeList[parent].level > nodeList[min].level)
96 {
97 //子節點和父節點進行交換操作
98 var temp = nodeList[parent];
99 nodeList[parent] = nodeList[min];
100 nodeList[min] = temp;
101
102 //繼續進行更上一層的過濾
103 parent = (int)Math.Ceiling(parent / 2d) – 1;
104 }
105 else
106 {
107 break;
108 }
109 }
110 }
111 #endregion
112
113 #region 優先佇列的出隊操作
114 ///
116 ///
117 ///
118 public HeapNode Dequeue()
119 {
120 if (nodeList.Count == 0)
121 return null;
122
123 //出佇列操作，彈出資料頭元素
124 var pop = nodeList[0];
125
126 //用尾元素填充頭元素
127 nodeList[0] = nodeList[nodeList.Count – 1];
128
129 //刪除尾節點
130 nodeList.RemoveAt(nodeList.Count – 1);
131
132 //然後從根節點下濾堆
133 DownHeapAdjust(nodeList, 0);
134
135 return pop;
136 }
137 #endregion
138
139 #region 對堆進行下濾操作，使得滿足堆性質
140 ///
142 ///
143 ///
144 /// 非葉子節點的之後指標（這裏要注意：我們
145 /// 的篩操作時針對非葉節點的）
146 ///
147 public void DownHeapAdjust(List
148 {
149 while (2 * parent + 1 < nodeList.Count)
150 {
151 //當前 index 節點的左孩子
152 var left = 2 * parent + 1;
153
154 //當前 index 節點的右孩子
155 var right = left + 1;
156
157 //parent 子節點中最大的孩子節點，方便於 parent 進行比較
158 //預設為 left 節點
159 var min = left;
160
161 //判斷當前節點是否有右孩子
162 if (right < nodeList.Count)
163 {
164 //判斷 parent 要比較的最大子節點
165 min = nodeList[left].level < nodeList[right].level ? left : right;
166 }
167
168 //如果parent節點小於它的某個子節點的話，此時篩操作
169 if (nodeList[parent].level > nodeList[min].level)
170 {
171 //子節點和父節點進行交換操作
172 var temp = nodeList[parent];
173 nodeList[parent] = nodeList[min];
174 nodeList[min] = temp;
175
176 //繼續進行更下一層的過濾
177 parent = min;
178 }
179 else
180 {
181 break;
182 }
183 }
184 }
185 #endregion
186
187 #region 獲取元素並下降到指定的 level 級別
188 ///
190 ///
191 ///
192 public HeapNode GetAndDownPriority(int level)
193 {
194 if (nodeList.Count == 0)
195 return null;
196
197 //獲取頭元素
198 var pop = nodeList[0];
199
200 //設定指定優先順序（如果為 MinValue 則為 — 操作）
201 nodeList[0].level = level == int.MinValue ? –nodeList[0].level : level;
202
203 //下濾堆
204 DownHeapAdjust(nodeList, 0);
205
206 return nodeList[0];
207 }
208 #endregion
209
210 #region 獲取元素並下降優先順序
211 ///
213 ///
214 ///
215 public HeapNode GetAndDownPriority()
216 {
217 //下降一個優先順序
218 return GetAndDownPriority(int.MinValue);
219 }
220 #endregion
221
222 #region 返回當前優先佇列中的元素個數
223 ///
225 ///
226 ///
227 public int Count()
228 {
229 return nodeList.Count;
230 }
231 #endregion
232 }
233 }
文章來自互聯網博客網站。原文地址 http://www.cnblogs.com/huangxincheng/archive/2012/12/09/2809993.html