#include <iostream>
#include <string>

using namespace std;
typedef struct
{
    int weight;  
    int parent;  
    int lchild; 
    int rchild; 
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;  

void SelectNode(HuffmanTree & HT,int n,int *s1,int *s2){
     int i;
     HuffmanTree ht1,ht2,t;
     ht1=ht2=NULL; 
     for(i=1;i<=n;++i)  
     {
        if(HT[i].parent==0)
         {
             if(ht1==NULL) 
             {
                 ht1= HT+i; //指向第i个结点 
                 continue; //继续循环 
             }
             if(ht2==NULL) {
                 ht2= HT+i; //指向第i个结点 
                 if(ht1->weight>ht2->weight) {
                     t=ht2;
                     ht2=ht1;
                     ht1=t;
                 }
                 continue; //继续循环 
             }
             if(ht1 && ht2){
                 if (HT[i].weight<=ht1->weight){
                     ht2=ht1;  
                     ht1= HT+i;  
                 }
                 else if( HT[i].weight<ht2->weight){ 
                     ht2= HT+i; 
                 }
             }
         }
     }
     if(ht1>ht2){ //增加比较，使二叉树左侧为叶结点 
         *s2=ht1- HT;
         *s1=ht2- HT;
     }
     else{
         *s1=ht1- HT;
         *s2=ht2- HT;
     }
}


void HuffmanCoding(HuffmanTree & HT,HuffmanCode &HC,int n,int *w)
{
    int i,m=2*n-1;
    HT=(HuffmanTree )malloc((m+1)*sizeof(HTNode));
    int s1,s2; 
    if(n<=1) return ;
    for(i=1;i<=n;++i) //初始化叶结点 
    {
        HT[i].weight=w[i-1];
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(;i<=m;++i)//初始化后续结点 
    {
         HT[i].weight=0;
        HT[i].parent=0;
        HT[i].lchild=0;
         HT[i].rchild=0;
    }
    for(i=n+1;i<=m;++i){
        SelectNode( HT,i-1,&s1,&s2); 
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight= HT[s1].weight+ HT[s2].weight;
    } 
     char *cd;
     int start;
     int current,parent; 
     HC=(HuffmanCode )malloc((n+1)*sizeof(char*));  
     cd=(char*)malloc(sizeof(char)*n);
     cd[n-1]='\0';                                 //设置字符串结束标志 
     for(i=1;i<=n;i++)
     {
         start=n-1;
         current=i;
         parent= HT[current].parent;                  //获取当前结点的父结点 
         while(parent)  {                             //父结点不为空
             if(current== HT[parent].lchild)            //左子树  
               cd[--start]='0';  
             else 
               cd[--start]='1';  
             current=parent;                        //设置当前结点指向父结点 
             parent= HT[parent].parent;              //获取当前结点的父结点序号    
         }
        HC[i-1]=(char*)malloc(sizeof(char)*(n-start));
         strcpy(HC[i-1],&cd[start]);        
     }
     free(cd); 
}

//将字符串转换为Huffman编码
void Encoding(HuffmanCode &HC,char *alphabet,char *str,char *code){   
    int len=0,i=0,j;
    code[0]='\0';
    while(str[i]){
        j=0;
        while(alphabet[j]!=str[i])
        j++;         
        strcpy(code+len,HC[j]); //将对应字母到code中 
        len=len+strlen(HC[j]); //累加字符串长度 
        i++;
    }
     code[len]='\0';
}
//将一个Huffman编码组成的字符串转换为明文字符串 
void Decoding(HuffmanTree & HT,int m,char *code,char *alphabet,char *decode){
    int position=0,i,j=0;
    m=2*m-1;
    while(code[position]) //字符串未结束 
     {
          for(i=m; HT[i].lchild &&  HT[i].rchild; position++) //在Huffman树中查找左右子树为空 ，以构造一个Huffman编码 
          {
              if(code[position]=='0') 
                  i= HT[i].lchild;
              else 
                  i= HT[i].rchild; 
          }
          decode[j]=alphabet[i-1]; //得到一个字母
          j++;//处理下一字符 
     }  
     decode[j]='\0'; //字符串结尾 
}
int main()
{
    int i,n=27,m; 
    char test[]="DBD BDABDCD ADBDADBDADACDBDBD";
    char code[100],code1[100];
    char alphabet[]={' ','A','B','C','D','E','F','G','H','I','J','K','L','M',
    'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; 
    int w[]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,
             63,15,1,48,51,80,23,8,18,1,16,1} ;
    HuffmanTree HT;
    HuffmanCode HC;    
    m=2*n-1;     
    HuffmanCoding( HT,HC,n,w); 
    for(i=1;i<=n;i++) {
        cout<<"字母"<<alphabet[i-1];
        cout<<"权重"<<HT[i].weight;
        cout<<"编码为"<<HC[i-1]<<endl;
          }
     Encoding(HC,alphabet,test,code);
    cout<<"字符串:"<<test<<"\n"
        <<"转换后为:"<<code<<endl;
     Decoding( HT,n,code,alphabet,code1); 
    cout<<"编码:"<<code<<"\n"
        <<"转换后为:"<<code1<<endl; 
    return 0;
}



程序出错是在输出霍夫曼编码之后执行中止