1. 简介

1.1 概念

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

路径和路径长度： 在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的权及带权路径长度： 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度： 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

Huffman Tree.png

上图所示数的路径长度：sum = 1+2+2+3+3+1+2+2 = 16
B： 1 C：1
D： 2 F： 2
E： 2 G： 2
H： 3
I： 3
假设权重分别为 H: 5, I: 10,E: 20, F 25, G: 30
WPL = 5x3+10x3+20x2+25x2+30x2 = 195

1.2 思考

我们经常会遇到成绩排名的问题例如：

代码⽚片段:
if( score < 60)
result = “不不及格”;
else if(score < 70)
result = “及格”;
else if(score < 80)
result = “中等”;
else if(score < 90)
result = “良好”;
else
result = “优秀”;

score.png 成绩分布.png

---

由以上两图可以得知成绩⽐比重: 在70~89分之间占⽤用了了70% 但是都是需要经过3次判断才能得到正 确的结果. 那么如果数量量集⾮非常⼤大时,这样的⽐比较就会出现效率问题.

优化前.png
优化后.png

---

可以看出优化后的路径长度和WPL都有所减少，对于查找来说会更加快速。

根据给定的节点构建一个Huffman Tree

构建Huffman Tree.png

2. 哈夫曼编码

现有要传输的文字内容： BADCADFEED

如果每个字符对于的编码如下 ：

字符	A	B	C	D	E	F
编码	000	001	010	011	100	101
权重	27	8	15	15	30	5

则传输 BADCADFEED 的内容是：001 000 011 010 000 011 101 100 100 011

根据以上权重生成一棵Huffman Tree : 左孩子的边为0， 右侧为1，得出编码为：

字符	A	B	C	D	E	F
编码	01	1001	101	00	11	1000

image.png

则传输 BADCADFEED 的内容变为：1001 01 00 101 01 00 1001 11 11 00，减少了5个字符，从而对传输内容进行了压缩。

3. 哈夫曼算法的实现

实现代码：

#include "string.h"
#include "stdio.h"
#include "stdlib.h"

const int MaxValue = 10000;//初始设定的权值最大值
const int MaxBit = 4;//初始设定的最大编码位数
const int MaxN = 10;//初始设定的最大结点个数

typedef struct HaffNode{// Huffman Tree 节点
    int weight;
    int flag;//1以及加入Huffman Tree 0没加入
    int parent;
    int leftChild;
    int rightChild;
}HaffNode;

typedef struct Code//存放哈夫曼编码的数据元素结构
{
    int bit[MaxBit];//数组
    int start;  //编码的起始下标
    int weight;//字符的权值
}Code;


/// 创建一个Huffman Tree
/// @param weight 权重数组
/// @param n 个数
/// @param T 树
void createHuffmanTree(int weight[], int n, HaffNode * T) {
    
    // 定义变量
    int j,m1,m2,x1,x2;
    // 初始化（顺序存储）一棵二叉树，n个叶子节点的二叉树共有2*n-1个节点
    for (int i = 0; i < 2*n-1; i++) {
        if (i<n) {
            // 叶子节点赋值权重
            T[i].weight = weight[i];
        } else {
            // 非叶子节点权重赋值为0
            T[i].weight = 0;
        }
        
        // 暂时还不知道父节点孩子节点，所有节点均未加入Huffman Tree
        T[i].parent = 0;
        T[i].flag = 0;
        T[i].leftChild = 0;
        T[i].rightChild = 0;
    }
    
    // 循环构造Huffman Tree 的其他n-1个非叶子节点
    for (int i = 0; i < n - 1; i++) {
        m1 = m2 = MaxValue;
        x1 = x2 = 0;
        
        for (j = 0; j < n+i; j++) { // 循环找出所有权重中，最小的两个值
            if (T[j].weight < m1 && T[j].flag == 0) {// 找出第一个值最小的及其位置
                m2 = m1;
                x2 = x1;
                m1 = T[j].weight;
                x1 = j;
            } else if(T[j].weight < m2 && T[j].flag == 0){// 找出第二个值最小的及其位置
                m2 = T[j].weight;
                x2 = j;
            }
        }
        /*
         1. 将上面循环找出的最小的两个值生成一棵子树
         2. 顺序存储的前n个已经存储了叶子节点
         3. 从第n+0开始存储第一棵子树的根节点
         */
        T[x1].parent = n + i;
        T[x2].parent = n + i;
        // 标记已经加入Huffman Tree
        T[x1].flag = 1;
        T[x2].flag = 1;
        // 修改第n+i个节点的权重
        T[n+i].weight = T[x1].weight + T[x2].weight;
        // 修改第n+i个节点的孩子的值
        T[n+i].leftChild = x1;
        T[n+i].rightChild = x2;
    }
}

// Huffman 编码
void HaffmanCode(HaffNode T[], int n, Code code[]) {
    // 创建一个编码节点
    Code *c = (Code *)malloc(sizeof(Code));
    // 临时变量
    int child, parent;
    
    for (int i = 0; i < n; i++) {
        // 从0开始计数
        c->start = 0;
        // 取得编码对应的权重值的字符
        c->weight = T[i].weight;
        // 孩子节点
        child = i;
        // 父节点
        parent = T[child].parent;
        // 由叶子节点一直向上找，直到根
        while (parent != 0) {
            if (T[parent].leftChild == child) {
                c->bit[c->start] = 0;//左侧为0
            } else {
                c->bit[c->start] = 1;//右侧为1
            }
            // 起始位置自增
            c->start++;
            // 当前双亲节点成为孩子节点
            child = parent;
            // 赋值新的父节点
            parent = T[child].parent;
        }
        
        int temp = 0;
        // start 先加一，所以j要减一，直到0 ，翻转当前节点的编码，因为是从叶子节点开始遍历的
        for (int j = c->start - 1; j >= 0; j--) {
            temp = c->start-j-1;
            code[i].bit[temp] = c->bit[j];
        }
        // 把临时变量里面的数据保存到code中
        code[i].start = c->start;
        code[i].weight = c->weight;
    }
    
}



int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    int i, j, n = 4, m = 0;
    
    //权值
    int weight[] = {2,4,5,7};
    
    //初始化哈夫曼树, 哈夫曼编码
    HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1);
    Code *myHaffCode = malloc(sizeof(Code)*n);
    
    //当前n > MaxN,表示超界. 无法处理.
    if (n>MaxN) {
        printf("定义的n越界，修改MaxN!");
        exit(0);
    }
    
    //1. 构建哈夫曼树
    createHuffmanTree(weight, n, myHaffTree);
    //2.根据哈夫曼树得到哈夫曼编码
    HaffmanCode(myHaffTree, n, myHaffCode);
    //3.打印
    for (i = 0; i<n; i++)
    {
        printf("Weight = %d\n",myHaffCode[i].weight);
        for (j = 0; j<myHaffCode[i].start; j++)
            printf("%d",myHaffCode[i].bit[j]);
        m = m + myHaffCode[i].weight*myHaffCode[i].start;
         printf("\n");
    }
    printf("Huffman's WPS is:%d\n",m);
    return 0;
}