一，什么是哈夫曼树

什么是哈夫曼树呢？

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。下面用一幅图来说明。

它们的带权路径长度分别为：

图a： WPL=5*2+7*2+2*2+13*2=54

图b： WPL=5*3+2*3+7*2+13*1=48

可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

二，如何构建哈夫曼树

一般可以按下面步骤构建：

1，将所有左，右子树都为空的作为根节点。

2，在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。

3，从森林中删除这两棵树，同时把新树加入到森林中。

4，重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。

下面是构建哈夫曼树的图解过程：

三，哈夫曼编码

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。

就拿上图例子来说：

A，B，C，D对应的哈夫曼编码分别为：111，10，110，0

用图说明如下：

记住，设计电文总长最短的二进制前缀编码，就是以n个字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。

#include<stdlib.h>
#include<stdio.h>
#include<string.h>

#define BEGIN -1

/**
 * 哈夫曼树结点
 */
typedef struct {
    int weight;
    int parent, left, right;
}HTNode, *HuffmanTree;

typedef char ** HuffmanTable; //动态分配存储各个字符哈夫曼编码的表


/**
 * 从树集中选取parent = 0，weight最小的两个结点，其下标存入s1,12
 */
void select_min_two(HuffmanTree htree, int end, int *s1, int *s2)
{
    int min1, min2;
    int i = 1;
    while(htree[i].parent != 0 && i<=end)
        i++;
    min1 = htree[i].weight;
    *s1 = i;

    i++;
    while(htree[i].parent != 0 && i<=end)
        i++;
    if(htree[i].weight < min1){
        min2 = min1;
        *s2 = *s1;
        min1 = htree[i].weight;
        *s1 = i;
    }else{
        min2 = htree[i].weight;
        *s2 = i;
    }



    for(int j=i+1; j <= end; j++)
    {
        if(htree[j].parent != 0)
            continue;

        if(htree[j].weight < min1){
            min2 = min1;
            min1 = htree[j].weight;
            *s2 = *s1;
            *s1 = j;
        }else if(htree[j].weight >= min1 && htree[j].weight < min2){
            min2 = htree[j].weight;
            *s2 = j;
        }
    }
}

/**
 * htree: 建立之后的哈夫曼树
 * htable: 建立之后的哈夫曼编码表
 * w: n个字符的权值数组
 * n: 待编码字符的个数
 */
void huffman_coding(HuffmanTree *htree, HuffmanTable *htable, int *w, int n)
{

    if(n<=1) return; // 如果只有一个编码就相当于0
    int m = 2*n-1; // 哈夫曼树总节点数，n就是叶子结点
    *htree = (HuffmanTree) malloc((m+1) * sizeof(HTNode)); // 0号位置不用

    HuffmanTree p = *htree;

    // 初始化整棵树
    for(int i=1; i<=n; i++)
    {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }

    for(int i=n+1; i<=m; i++)
    {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }


    // 建立哈夫曼树
    for(int i=n+1; i<=m; i++)
    {
        int s1, s2;
        select_min_two(*htree, i-1, &s1, &s2);
        (*htree)[s1].parent = (*htree)[s2].parent = i;
        (*htree)[i].left = s1;
        (*htree)[i].right = s2;
        (*htree)[i].weight = (*htree)[s1].weight + (*htree)[s2].weight;
    }

    // 生成哈夫曼表，从叶子到根求每个字符的哈夫曼编码
    *htable = (HuffmanTable) malloc((n+1) * sizeof(char *)); // 0号元素不用，相当于保存n个C字符串
    char *eachCode = (char *)malloc(n*sizeof(char)); // 每个字符对应的编码字符串
    eachCode[n-1] = '\0';
    for(int i=1; i<=n; i++)
    {
        int start = n-1; // 因为是逆向编码，所以要从后面填充编码字符串
        int current = i;
        int j = (*htree)[i].parent;
        // 一直寻找到根结点
        while(j != 0){
            // 如果改结点是父亲结点的左孩子则对应路径编码为0，否则为右孩子编码为1
            if((*htree)[j].left == current)
                eachCode[--start] = '0';
            else
                eachCode[--start] = '1';

            current = j;
            j = (*htree)[j].parent;
        }

        // 为第i个字符编码分配空间, n-start 表示字符数
        (*htable)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*htable)[i], &eachCode[start]);
    }

    free(eachCode);
}

/**
 * 打印Huffman树
 */
void print_huffman_tree(HuffmanTree htree, int n)
{
    printf("Huffman tree: \n");
    int m = 2*n-1;
    for(int i=1; i<=m; i++)
        printf("node_%d, weight = %d, parent = %d, left = %d, right = %d\n", i, htree[i].weight, htree[i].parent, htree[i].left, htree[i].right);
}

/**
 * 打印Huffman编码表中所有编码
 */
void print_all_huffman_code(HuffmanTable htable, int n)
{
    printf("Huffman code table: \n");
    for(int i=1; i<=n; i++)
        printf("%d code = %s\n", i, htable[i]);
}

int main(void)
{
    int w[5] = {2, 8, 7, 6, 5};
    int n=5;
    HuffmanTree htree;
    HuffmanTable htable;

    huffman_coding(&htree, &htable, w, n);

    print_huffman_tree(htree, n);
    print_all_huffman_code(htable, n);


    return 0;
}