1. 最优二叉树(赫夫曼树)

带权路径长度(WPL):设二叉树有n个叶子结点，每个叶子结点带有权值W_K，从根结点到每个叶子结点的长度为L_k，则每个叶子结点的带权路径长度之和就是: WPL = ∑W_kL_k
最优二叉树(赫夫曼树): WPL最小的二叉树，每次把权值最小的两棵二叉树合并。
赫夫曼树的特点：

• 没有度为1的结点；
• n个叶子结点的赫夫曼树共有2n-1个节点；
• 赫夫曼树的任意非叶子结点的左右子树交换后仍为赫夫曼树。
• 对同一组权值{w₁,w₂,......,w_n}, 是否存在不同构的两棵赫夫曼树呢？
  对一组权值{1,2,3,3}, 不同构的两棵哈夫曼树：
  

构建赫夫曼树

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
    int weight;
    HuffmanTree left,right;
};
构建赫夫曼树
HuffmanTree Huffman(MinHeap H)
{
    int i;
    HuffmanTree T;
    buildMinHeap(H);
    for (i = 1; i < H->size; i++) {
        T = malloc(sizeof(struct TreeNode));
        T->left = deleteMin(H)；
        T->right = deleteMin(H);
        T->weight = T->left->weight + T->right->weight;
        insert(H, T);
    }
    T = deleteMin(H);
    return T;
}

• 构建赫夫曼树的整体时间复杂度为 T = O(N logN)

2. 赫夫曼编码

为了让编码尽可能的短，我们进行不等长编码。如下：
a: 1 e: 0 s: 10 t: 11
1011是什么字符串的编码？
aeaa: 1011
aet: 1011
st: 1011
因此这么编码会产生二义性
如何避免二义性呢？
前缀编码：任何字符的编码都不是另一个字符编码的前缀。

我们用二叉树进行编码：
(1) 左右分支：0、1
(2) 字符只在叶子结点上

四个字符的频率：a:4, u:1, x:2, z:1

1. 用等长编码方式：

   
   

2. 用赫夫曼树进行编码方式：

   
   

• 可以看出编码长度乘以频率之和后者较小。而且没有二义性。

赫夫曼编码代码：

typedef struct TreeNode *HuffmanTree;
typedef struct TreeNode HTNode;
struct TreeNode{
    unsigned int weight;
    unsigned int left,right, parent;
    bool minFlag;
};
typedef char** HuffmanCode;

void selectMins(HuffmanTree HT,int end, int *s1, int *s2)
{
    HTNode *minp1 = NULL;
    HTNode *minp2 = NULL;
    for (int i = 1; i <= end; i++) {
        HTNode *node = &HT[i];
        if(node->minFlag)
            continue;
        if(minp1 == NULL){
            minp1 = node;
            *s1 = i;
        }else{
            minp2 = node;
            *s2 = i;
            break;
        }
    }
    if(minp1->weight > minp2->weight)
    {
        HTNode* tmp = minp1;
        minp1 = minp2;
        minp2 = tmp;
        
        int tmpI = *s1;
        *s1 = *s2;
        *s2 = tmpI;
    }
    
    for (int i = 1; i <= end; ++i) {
        
        HTNode *node = &HT[i];
        if(node->minFlag)
            continue;
        if(node->weight < minp1->weight){
            minp1 = node;
            *s1 = i;
        }else if (node->weight < minp2->weight && node != minp1){
            minp2 = node;
            *s2 = i;
        }
    }
    minp1->minFlag = true;
    minp2->minFlag = true;
}

void HuffmanCoding(int *w, int n)
{
    if(n <= 1) return;
    int m = 2 * n - 1;
    HuffmanTree HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
    HuffmanTree p;
    int i, s1, s2;
    int *wp = w;
    for(p = HT + 1, i = 1; i<=n; ++i, ++p, ++wp)
    {
        p->weight = *wp;
        p->left = 0;
        p->right = 0;
        p->parent = 0;
        p->minFlag = false;
    }
    
    for (; i <= m; ++i, ++p) {
        p->weight = 0;
        p->left = 0;
        p->right = 0;
        p->parent = 0;
        p->minFlag = false;
    }
    
    for (i = n + 1; i <= m; ++i) {
        selectMins(HT, i-1, &s1, &s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].left = s1;
        HT[i].right = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        HT[i].minFlag = false;
    }
    
    for(int j = 1; j <= m; j++)
    {
        printf("w:%u, left:%u, right:%u, parent:%u\n", HT[j].weight,HT[j].left,HT[j].right,HT[j].parent);
    }
    HuffmanCode HC = (HuffmanCode)malloc((n+1)*sizeof(char*));
    char *cd = (char *)malloc(n * sizeof(char));
    cd[n-1] = '\0';
    int start , c, f;
    for (int i = 1; i <= n; ++i) {
        start = n - 1;
        for (c = i, f = HT[i].parent; f!=0; c = f, f = HT[f].parent)
        {
            if(HT[f].left == c) cd[--start] = '0';
            else cd[--start] = '1';
        }
        
        HC[i] = (char *)malloc((n - start) *sizeof(char));
        strcpy(HC[i], &cd[start]);
        printf("w:%u %s \n",w[i-1],HC[i]);
        free(HC[i]);
    }
    free(cd);
    free(HC);
}