# include
# include
# include
typedef struct HuffmanTreeNode{
int weight;//权值
int parent;//父结点下标
int lchild, rchild;//左右孩子结点下标
}HFNode, *HFTree;
HFTree CreateHuffmanTree(HFTree HF, int n);//创建哈夫曼树
void SeleteMin(HFTree HF, int i, int * min1, int * min2);//寻找无父结点元素合集中的最小和次小元素及其对应下标
void PrintHuffmanTree(HFTree HF, int n);//打印哈夫曼树数组
void InOrderHuffmanTree(HFTree HF, int index);//中序遍历哈夫曼树
int HuffmanWPL(HFTree HF, int n);//哈夫曼树的带权路径长度
void HuffmanCoding(HFTree HF, char ** coding, int n);//哈夫曼编码
int main(void)
{
int n;
HFTree HF = NULL;
printf("请输入初始结点个数:");
scanf("%d", &n);
HF = CreateHuffmanTree(HF, n);
PrintHuffmanTree(HF, 2*n-1);
printf("中序遍历:");
InOrderHuffmanTree(HF, 2*n-2);
printf("n");
printf("树的带权路径长度WPL = %dn", HuffmanWPL(HF, n));
printf("哈夫曼编码:n");
char ** coding = (char**)malloc(n * sizeof(char*));
if(!coding)
exit(-1);
HuffmanCoding(HF, coding, n);
for(int i = 0; i < n; i++)
printf("%sn", coding[i]);
for(int i = 0; i < n; i++)
{
free(coding[i]);
coding[i] = NULL;
}
free(coding);
coding = NULL;
free(HF);
HF = NULL;
system("pause");
return 0;
}
//创建哈夫曼树
HFTree CreateHuffmanTree(HFTree HF, int n)
{
int total = 2*n - 1;
HF = (HFTree)malloc(total*sizeof(HFNode));
if(!HF)
exit(-1);
for(int i = 0; i < total; i++)
{
HF[i].parent = -1;
HF[i].lchild = -1;
HF[i].rchild = -1;
}
printf("请输入%d个权值:", n);
for(int i = 0; i < n; i++)
{
scanf("%d", &HF[i].weight);
}
int min1, min2;
for(int i = n; i < total; i++)
{
SeleteMin(HF, i, &min1, &min2);
HF[i].weight = HF[min1].weight + HF[min2].weight;
HF[i].lchild = min1;
HF[i].rchild = min2;
HF[min1].parent = i;
HF[min2].parent = i;
}
return HF;
}
//寻找无父结点元素合集中的最小和次小元素及其对应下标
void SeleteMin(HFTree HF, int i, int * min1, int * min2)
{
int Min1, Min2;//定义最小值和次小值
Min1 = Min2 = INT_MAX;//明示常量INT_MAX:int类型的最大值
for(int j = 0; j < i; j++)
{
if(HF[j].weight < Min1 && -1 == HF[j].parent)
{
Min2 = Min1;
*min2 = *min1;
Min1 = HF[j].weight;
*min1 = j;
}
else if(HF[j].weight < Min2 && -1 == HF[j].parent)
{
Min2 = HF[j].weight;
*min2 = j;
}
}
printf("最小元素为%d下标为%d, 次小元素为%d下标为%dn", HF[*min1].weight, *min1, HF[*min2].weight, *min2);
}
//打印哈夫曼树数组
void PrintHuffmanTree(HFTree HF, int num)
{
printf("下标tweighttparenttlchildtrchildn");
for(int i = 0; i < num; i++)
{
printf("%dt%dt%dt%dt%dn", i, HF[i].weight, HF[i].parent, HF[i].lchild, HF[i].rchild);
}
}
//中序遍历哈夫曼树
void InOrderHuffmanTree(HFTree HF, int index)
{
if(index != -1)
{
InOrderHuffmanTree(HF, HF[index].lchild);
printf("%d ", HF[index].weight);
InOrderHuffmanTree(HF, HF[index].rchild);
}
}
//哈夫曼树的带权路径长度
int HuffmanWPL(HFTree HF, int n)
{
int sum = 0;
for(int i = 0; i < n; i++)
{
int wpl = 0;
int pos = i;
int p_index = HF[i].parent;
while(p_index != -1)
{
pos = p_index;
p_index = HF[p_index].parent;
wpl++;
}
sum += HF[i].weight * wpl;
}
return sum;
}
void HuffmanCoding(HFTree HF, char ** coding, int n)
{
char * code = (char*)malloc(n *sizeof(char));//临时存放编码
if(!code)
exit(-1);
code[n-1] = ' ';
for(int i = 0; i < n; i++)
{
int start = n-1;
int pos = i;//当前处理结点下标
int p_index = HF[i].parent;
while(p_index != -1)
{
if(pos == HF[p_index].lchild)
code[--start] = '0';
else
code[--start] = '1';
pos = p_index;//当前位置向上移动
p_index = HF[p_index].parent;//当前位置的父节点向上移动
}
coding[i] = (char*)malloc((n-start) *sizeof(char));//创建实际编码空间
if(!coding[i])
exit(-1);
strcpy(coding[i], &code[start]);
}
free(code);
code = NULL;
}
