哈夫曼树编码 代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;

void Select(HuffmanTree HT,int n,int &first,int &second)
{
    int min=100000;
    for (int i=0;i<n;i++){
        if(min>HT[i].weight&&HT[i].parent==0){
            first=i;
            min=HT[i].weight;
        }
    }
    min=100000;
    for (int i=0;i<n;i++)
    {
        if(min>HT[i].weight&&first!=i&&HT[i].parent==0){
            second=i;
            min=HT[i].weight;
        }
    }
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
    if(n<1) return;
    int m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for (int i=0;i<n;i++){
        HT[i].weight=w[i];
        HT[i].parent=HT[i].lchild=HT[i].rchild=0;
    }
    for(int j=n;j<m+1;j++){
        HT[j].weight=0;
        HT[j].parent=HT[j].lchild=HT[j].rchild=0;
    }
    for(int i=n;i<m;i++){
        int first,second;
        Select(HT,i,first,second);
        HT[i].lchild=first;
        HT[i].rchild=second;
        HT[first].parent=i;
        HT[second].parent=i;
        HT[i].weight=HT[first].weight+HT[second].weight;
        printf("%d(%d,%d)\n",HT[i].weight,HT[first].weight,HT[second].weight);
    }
    
    
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
    char *cd=(char*)malloc(sizeof(char)*(n+1));
    cd[n-1]='\0';
    for(int i=0;i<n;i++)
    {
        int start=n-1;
        for(int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
            if(HT[f].lchild==c) cd[--start]='0';
            else cd[--start]='1';
        }
        HC[i]=(char *)malloc(sizeof(char)*(n-start));
        strcpy(HC[i],&cd[start]);
    }
    free(cd);
}
int main()
{
    int w[100],n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&w[i]);
    }
    HuffmanCode HC;
    HuffmanTree HT;
    HuffmanCoding(HT,HC,w,n);
    for(int i=0;i<n;i++)
    {
        printf("%s\n",HC[i]);
    }
}