代码清单如下：
#pragma once
#include<stdio.h>
#include"stdlib.h"
#include <string.h> typedef int ElemType1; struct BTreeNode
{
ElemType1 data;
struct BTreeNode* left;
struct BTreeNode* right;
};
//遍历哈夫曼树
void PrintBTree_int(struct BTreeNode* BT)
{
if (BT != NULL)
{
printf("%d", BT->data);
if (BT->left != NULL || BT->right != NULL)
{
printf(" ( ");
PrintBTree_int(BT->left); //输出左子树
if (BT->right != NULL)
printf(" , ");
PrintBTree_int(BT->right); //输出右子树
printf(" ) ");
}
}
} //创建哈夫曼树
struct BTreeNode* CreateHuffman(ElemType1 a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = (BTreeNode **)malloc(n * sizeof(struct BTreeNode));
for (i = ; i < n; i++) //动态内存分配
{
b[i] = (BTreeNode *)malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = ; i < n; i++)
{
//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
int k1 = -, k2;
for (j = ; j < n; j++) //让k1初始指向森林中第一棵树，k2指向第二棵
{
if (b[j] != NULL && k1 == -)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++) //构造最优解
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
q = (BTreeNode *)malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2]; b[k1] = q;
b[k2] = NULL;
}
free(b);
return q;
}
//计算带权路径
ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0
{
if (FBT == NULL) //空树返回0
return ;
else
{
if (FBT->left == NULL && FBT->right == NULL)
return FBT->data * len;
else
return WeightPathLength(FBT->left, len + ) + WeightPathLength(FBT->right, len + );
}
} //构造哈夫曼编码
void HuffManCoding(struct BTreeNode* FBT, int len)
{
static int a[];
if (FBT != NULL)
{
if (FBT->left == NULL && FBT->right == NULL)
{
int i;
printf("结点的值为%d的编码：", FBT->data);
for (i = ; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
else
{
a[len] = ;
HuffManCoding(FBT->left, len + );
a[len] = ;
HuffManCoding(FBT->right, len + );
}
}
}