哈夫曼树创建
#include "stdafx.h"#include<stdlib.h>
typedef char ElemType;//要加分号
void creathafuman(int n);
typedef struct node
{
ElemType data;
int weight;
int parent;
int lchild;
int rchild;
}htnode;
int main()
{
creathafuman(3);
return 0;
}
void creathafuman(int n)//n是哈夫曼树叶子结点个数
{
htnode *p;
p = (htnode *)malloc((2 * n - 1) * sizeof(htnode));
int i; for (i = 0; i < 2*n - 1; i++)
{
p[i].parent = p[i].lchild = p[i].rchild = -1;
}
for (i = 0; i < n; i++)
{
scanf_s("%d", &p[i].weight,1);//输入叶子结点的权重
}
int min1 = 0, min2 = 0, e, f;//min1,min2存储最小权重值，e ,f存储最小权重的数组下标
int j;
for (j = 0; j < n; j++)
{
for (i = 0; i<=n+j; i++)
{
while (p[i].parent == -1)
{
if (min1 == 0)
{
min1 = p[i].weight;
e = i;
break;
}
if (min2 == 0)
{
min2 = p[i].weight;
f = i;
break;
}
if (min1 >= min2)
{
if (p[i].weight< min1)
{
min1 = p[i].weight;
e = i;
}
}
else
if (p[i].weight < min2)
{
min2 = p[i].weight;
f = i;
}
}
}
p[n + j + 1].weight =(min1 + min2);
p[n + j + 1].lchild = e;
p[n + j + 1].rchild = f;
p[e].parent = n + j + 1;
p[f].parent = n + j + 1;
}
printf("%d", p[2 * n - 2].weight);
}
