题解 | #哈夫曼树#

#include<stdio.h>
struct tree
{
    int weight;
    int left;
    int right;
    int parent;
    int car;   //1表明该节点要加入计算
};
void insert(int y[],struct tree haf[],int z){
    int a,min1=100000000,min2=100000000,count1,count2;
    for(int i=0;i<2000;i++){
        if(y[i]<min1&&y[i]!=-1){
            min1=y[i];
            count1=i;
        }
    }
    y[count1]=-1;
    for(int i=0;i<2000;i++){
        if(y[i]<min2&&y[i]!=-1){
            min2=y[i];
            count2=i;
        }
    }
    y[count2]=-1;
    a=min1+min2;
    y[z]=a;
    haf[z].weight=a;
    haf[z].left=count1;
    haf[z].right=count2;
    haf[count1].parent=z;
    haf[count2].parent=z;
    return;
}
void cal(int sum1[],struct tree haf[],int head,int e){
    if(haf[head].car==1){
        sum1[0]=sum1[0]+e*haf[head].weight;
    }
    if(haf[head].left!=-1){
        cal(sum1,haf,haf[head].left,e+1);
    }
    if(haf[head].right!=-1){
        cal(sum1,haf,haf[head].right,e+1);
    }
    return;
}
int main(){
    int b,n,m[2000],count,sum[1],k=0;
    struct tree haff[2000];
    for(int i=0;i<2000;i++){
        haff[i].left=-1;
        haff[i].right=-1;
        haff[i].parent=-1;
        haff[i].car=-1;
        haff[i].weight=-1;
        m[i]=-1;
    }
    scanf("%d",&n);
    for(b=0;b<n;b++){
        int j;
        scanf("%d",&j);
        m[b]=j;
        haff[b].weight=j;
        haff[b].car=1;
    }
    for(int i=0;i<n-1;i++){
        insert(m,haff,b);
        b++;
    }
    for(int i=0;i<2000;i++){
        if(m[i]!=-1){
            count=i;
            break;
        }
    }
    sum[0]=0;
    cal(sum,haff,count,k);
    printf("%d",sum[0]);
    return 0;
}