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;
        }

   }