欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C#求解哈夫曼树,实例代码

程序员文章站 2023-12-17 19:21:34
复制代码 代码如下:  class huffmantree    {     &n...

复制代码 代码如下:

  class huffmantree
    {
        private node[] data;
        public int leafnum { get; set; }
        public node this[int index]
        {
            get { return data[index]; }
            set { data[index] = value; }
        }
        public huffmantree(int n)
        {
            data = new node[2 * n - 1];
            for (int i = 0; i < 2 * n - 1; i++)
            {
                data[i] = new node();
            }
            leafnum = n;
        }
        public void create(list<int> list)
        {
            int min1;
            int min2;
            int tmp1, tmp2;
            for (int i = 0; i < list.count; i++)
            {
                data[i].weight = list[i];
            }              
            for (int i = 0; i < leafnum-1; i++)
            {
                min1 = min2 = int.maxvalue;
                tmp1 = tmp2 = 0;

               //获取数组中最小的2个值
                for (int j = 0; j < leafnum + i; j++)
                {
                    if (data[j].weight<min1&&data[j].parent == -1)
                    {
                        min2 = min1;
                        tmp2 = tmp1;
                        min1 = data[j].weight;
                        tmp1 = j;
                    }
                   else if (data[j].weight < min2 && data[j].parent == -1)
                    {
                        min2 = data[j].weight;
                        tmp2 = j;
                    }                
                }
                data[tmp1].parent = this.leafnum + i;
                data[tmp2].parent = this.leafnum + i;
                data[this.leafnum + i].weight = data[tmp1].weight + data[tmp2].weight;
                data[this.leafnum + i].lchild = tmp1;
                data[this.leafnum + i].rchild = tmp2;
            }
        }


//树的结点(树是用数组保存的) 

public class node
    {
        public int weight { get; set; }//权值
        public int lchild { get; set; }//左孩子在数组中的位置
        public int rchild { get; set; }//右孩子在数组中的位置
        public int parent { get; set; }//父节点在数组中的位置
        public node()
        {
            weight = 0;
            lchild = -1;
            rchild = -1;
            parent = -1;//-1表示没有
        }
        public node(int weight,int lchild,int rchild,int parent )
        {
            this.weight = weight;
            this.lchild = lchild;
            this.rchild = rchild;
            this.parent = parent;
        }
    }

上一篇:

下一篇: