赫夫曼树又称最优二叉树，也就是带权路径最短的树，对于赫夫曼树，我想大家对它是非常的熟悉，也知道它的应用场景，
但是有没有自己亲手写过，这个我就不清楚了，不管以前写没写，这一篇我们来玩一把。
一：概念
赫夫曼树里面有几个概念，也是非常简单的，先来看下面的图：
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 //节点119 var node1 = queue.Dequeue();20 21 //节点222 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 ///3 /// 赫夫曼编码 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 #endregion18 19 #region 赫夫曼解码20 /// 21 /// 赫夫曼解码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
最后我们做个例子，压缩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 #endregion125 126 PriorityQueuequeue = new PriorityQueue ();127 128 /// 129 /// 编码对应表（加速用）130 /// 131 DictionaryhuffmanEncode = new Dictionary ();132 133 /// 134 /// 解码对应表（加速用）135 /// 136 DictionaryhuffmanDecode = 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 Dictionarydic = new Dictionary ();150 151 foreach (var s in str)152 {153 if (dic.ContainsKey(s))154 dic[s] += 1;155 else156 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 //节点1190 var node1 = queue.Dequeue();191 192 //节点2193 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 #endregion228 229 #region 赫夫曼编码230 ///231 /// 赫夫曼编码232 /// 233 ///234 public string Encode()235 {236 StringBuilder sb = new StringBuilder();237 238 foreach (var item in word)239 {240 sb.Append(huffmanEncode[item]);241 }242 243 return sb.ToString();244 }245 #endregion246 247 #region 赫夫曼解码248 /// 249 /// 赫夫曼解码250 /// 251 ///252 public string Decode(string str)253 {254 StringBuilder decode = new StringBuilder();255 256 string temp = string.Empty;257 258 for (int i = 0; i 277 /// 深度优先遍历子节点，统计各个节点的赫夫曼编码278 /// 279 /// 280 public void DFS(Node node)281 {282 if (node == null)283 return;284 285 //遍历左子树286 DFS(node.left);287 288 //遍历右子树289 DFS(node.right);290 291 //如果当前叶节点292 if (node.isLeaf)293 {294 string code = string.Empty;295 296 var temp = node;297 298 //回溯的找父亲节点的huffmancode LgN 的时间299 while (temp.parent != null)300 {301 //注意，这里最后形成的 “反过来的编码”302 code += temp.huffmancode;303 304 temp = temp.parent;305 }306 307 var codetemp = new String(code.Reverse().ToArray());308 309 huffmanEncode.Add(node.c, codetemp);310 311 huffmanDecode.Add(codetemp, node.c);312 }313 }314 #endregion315 }316 }
小根堆：
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 PriorityQueuewhere T : class 12 { 13 /// 14 /// 定义一个数组来存放节点 15 /// 16 private ListnodeList = 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(ListnodeList, 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 else106 {107 break;108 }109 }110 }111 #endregion112 113 #region 优先队列的出队操作114 /// 115 /// 优先队列的出队操作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 #endregion138 139 #region 对堆进行下滤操作，使得满足堆性质140 /// 141 /// 对堆进行下滤操作，使得满足堆性质142 /// 143 /// 144 /// 非叶子节点的之后指针（这里要注意：我们145 /// 的筛操作时针对非叶节点的）146 /// 147 public void DownHeapAdjust(ListnodeList, 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 else180 {181 break;182 }183 }184 }185 #endregion186 187 #region 获取元素并下降到指定的level级别188 /// 189 /// 获取元素并下降到指定的level级别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 #endregion209 210 #region 获取元素并下降优先级211 /// 212 /// 获取元素并下降优先级213 /// 214 ///215 public HeapNode GetAndDownPriority()216 {217 //下降一个优先级218 return GetAndDownPriority(int.MinValue);219 }220 #endregion221 222 #region 返回当前优先队列中的元素个数223 /// 224 /// 返回当前优先队列中的元素个数225 /// 226 ///227 public int Count()228 {229 return nodeList.Count;230 }231 #endregion232 }233 }
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/2815/viewspace-2811504/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
