问题 B: 简单哈夫曼树
时间限制: 1 Sec 内存限制: 128 MB
提交: 543 解决: 343
[提交][状态]
题目描述
给出n个结点的描述,构造一棵哈夫曼树。
输入
第一行是一个正整数t。
接下来有t组数据,每组数据有两行。
第一行是一个正整数n,表示有n个结点。
第二行是n个整数,第i个整数mi表示编号为i的结点权重为mi。
(0<t<100, 1<=n<=1000, 0<mi<=100)
输出
每组数据输出一个整数,表示哈夫曼树的带权路径长度。
样例输入
1 4 1 3 5 7
样例输出
29
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{
int weight;
struct node* parent;
struct node* lchild;
struct node* rchild;
}hfmtree;
int caculate(hfmtree*root,int depth)//计算带权路径长度
{
if(root==NULL)
return 0;
if(root->lchild==NULL&&root->rchild==NULL)
{
return root->weight*depth;
}
return caculate(root->lchild,depth+1)+caculate(root->rchild,depth+1);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int data[500];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&data[i]);
}
hfmtree**nodes=(hfmtree**)malloc(n*sizeof(hfmtree*));
for(int i=0;i<n;i++)
{
hfmtree*temp=(hfmtree*)malloc(sizeof(hfmtree));
temp->weight=data[i];
temp->lchild=NULL;
temp->rchild=NULL;
temp->parent=NULL;
nodes[i]=temp;
}//创造初始节点
while(n>1)
{
// 找到权重最小的两个节点
int min1 = 0, min2 = 1;
if (nodes[min1]->weight > nodes[min2]->weight) {
int temp = min1;
min1 = min2;
min2 = temp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
hfmtree*merged=(hfmtree*)malloc(sizeof(hfmtree));//合并节点
merged->weight=nodes[min1]->weight+nodes[min2]->weight;
merged->lchild=nodes[min1];
merged->rchild=nodes[min2];
merged->parent=NULL;
nodes[min1]->parent=merged;
nodes[min2]->parent=merged;
nodes[min1]=merged;
nodes[min2]=nodes[n-1];
n--;//将新节点插入nodes
}
int ans=caculate(nodes[0],0);
printf("%d\n",ans);
}
return 0;
}