哈夫曼树小结

定义

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

哈夫曼树是带权路径最短的二叉树，权值较大的结点离根结点较近。

基本术语

路径和路径长度

路径：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路

路径长度：通路中分支的数目称为路径长度，若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1

结点的权及带权路径长度

结点的权：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积

树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径之和，记为 WPL。 $$ WPL = (W1 \times L1 + W2 \times L2 + ... + + Wn \times Ln) $$

N个权值Wi（i = 1，2...n）构成一棵有N个叶子结点的二叉树，相应的叶集结地的路径长度为Li（i = 1, 2...n）

构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点，n个权值分别为w1、w2、...、wn。

哈夫曼树的构造规则为：

将w1、w2、...、wn看成是有n棵树的森林（每棵树仅有一个结点）
在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左右子树结点权值之和
从森林中删除选取的两棵树，并将新树加入森林
重复2、3，直到森林中只剩一颗树为止，该树即为所求得的哈夫曼树

代码实现

设计哈夫曼树结点结构

typedef struct HaffNode{
    int weight;
    int flag;    /* 标记是否被加入到森林 */
    int parent;
    int leftChild;
    int rightChild;
}HaffNode, *HaffTree;

构建哈夫曼树

void createHaffTree(int weights[], int n, HaffTree haffTree) {
    /* 1. 初始化哈夫曼树 */
    int maxNodeCount = 2*n - 1;
    for (int i = 0; i < maxNodeCount; i++) {
        if (i < n) {
            haffTree[i].weight = weights[i];
        }else {
            haffTree[i].weight = 0;
        }
        haffTree[i].parent     = 0;
        haffTree[i].flag       = 0;
        haffTree[i].leftChild  = -1;
        haffTree[i].rightChild = -1;
    }
    
    /* 构建哈夫曼树n-1个非叶子结点 */
    int min1, min2;
    int x1, x2;
    for (int i = 0; i < n - 1; i++) {
        min1 = min2 = UINT16_MAX;
        x1 = x2 = 0;
        
        /* 找出森林中权值最小的2个结点 */
        for (int j = 0; j < n + i; j++) {
            if (haffTree[j].weight < min1 && haffTree[j].flag == 0) {
                min2 = min1;
                x2 = x1;
                min1 = haffTree[j].weight;
                x1 = j;
            }else if (haffTree[j].weight < min2 && haffTree[j].flag == 0) {
                min2 = haffTree[j].weight;
                x2 = j;
            }
        }
        
        /* 2个结点，合成一棵新树 */
        haffTree[x1].parent = n + i;
        haffTree[x2].parent = n + i;
        
        /* 将用过的结点标记为1，表示从森林中删除 */
        haffTree[x1].flag = 1;
        haffTree[x2].flag = 1;
        
        /* 修改新树的权值 */
        haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
        
        /* 修改新树的左右子树 */
        haffTree[n + i].leftChild = x1;
        haffTree[n + i].rightChild = x2;
    }
}

应用

哈夫曼树 —— 即最优二叉树，带权路径长度最小的二叉树，经常应用于书记压缩。

在计算机信息处理中，哈夫曼编码是一种一致性编码法（又称为“熵编码法”），用于数据的无损耗压缩

这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）

如图所示

7的编码为：0
5的编码为：10
2的编码为：110
4的编码为：111

哈夫曼编码的构造

哈夫曼编码结构设计

const int MaxBit = 4;

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

构造哈夫曼编码

流程：

创建一个临时结点code
循环n个结点
1. 将当前结点的权值，赋值给code，同时将start从0开始计数
2. 当前叶子结点i为孩子结点
3. 由叶子结点向上直到根结点遍历
  1. 如果当前叶子结点是左孩子，编码为0
  2. 如果当前叶子结点是右孩子，编码为1
4. 将临时code中计数、权值以及bit数组逆序存入哈夫曼编码数组中对应的位置

代码实现

void initHaffCode(HaffTree haffTree, int n, HaffCode codes[]) {
    HaffCode *code = malloc(sizeof(HaffCode));
    int child, parent;
    
    for (int i = 0; i < n; i++) {
        
        code->start = 0;
        
        code->weight = haffTree[i].weight;
        
        child = i;
        
        parent = haffTree[i].parent;
        
        while (parent != 0) {
            if (haffTree[parent].leftChild == child) {
                code->bit[code->start] = 0;
            }else code->bit[code->start] = 1;
            
            code->start++;
            
            child = parent;
            
            parent = haffTree[parent].parent;
        }
        
        int temp = 0;
        
        for (int j = code->start - 1; j >= 0; j--) {
            temp = code->start - j - 1;
            codes[i].bit[temp] = code->bit[j];
        }
        
        codes[i].start = code->start;
        codes[i].weight = code->weight;
    }
}

完整代码