哈夫曼树，二叉树的一种，称为最优二叉树。给定N个权值作为N个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为哈夫曼树。

 一、图文介绍

    我们给定六个节点，每个节点的权重为{3, 2, 5, 1, 9, 7}。

1.1，选取第一步

    我们选取最小权重的两个节点1和2，组成一个二叉树。

1.2，选取第二步

    第二步，我们第一步生成了一个新的权重为3的节点，我们再去剩余节点中找取最小权重的节点和它组成新的二叉树：

1.3，选取第三步

1.4，选取第四步和第五步

二、算法实现

2.1，初始化

    我们叶子节点有6个，那么最终二叉树节点必然有2*6-1=11个节点（2*n-1），所以我们一开始申请11个节点的动态堆空间：

struct huffmanNode
{
    unsigned  int weight;
    unsigned  int parent;
    unsigned  int lchild;
    unsigned  int rchild;
};

typedef struct huffmanNode * huffmanTree;

typedef char * * huffmanCode;


char ** huffmanCoding(huffmanTree,int);

void huffmanSelect(huffmanTree,int,int *,int *);

void freeHuffman(huffmanTree,huffmanCode);

void testHuffman();

void printHuffman(huffmanTree,int);

huffmanTree initHuffman(huffmanTree, unsigned int *,int);

huffmanTree initHuffman(huffmanTree ht, unsigned int *w,int n)
{
    if(n<=1)
        return NULL;

    int node = 2 * n - 1; //定义节点总数
    int w1,w2;

    ht = (huffmanTree)malloc(node*sizeof(struct huffmanNode)); //动态申请空间

    huffmanTree hp;
    int i;
    for(hp = ht,i = 1;i<=n;++i,++hp,++w){   //叶子节点初始化
        hp->weight = *w;
        hp->parent = 0;
        hp->lchild = -1;
        hp->rchild = -1;
    }
    for(;i<=node;++i,++hp){  //父节点初始化
        hp->weight = 0;
        hp->parent = 0;
        hp->lchild = -1;
        hp->rchild = -1;
    }
    for(i=n;i<node;++i)
    {
        huffmanSelect(ht,i,&w1,&w2);
        printf("the left clild index is:%d,the right child is:%d\n",w1,w2);
        if(w1!=w2)
        {
            ht[w1].parent = i;
            ht[w2].parent = i;
            ht[i].lchild = w1;
            ht[i].rchild = w2;
            ht[i].weight = ht[w1].weight + ht[w2].weight;
        }

    }
    return ht;
}

2.2，节点选择：

void huffmanSelect(huffmanTree ht,int n,int *s1,int *s2)
{
    int min1=10000,min2=10000;
    int idx1=0,idx2=0;

    for(int i=0;i<n;i++)
    {
        if(!ht[i].parent&&ht[i].weight<min1)
        {
            min2=min1;
            idx2=idx1;
            min1 = ht[i].weight;
            idx1 = i;
        }else if(!ht[i].parent&&ht[i].weight<=min2)
        {
            min2=ht[i].weight;
            idx2 = i;
        }
    }
    *s1 = idx1;
    *s2 = idx2;

}

2.3，哈夫曼编码

char ** huffmanCoding(huffmanTree ht,int n)
{


    huffmanCode hc = (huffmanCode)malloc((n+1)*sizeof(char *)); //动态申请指针数组空间
    char *cd = (char *)malloc(n*sizeof(char));  //动态申请哈夫曼编码字符串空间
    int idx;
    int cur;
    cd[n-1] = '\0';
    for(int i=0;i<n;i++)
    {
        char *pc = cd;  
        idx = ht[i].parent;  //最找父亲节点
        cur = i;
        while(idx!=0)
        {
            if(ht[idx].lchild==cur)  //如果当前节点为左节点，则编码为1
            {
                *pc++ = '1';
            } else if(ht[idx].rchild==cur)  //如果当前节点为左节点，则编码为0
            {
                *pc++ = '0';
            }
            cur = idx;
            idx = ht[idx].parent;
        }
        *pc = '\0';
        hc[i] = (char *)malloc((pc-cd)); 
        strcpy(hc[i],cd); //我们只拷贝需要的长度字符

    }
    free(cd);
    return hc;
}

2.4，打印哈夫曼和测试哈夫曼编码

void printHuffman(huffmanTree ht,int len)
{
    for(int i=0;i<len;i++)
    {
        int left = ht[i].lchild == -1?0:ht[ht[i].lchild].weight;
        int rigth = ht[i].rchild == -1?0:ht[ht[i].rchild].weight;
        int parent = ht[i].parent == 0?0:ht[ht[i].parent].weight;
        printf("the %d element weight is %d; lchild index is %d, lchild weight is %d, rchild index is %d, rchild weight is %d; parent index is %d parent weight is %d\n",i,ht[i].weight,ht[i].lchild,left,ht[i].rchild,rigth,ht[i].parent,parent);
    }
}

void testHuffman()
{
    huffmanTree ht = NULL;
    unsigned  int w[] = {3,2,5,1,9,7};
    ht = initHuffman(ht,w,6);
    huffmanCode hc ;
    hc = huffmanCoding(ht,6);
    printHuffman(ht,2*6-1);
    for(int i=0;i<6;i++)
    {
        printf("the element %d huffmancode is:",ht[i].weight);
        char *p = hc[i];
        int idx = 0;
        while(*p++){
            idx++; //记录编码长度
        }
        p = hc[i];
        char *t;
        for(t=p+idx;t>=p;t--){ //倒序输出编码
            printf("%c",*t);
        }
        printf("\n");
        //printf("%s\n",hc[i]);

    }
    freeHuffman(ht,hc);
}

2.5，结果