假设有n个权值{w1, w2, ..., wn}，试构造一颗有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。

构造赫夫曼树

赫夫曼算法：

1. 根据给定的n个权值{w1, w2, ..., wn}构成N棵二叉树的集合F = {T1, T2,... , Tn}，其中每棵而茶水Ti中只有一个带权为wi的跟结点，其左右子树均空。
2. 在F中选取两颗跟结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的跟结点的权值为其左、右树上跟结点的权值之和。
3. 在F中删除这两棵树，同时将新得到的二叉树加入F中。
4. 重复（2）（3），直到F只含一棵树为止。这棵树便是赫夫曼树。

代码实现

const int MaxValue = 10000;
const int MaxBit = 4;
const int MaxN = 10;

typedef struct HaffNode {
    int weight;
    int flag;
    int parent;
    int leftChild;
    int rightChild;
} HaffNode;

void Haffman(int weight[], int n, HaffNode *haffTree) {
    // 初始化
    for (int i = 0; i < 2 * n - 1; i++) {
        if (i < n) {
            haffTree[i].weight = weight[i];
        } else {
            haffTree[i].weight = 0;
        }
        
        haffTree[i].flag = 0;
        haffTree[i].parent = 0;
        haffTree[i].leftChild = -1;
        haffTree[i].rightChild = -1;
    }
    
    int j, m1, m2, x1, x2;
    for (int i = 0; i < n - 1; i++) {
        m2 = m1 = MaxValue;
        x2 = x1 = 0;
        for (j = 0; j < n + i; j++) {
            if (haffTree[j].weight < m1 && haffTree[j].flag == 0) {
                m2 = m1 = haffTree[j].weight;
                x2 = x1 = j;
            } else if (haffTree[j].weight < m2 && haffTree[j].flag == 0) {
                m2 = haffTree[j].weight;
                x2 = j;
            }
        }
        
        haffTree[x1].parent = n + i;
        haffTree[x1].flag = 1;
        
        haffTree[x2].parent = n + i;
        haffTree[x2].flag = 1;
        
        haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
        haffTree[n + i].leftChild = x1;
        haffTree[n + i].rightChild = x2;
    }
}

赫夫曼编码

哈夫曼编码是一种编码方式，该方法依据字符出现概率来构造异字头的平均长度最短的码字，一般就叫做Huffman编码。

哈夫曼思想就是依据使用的频率来最大化的节省字符存储空间。

代码实现

typedef struct Code {
    int bit[MaxBit];
    int start;
    int weight;
} Code;

void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[]) {
    Code *cd = (Code *)malloc(sizeof(Code));
    int child, parent;
    for (int i = 0; i < n; i++) {
        cd->start = 0;
        cd->weight = haffTree[i].weight;
        child = i;
        parent = haffTree[child].parent;
        while (parent != 0) {
            if (haffTree[parent].leftChild == child) {
                cd->bit[cd->start] = 0;
            } else {
                cd->bit[cd->start] = 1;
            }
            
            cd->start++;
            child = parent;
            parent = haffTree[child].parent;
        }
        
        int temp;
        for (int j = cd->start - 1; j >= 0; j--) {
            temp = cd->start - 1 - j;
            haffCode[i].bit[temp] = cd->bit[j];
        }
        
        haffCode[i].start = cd->start;
        haffCode[i].weight = cd->weight;
    }
    free(cd);
}