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=http://www.mamicode.com/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=http://www.mamicode.com/"A";
            n1.weight = 5;
            list.Add(n1);
            HuffmanNode n2 = new HuffmanNode();
            n2.data = http://www.mamicode.com/"B";
            n2.weight = 24;
            list.Add(n2);
            HuffmanNode n3 = new HuffmanNode();
            n3.data = http://www.mamicode.com/"C";
            n3.weight = 7;
            list.Add(n3);
            HuffmanNode n4 = new HuffmanNode();
            n4.data = http://www.mamicode.com/"D";
            n4.weight = 17;
            list.Add(n4);
            HuffmanNode n5 = new HuffmanNode();
            n5.data = http://www.mamicode.com/"E";
            n5.weight = 34;
            list.Add(n5);
            HuffmanNode n6 = new HuffmanNode();
            n6.data = http://www.mamicode.com/"F";
            n6.weight = 5;
            list.Add(n6);
            HuffmanNode n7 = new HuffmanNode();
            n7.data = http://www.mamicode.com/"G";
            n7.weight = 13;
            list.Add(n7);
            HuffmanTree t = new HuffmanTree(list);
            t.Visit();


            Console.Read();

运行结果：