复制代码 代码如下:
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;
}
}