#include <string.h>
#include <iostream.h>
#include <conio.h>
const int Max=21;
  typedef struct                        //定义结点 结构体
      {
      int weight;
      char data;
      int  lchild,rchild,parent;
       }huffnode;
 typedef struct
 {
     char cd[Max];
     int start;
 }huffcode;
 //void HuffmanTree(NodeType huffTree[],int w[],int n)
        
    
void main()
{
    huffnode ht[2*Max];
    huffcode hcd[Max],d;
    int i,k,f,l,r,n,c,m1,m2;
    cout<<"元素个数:";
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cout<<"参考课本P181字符编码"<<endl;
        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].lchild=ht[i].rchild=0;
    for(i=n+1;i<=2*n-1;i++)//构造huffman树
    {
        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].lchild=l;
                ht[i].rchild=r;
    }
    for(i=1;i<=n;i++)//编码
    {
        d.start=n+1;
        c=i;
        f=ht[i].parent;
        while(f!=0)
        {
            if(ht[f].lchild==c)
                d.cd[--d.start]='0';
            else
                d.cd[--d.start]='1';
            c=f;
            f=ht[f].parent;
        }
        hcd[i]=d;
    }
    cout<<"输出huffman编码";
    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;
    }
}