代码语言：javascript复制
//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表示是父树的左/右孩子。
}
