C# 哈夫曼树

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.bkjia.com/

用户名与密码都是www.bkjia.com

具体下载目录在 /2014年资料/10月/15日/C# 哈夫曼树

下载方法见

------------------------------------------分割线------------------------------------------

C#多线程编程实例 线程与窗体交互【附源码】

C#数学运算表达式解释器

在C语言中解析JSON配置文件

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码

本文永久更新链接地址：