#include<iostream.h>
#define Max 21
typedef struct{
    char data;
    int weight;
    int parent;
    int left;
    int right;
}huffnode;
typedef struct{
    char cd[Max];
    int start;
}huffcode;
void main(){
    huffnode ht[2*Max];
    huffcode hcd[Max],d;
    int i,k,f,r,l,n,c,m1,m2;
    cout<<"元素个数：";
    cin>>n;
    for(i=1;i<=n;i++){
        cout<<"第"<<i<<"个元素=>\t节点值：";
        cin>>ht[i].data;
        cout<<"\t\t权 重：";
        cin>>ht[i].weight;
    }
    for(i=1;i<=2*n-1;i++)
        ht[i].parent=ht[i].left=ht[i].right=0;
    for(i=n+1;i<=2*n-1;i++){
        m1=m2=32767;
        l=r=0;
        for(k=1;k<=i-1;k++)
            if(ht[k].parent==0)
                if(ht[k].weight<m1){
                    m2=m1;
                    r=l;
                    m1=ht[k].weight;
                    l=k;
                }
                else if(ht[k].weight<m2){
                    m2=ht[k].weight;
                    r=k;
                }
                ht[l].parent=i;
                ht[r].parent=i;
                ht[i].weight=ht[l].weight+ht[r].weight;
                ht[i].left=l;
                ht[i].right=r;
    }
    for(i=1;i<=n;i++){
        d.start=n+1;
        c=i;
        f=ht[i].parent;
        while(f!=0){
            if(ht[f].left==c)
                d.cd[--d.start]='0';
            else
                d.cd[--d.start]='1';
            c=f;
            f=ht[f].parent;
        }
        hcd[i]=d;
    }
    cout<<"输入赫夫曼编码：\n";
    for(i=1;i<=n;i++){
        cout<<"  "<<ht[i].data<<":";
        for(k=hcd[i].start;k<=n;k++)
            cout<<hcd[i].cd[k];
        cout<<endl;
    }
}