Question

求助一道数据结构题，用c/c++,感谢急急！

有8个元素，编号依次为1，2，3，4，5，6，7，8，它们的权重分别为：5，29，7，8，14，23，3，11。构造它们的哈弗曼树。最后输出已有元素对应的结点和增加的结点的上下级关系，比如：
Node:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
Parent:9,14,10,10,12,13,9,11,11,12,13,14,15,15,0

Answer 1

#include<stdio.h>

int const N=8;

int a[]={5,29,7,8,14,23,3,11};

struct pnp{

int w;

int pren;

}hfm[2*N-1];

void select(int n,int &a){

int t=0x7ffff;

for(int i=n;i>=0;i--)

if(hfm[i].w<=t&&hfm[i].pren==0){

t= hfm[i].w;

a=i;} 

hfm[a].pren=n+2;

}

void careat(int n){

int i, a,b;

for(i=n;i<2*n-1;i++){

select(i-1,a);

select(i-1,b);

hfm[i].pren=0;

hfm[i].w=hfm[a].w+hfm[b].w;

}

}

int main(){

int n=N;

printf("Node:");

    for(int i=0;i<2*n-1;i++){

    if(i<n)hfm[i].w=a[i];

    hfm[i].pren=0;

    printf("%d",i+1);

    if(i<2*n-2)printf(",");

}

printf("\nParent:");

careat(n);

for(int i=0;i<2*n-1;i++){

printf("%d",hfm[i].pren);

    if(i<2*n-2)printf(",");

}

return 0;

}