哈夫曼树及编码 分数 10 作者 王东 单位 贵州师范学院 构造哈夫曼树，计算WPL。 函数接口定义： void CreateHTree(); void CreateHCode();

哈夫曼树是一种用于解决编码问题的树形数据结构。它的构造过程是将待编码的字符按照出现频率从小到大排序，然后依次取出相邻的两个字符，将它们合并为一个节点，并将它们出现的频率相加作为新节点的频率。这个过程不断重复，直到所有的字符都被合并成一个根节点为止。

WPL是哈夫曼树的带权路径长度，它是将每个叶节点的权值（即出现频率）乘以它到根节点的路径长度之和。计算WPL只需要遍历哈夫曼树，累加每个叶节点的权值和路径长度的乘积，就可以得到最终结果。

下面是一个简单的哈夫曼编码的实现：

void CreateHTree()
{
int i, j, m1, m2, n;
n = 10; //待编码字符的数量
for (i = 1; i <= n; i++)
{
scanf("%d", &w[i]); //输入每个字符的频率
ht[i].parent = 0; //初始化每个节点的父节点
ht[i].lchild = 0; //初始化每个节点的左子节点
ht[i].rchild = 0; //初始化每个节点的右子节点
}
for (i = n + 1; i <= 2 * n - 1; i++)
{
ht[i].weight = 0; //初始化所有新节点的权值为0
ht[i].parent = 0; //初始化所有新节点的父节点为0
ht[i].lchild = 0; //初始化所有新节点的左子节点为0
ht[i].rchild = 0; //初始化所有新节点的右子节点为0
}
for (i = n + 1; i <= 2 * n - 1; i++)
{
m1 = m2 = INF;
ht[i].weight = w[i - n]; //将新节点的权值设为合并后的两个节点的权值之和
for (j = 1; j <= i - 1; j++)
{
if (ht[j].parent == 0)
{
if (ht[j].weight < m1)
{
m2 = m1;
m1 = ht[j].weight;
ht[i].lchild = j; //将新节点作为两个权值最小的节点的父节点
}
else if (ht[j].weight < m2)
{
m2 = ht[j].weight;
ht[i].rchild = j; //将新节点作为次小的节点的父节点
}
}
}
ht[ht[i].lchild].parent = i;
ht[ht[i].rchild].parent = i;
}
}

void CreateHCode()
{
int i, j, k;
char code[100];
for (i = 1; i <= n; i++)
{
k = i;
j = 0;
while (ht[k].parent != 0)
{
if (ht[ht[k].parent].lchild == k)
code[j++] = '0';
else
code[j++] = '1';
k = ht[k].parent;
}
code[j] = '\0';
strcpy(hc[i], strrev(code));
}
}

在这个实现中，我们将待编码字符的数量预设为10，可以根据实际情况进行修改。我们首先输入每个字符的频率，然后根据它们的频率构造哈夫曼树。在构造树的过程中，我们用ht数组来存储节点的相关信息，包括权值、父节点、左子节点和右子节点。当树构造完成后，我们就可以用CreateHCode函数来生成每个字符的哈夫曼编码了。