C#求解哈夫曼树,实例代码
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;
}
}
推荐阅读