C#笔记：哈夫曼树和编码 <pre class="brush:c#;toolbar:false">//QQ真坑爹，用它记笔记居然遗失了我的笔记。 class Program { static void Main(string[] args) { List<Node> lstNode = new List<Node>(); lstNode.Add(new Node() { val = "a", frequency = 2 }); lstNode.Add(new Node() { val = "b", frequency = 3 }); lstNode.Add(new Node() { val = "c", frequency = 7 }); lstNode.Add(new Node() { val = "d", frequency = 15 }); lstNode.Add(new Node() { val = "e", frequency = 4 }); lstNode.Add(new Node() { val = "f", frequency = 6 }); HuffmanTree ht = new HuffmanTree(); var tree = ht.BuildTree(lstNode); Console.WriteLine(ht.GetHuffmanCode("b", tree)); Console.WriteLine(ht.WPL(tree)); } } public class HuffmanTree { /// <summary> /// 返回一棵树中所有有值的节点。最后一个位置保存哈夫曼树（顶节点）。 /// </summary> /// <param name="list">传入的叶子</param> /// <returns>构造的树，包含所有有值的叶子和树（最后一个位置）</returns> public List<Node> BuildTree(List<Node> list) { List<Node> result = new List<Node>(); list.Sort(new NodeComparer());//首先排序 while (list.Count > 1) { //选取最小的两个节点 Node tempLeft = list[0]; Node tempRight = list[1]; Node union = new Node(); union.leftChild = tempLeft; union.rightChild = tempRight; union.frequency = tempLeft.frequency + tempRight.frequency; tempLeft.parent = union; tempLeft.ChildType = 0; tempRight.parent = union; tempRight.ChildType = 1; list.Remove(tempLeft); list.Remove(tempRight); InsertList(union, list); if (!string.IsNullOrEmpty(tempLeft.val)) { result.Add(tempLeft); } if (!string.IsNullOrEmpty(tempRight.val)) { result.Add(tempRight); } } result.Add(list[0]); return result; } //把新增的节点插入适当的位置。因为原来的数组是有序的。插入排序节省效率。 void InsertList(Node n, List<Node> list) { int posistion = list.Count; //从后往前扫描，因为新增的节点的值一般来说是比较大的。而数组已经有序。 while (true) { --posistion; if (posistion == -1)//这说明扫描完整个列表了。它自己是最小的节点，或者树中只有它一个节点。插入到头。 { break; } if (list[posistion].frequency < n.frequency)//插入适当的位置。 { break; } } list.Insert(posistion + 1, n); } public string GetHuffmanCode(string val, List<Node> list) { Node resultNode = null; string result = ""; foreach (var item in list) { if (item.val != null && item.val == val) { resultNode = item; break; } } Stack<int> stackPath = new Stack<int>(); if (resultNode != null) { while (resultNode.parent != null) { stackPath.Push(resultNode.ChildType); resultNode = resultNode.parent; } } while (stackPath.Count != 0) { result += stackPath.Pop(); } return result; } /// <summary> /// 返回带权路径 /// </summary> /// <param name="tree">生成的树</param> /// <returns>此树的带权路径</returns> public int WPL(List<Node> tree) { int result = 0; Node tempNode = null; foreach (var item in tree) { tempNode = item; int tempFrequency = item.frequency; if (item.val != null) { int temp = 0; while (tempNode.parent != null) { temp++; tempNode = tempNode.parent; } result += temp * tempFrequency; } } return result; } //这个是用来排序的辅助方法。用frequency排序。和list.sort()配合使用。 class NodeComparer : IComparer<Node> { public int Compare(Node x, Node y) { return x.frequency.CompareTo(y.frequency); } } } public class Node { public string val; public int frequency; public Node leftChild; public Node rightChild; public Node parent; public int ChildType;//用0和1表示是父树的左/右孩子。 }</pre><p><br/></p> 来自 大脸猫 写于 2015-02-16 22:02 -- 更新于2020-10-19 13:06 -- 0 条评论