下面的例子用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.htm
C#數學運算表達式解釋器 http://www.linuxidc.com/Linux/2014-07/104289.htm
在C語言中解析JSON配置文件 http://www.linuxidc.com/Linux/2014-05/101822.htm
C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm
