问题 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;
}
