但是有没有自己亲手写过，这个我就不清楚了，不管以前写没写，这一篇我们来玩一把。
一：概念
赫夫曼树里面有几个概念，也是非常简单的，先来看下面的图：
1. 基础概念
节点的权： 节点中红色部分就是权，在实际应用中，我们用“字符”出现的次数作为权。
路径长度：可以理解成该节点到根节点的层数，比如：“A”到根节点的路径长度为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 ///
3 /// 赫夫曼节点
4 ///
5 public class Node
6 {
7 ///
8 /// 左孩子
9 ///
10 public Node left;
11
12 ///
13 /// 右孩子
14 ///
15 public Node right;
16
17 ///
18 /// 父节点
19 ///
20 public Node parent;
21
22 ///
23 /// 节点字符
24 ///
25 public char c;
26
27 ///
28 /// 节点权重
29 ///
30 public int weight;
31
32 //赫夫曼“0"or“1"
33 public char huffmancode;
34
35 ///
36 /// 标记是否为叶子节点
37 ///
38 public bool isLeaf;
39 }
40 #endregion
1. 构建赫夫曼树（Build）
上面也说了，构建赫夫曼编码树我们采用小根堆的形式构建，构建完后，我们采用DFS的方式统计各个字符的编码，复杂度为N*logN。
关于小根堆（详细内容可以参考我的系列文章 “优先队列”）
1 #region 构建赫夫曼树
2 ///
3 /// 构建赫夫曼树
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 #endregion2：编码(Encode,Decode)
树构建起来后，我会用字典来保存字符和”赫夫曼编码“的对应表，然后拿着明文或者密文对着编码表翻译就行了， 复杂度O(N)。
1 #region 赫夫曼编码
2 ///
3 /// 赫夫曼编码
4 ///
5 ///
21 /// 赫夫曼解码
22 ///
23 /// 最后我们做个例子，压缩9M的文件，看看到底能压缩多少？
1 public static void Main()
2 {
3 StringBuilder sb = new StringBuilder();
4
5 for (int i = 0; i list = new List();
28
29 var start = 0;
30
31 for (int i = 8; i 
看看，多帅气，将9M的文件压缩到了4M，同时我也打开了压缩后的秘文，相信这些东西是什么，你懂我懂的。
主程序：
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 Program
12 {
13 public static void Main()
14 {
15 StringBuilder sb = new StringBuilder();
16
17 for (int i = 0; i list = new List();
40
41 var start = 0;
42
43 for (int i = 8; i
87 /// 赫夫曼节点
88 ///
89 public class Node
90 {
91 ///
92 /// 左孩子
93 ///
94 public Node left;
95
96 ///
97 /// 右孩子
98 ///
99 public Node right;
100
101 ///
102 /// 父节点
103 ///
104 public Node parent;
105
106 ///
107 /// 节点字符
108 ///
109 public char c;
110
111 ///
112 /// 节点权重
113 ///
114 public int weight;
115
116 //赫夫曼“0"or“1"
117 public char huffmancode;
118
119 ///
120 /// 标记是否为叶子节点
121 ///
122 public bool isLeaf;
123 }
124 #endregion
125
126 PriorityQueue queue = new PriorityQueue();
127
128 ///
129 /// 编码对应表（加速用）
130 ///
131 Dictionary huffmanEncode = new Dictionary();
132
133 ///
134 /// 解码对应表（加速用）
135 ///
136 Dictionary huffmanDecode = new Dictionary();
137
138 ///
139 /// 明文
140 ///
141 string word = string.Empty;
142
143 public Node root = new Node();
144
145 public Huffman(string str)
146 {
147 this.word = str;
148
149 Dictionary dic = new Dictionary();
150
151 foreach (var s in str)
152 {
153 if (dic.ContainsKey(s))
154 dic[s] += 1;
155 else
156 dic[s] = 1;
157 }
158
159 foreach (var item in dic.Keys)
160 {
161 var node = new Node()
162 {
163 c = item,
164 weight = dic[item]
165 };
166
167 //入队
168 queue.Eequeue(node, dic[item]);
169 }
170 }
171
172 #region 构建赫夫曼树
173 ///
174 /// 构建赫夫曼树
175 ///
176 public void Build()
177 {
178 //构建
179 while (queue.Count() > 0)
180 {
181 //如果只有一个节点，则说明已经到根节点了
182 if (queue.Count() == 1)
183 {
184 root = queue.Dequeue().t;
185
186 break;
187 }
188
189 //节点1
190 var node1 = queue.Dequeue();
191
192 //节点2
193 var node2 = queue.Dequeue();
194
195 //标记左孩子
196 node1.t.huffmancode = '0';
197
198 //标记为右孩子
199 node2.t.huffmancode = '1';
200
201 //判断当前节点是否为叶子节点,hufuman无度为1点节点（方便计算huffman编码）
202 if (node1.t.left == null)
203 node1.t.isLeaf = true;
204
205 if (node2.t.left == null)
206 node2.t.isLeaf = true;
207
208 //父节点
209 root = new Node();
210
211 root.left = node1.t;
212
213 root.right = node2.t;
214
215 root.weight = node1.t.weight + node2.t.weight;
216
217 //当前节点为根节点
218 node1.t.parent = node2.t.parent = root;
219
220 //将当前节点的父节点入队列
221 queue.Eequeue(root, root.weight);
222 }
223
224 //深度优先统计各个字符的编码
225 DFS(root);
226 }
227 #endregion
228
229 #region 赫夫曼编码
230 ///
231 /// 赫夫曼编码
232 ///
233 ///
249 /// 赫夫曼解码
250 ///
251 ///
小根堆：
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 where T : class
12 {
13 ///
14 /// 定义一个数组来存放节点
15 ///
16 private List nodeList = new List();
17
18 #region 堆节点定义
19 ///
20 /// 堆节点定义
21 ///
22 public class HeapNode
23 {
24 ///
25 /// 实体数据
26 ///
27 public T t { get; set; }
28
29 ///
30 /// 优先级别 1-10个级别 (优先级别递增)
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 ///
46 /// 添加操作
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 ///
67 /// 对堆进行上滤操作，使得满足堆性质
68 ///
69 ///
70 /// 非叶子节点的之后指针（这里要注意：我们
71 /// 的筛操作时针对非叶节点的）
72 ///
73 public void UpHeapAdjust(List nodeList, int parent)
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[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 ///
115 /// 优先队列的出队操作
116 ///
117 ///
141 /// 对堆进行下滤操作，使得满足堆性质
142 ///
143 ///
144 /// 非叶子节点的之后指针（这里要注意：我们
145 /// 的筛操作时针对非叶节点的）
146 ///
147 public void DownHeapAdjust(List nodeList, int parent)
148 {
149 while (2 * parent + 1 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 ///
189 /// 获取元素并下降到指定的level级别
190 ///
191 ///
212 /// 获取元素并下降优先级
213 ///
214 ///
224 /// 返回当前优先队列中的元素个数
225 ///
226 ///
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
