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

时间:2021-05-20

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

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章