C# 哈夫曼树

下面的例子用C#实现了基本的哈夫曼树 //哈夫曼树构造的基本思想，从list中取出最小的两个节点，构造出他们的父节点，
//然后将这两个节点从list中删除，将他们的父节点插入list中，左孩子code设置为0，右孩子code设置为1，
//直到list为空。
//接下来遍历以list中节点为根节点的树。
public class HuffmanTree
{
private List<HuffmanNode> nodes=new List<HuffmanNode>（）;
public HuffmanTree（List<HuffmanNode> node）//哈夫曼树初始胡
{
foreach （HuffmanNode n in node）
nodes.Add（n）;
initTree（）;
}
private void initTree（）
{
while （nodes.Count > 1）
{
List<HuffmanNode> n = getminimum2（）;
HuffmanNode p = new HuffmanNode（）;
n[0].code += "0" + n[0].code;
n[1].code += "1" + n[1].code;
p.weight = n[0].weight + n[1].weight;
p.left = n[0];
p.right = n[1];
n[0].parent = p;
n[1].parent = p;
nodes.Add（p）;
}

}
private List<HuffmanNode> getminimum2（）//第一个最小，第二个第二小,并且删除这两个节点
{
List<HuffmanNode> n = new List<HuffmanNode>（）;
n.Add（nodes[0].weight > nodes[1].weight ？ nodes[1] : nodes[0]）;
n.Add（nodes[0].weight > nodes[1].weight ？ nodes[0] : nodes[1]）;
for （int i = 2; i < nodes.Count; i++）
{
if （n[0].weight > nodes[i].weight）
{
n[1] = n[0];
n[0] = nodes[i];
}
else if （n[1].weight > nodes[i].weight）
{
n[1] = nodes[i];
}
}
nodes.Remove（n[0]）;
nodes.Remove（n[1]）;
return n;
}
public void Visit（）
{
if（nodes.Count>0）
visitTree（nodes[0],"",""）;
}
private void visitTree（HuffmanNode node,String prefixStr,String addStr）
{
if （node ！= null）
{
if （node.data ！= null）
Console.WriteLine（node.data.ToString（） + ":" + prefixStr + addStr）;
visitTree（node.left,prefixStr+addStr,"0"）;
visitTree（node.right, prefixStr + addStr, "1"）;
}
}
}
public class HuffmanNode
{
public String data=null;//需要编码的字符，组合节点的字符为空
public int weight;//权重
public String code="";//字符编码
public HuffmanNode parent , left, right;
}
测试代码：首先是添加了一些节点，接下来Visit哈夫曼树即可输出每一个节点的哈夫曼编码： List<HuffmanNode> list = new List<HuffmanNode>（）;

HuffmanNode n1 = new HuffmanNode（）;
n1.data="A";
n1.weight = 5;
list.Add（n1）;
HuffmanNode n2 = new HuffmanNode（）;
n2.data = "B";
n2.weight = 24;
list.Add（n2）;
HuffmanNode n3 = new HuffmanNode（）;
n3.data = "C";
n3.weight = 7;
list.Add（n3）;
HuffmanNode n4 = new HuffmanNode（）;
n4.data = "D";
n4.weight = 17;
list.Add（n4）;
HuffmanNode n5 = new HuffmanNode（）;
n5.data = "E";
n5.weight = 34;
list.Add（n5）;
HuffmanNode n6 = new HuffmanNode（）;
n6.data = "F";
n6.weight = 5;
list.Add（n6）;
HuffmanNode n7 = new HuffmanNode（）;
n7.data = "G";
n7.weight = 13;
list.Add（n7）;
HuffmanTree t = new HuffmanTree（list）;
t.Visit（）;
Console.Read（）;运行结果：代码下载：------------------------------------------分割线------------------------------------------免费下载地址在 http://linux.linuxidc.com/用户名与密码都是www.linuxidc.com具体下载目录在 /2014年资料/10月/15日/C# 哈夫曼树下载方法见 http://www.linuxidc.com/Linux/2013-07/87684.htm------------------------------------------分割线------------------------------------------C#多线程编程实例线程与窗体交互【附源码】 http://www.linuxidc.com/Linux/2014-07/104294.htmC#数学运算表达式解释器 http://www.linuxidc.com/Linux/2014-07/104289.htm在C语言中解析JSON配置文件 http://www.linuxidc.com/Linux/2014-05/101822.htmC++ Primer Plus 第6版中文版清晰有书签PDF+源代码 http://www.linuxidc.com/Linux/2014-05/101227.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-10/108086.htm