数据结构：哈夫曼树

树结构是一种应用非常广泛的结构，在一些特定的应用中，树具有一些特殊特点，利用这些特点可以解决很多工程问题。例如，我们今天要讨论的哈夫曼树，就是一种应用很广的树。

一、哈夫曼树的基本概念

哈夫曼（Huffman）树又称最优二叉树，它是一棵带权路径长度最小的二叉树。在哈夫曼树中，涉及路径、路径长度、权等概念，这些概念的具体含义如下：

路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分支数目称作路径长度。
树的路径长度：从树根到每一结点的路径长度之和。
权：赋给实体的一个量，是对实体的某个或某些属性的数值化描述。在数据结构中，实体有结点（元素）和边（关系）两大类，所以对应有结点权和边权。结点权或边权具体代表什么意义，由具体情况而定。如果一棵树中的结点有权值，则对应的就有带权树等概念。
结点的带权路径长度：从该结点到树根之间的路径长度与结点权值的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和。

假设有n个权值 $\{w_1,w_2,...,w_n\}$ ，构造一棵含n个叶子结点的二叉树，每个叶子结点的权为 $w_i$ ，其中带权路径长度（WPL）最小的二叉树就称作最优二叉树或哈夫曼树。如下图，有3棵二叉树，都含有4个叶子结点a、b、c、d，这4个叶子结点的权值分别为7、5、2、4。而这3棵二叉树的带权路径长度分别为36、46、35，其中树（c）的带权路径长度最小。可以验证，它恰为哈夫曼树，即其带权路径长度在所有权值为7、5、4、2的4个叶子结点的二叉树中居最小。

从这个例子，可以直观地发现，在哈夫曼树中，权值越大的结点离根结点越近。根据这个特点，哈夫曼最早给出了构造最优二叉树的算法，因此也被称为哈夫曼算法。

二、哈夫曼树的构造算法

2.1、构造过程

哈夫曼树的构造过程如下：

根据给定的n个权值 $\{w_1,w_2,...,w_n\}$ ，构造n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。
在森林F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左、右子树上根结点的权值之和。
在森林F中删除这两棵树，同时将新得到的二叉树加入F中。
重复第二步和第三步，直到F只含一棵树为止。这棵树便是哈夫曼树。

在构造哈夫曼树时，首先选择权小的，这样保证权大的离根较近，这样一来，在计算树的带权路径长度时，自然会得到最小带权路径长度，这种生成算法是一种典型的贪心法。如下图所示，为哈夫曼树的构造过程。

2.2、存储结构设计

哈夫曼树是一种二叉树，当然可以采用前面介绍过的通用存储方法。由于哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n−1个结点，可以存储在一个大小为2n−1的一维数组中。树中每个结点还要包含其双亲信息和孩子结点的信息，由此，每个结点的形式如下图所示。

在C语言中，哈夫曼树的存储结构的类型描述如下：

typedef struct {
    // 结点的权值
    int weight;
    // 结点的双亲、左孩子、右孩子的下标
    int parent, lchild, rchild;
}HTNode, *HuffmaTree;

哈夫曼树的各结点存储在由HuffmanTree定义的动态分配的数组中，为了实现方便，数组的0号单元不使用，从1号单元开始使用，所以数组的大小为2n。叶子结点集中存储在前面部分1～n个位置，而后面的n−1个位置存储其余非叶子结点。

2.3、算法步骤

哈夫曼树的构造算法的实现可以分成两大部分：

1）初始化。其步骤如下：

首先，动态申请2n个单元；
然后，循环2n-1次，从1号单元开始，依次将1至2n-1号单元中的双亲、左孩子、右孩子的下标都初始化为0；
最后，循环n次，输入前n个单元中叶子结点的权值。

2）创建树。通过n-1次的选择、删除与合并来创建哈夫曼树。其步骤如下：

选择，从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2；
删除，将结点s1和s2的双亲改为非0；
合并，将s1和s2的权值之和作为一个新结点的权值依次存入数组的n+1号及之后的单元中，同时记录这个新结点左孩子的下标为s1，右孩子的下标为s2。

2.4、算法描述

哈夫曼树的构造算法的实现，可以用如下C语言描述：

// 构造哈夫曼树HT，n是叶子结点的个数
void CreateHuffmanTree(HuffmanTree &HT, int n) {
    if(n<=1) return;

    // 哈夫曼树的结点数
    m=2*n-1;
    // 0号单元未使用，所以需要动态分配m+1个单元，HT[m]表示根结点
    HT=new HTNode[m+1];

    /* ---- 初始化 ---- */
    // 将1至m号单元中的双亲、左孩子、右孩子的下标都初始化为0
    for(i=1;i<=m;++i) {
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    //输入前n个单元中叶子结点的权值
    for(i=1;i<=n;++i) {
        cin>>HT[i].weight;
    }

    /* ---- 创建树 ---- */
    // 通过n-1次选择、删除、合并来创建哈夫曼树
    for(i=n+1;i<=m;++i) {
        // 选择。在HT[k]（1<=k<=i-1）中选择两个其双亲域为0且权值最小的结点，并返回它们在HT中的序号s1和s2
        Select(HT,i-1,s1,s2);
        // 删除。从森林中删除s1和s2，即将s1和s2的双亲域由0改为i
        HT[s1].parent=i;
        HT[s2].parent=i;
        // 合并。将i的权值设为s1和s2的权值之和，并将i的左右孩子分别设为s1和s2
        HT[i].weight=HT[s1].weight+HT[s2].weight;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
    }
}

哈夫曼树的一个典型应用是实现二进制编码。

三、哈夫曼编码

编码是指将数据转换成由二进制字符0、1组成的二进制串。反之，将二进制串转换成数据就是解码。哈夫曼树在数据通信、数据压缩等技术领域有着广泛的应用。

3.1、数据压缩问题

假设待压缩的数据为“abcdabcdaaaaabbbdd”，该数据中只包含a、b、c、d四种字符。现有如下编码方案：

方案（a）采用的是等长编码，用2位二进制码表示四种字符：a、b、c、d分别为00、01、10、11。上述待压缩数据为18个字符，其编码总长度为36位。但这并非最优的编码方案，因为每个字符出现的频率不同，如果在编码时考虑字符出现的频率，使频率高的字符采用尽可能短的编码，频率低的字符采用稍长的编码，来构造一种不等长编码，则会获得更好的空间效率，这也是文件压缩技术的核心思想。

方案（b）是一种不等长编，采用这种编码方案时，其编码总长度为35位。但对于不等长编码，如果设计得不合理，便会给解码带来困难。例如，方案（c）是另一种不等长编码方案，上述待压缩数据编码后为“00101111100101111100000010101111111”。但是，这样的编码数据无法翻译，比如，传送过去的字符串中前4个字符的子串“0010”就可有不同的译法，或是“aba”，或是“ac”。因此，若要设计长短不等的编码，必须满足一个条件：任何一个字符的编码都不是另一个字符的编码的前缀。显然，方案（b）所示的编码方案便满足这个条件。

那么如何设计有效的用于数据压缩的二进制编码呢？可使用哈夫曼编码。

3.2、基本概念

哈夫曼编码，是指利用哈夫曼树求得的二进制编码。

在进行数据压缩时，为了使压缩后的数据文件尽可能短，通常会采用不定长编码。其基本思想是：为出现次数较多的字符编以较短的编码。为确保对数据文件进行有效的压缩和对压缩文件进行正确的解码，可以利用哈夫曼树来设计二进制编码。如下图所示的哈夫曼树，约定左分支记为0，右分支记为1，则根结点到每个叶子结点路径上的0、1序列即为相应字符的编码。

在哈夫曼编码中，有两个重要的概念：

前缀编码：如果在一个编码方案中，任一个编码都不是其他任何编码的前缀（最左子串），则称编码是前缀编码。例如，编码0，10，110，111是前缀编码，而编码0，01，010，111就不是前缀编码。前缀编码可以保证对压缩文件进行解码时不产生二义性，确保正确解码。
哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。

3.3、算法实现

在构造哈夫曼树之后，求哈夫曼编码的主要思想是：依次以叶子为出发点，向上回溯至根结点为止。回溯时走左分支则生成代码0，走右分支则生成代码1。

由于每个哈夫曼编码是变长编码，因此使用一个指针数组来存放每个字符编码串的首地址。

各字符的哈夫曼编码存储在由HuffmanCode定义的动态分配的数组HC中，为了实现方便，数组的0号单元不使用，从1号单元开始使用，所以数组HC的大小为n+1，即编码表HC包括n+1行。但因为每个字符编码的长度事先不能确定，所以不能预先为每个字符分配大小合适的存储空间。为不浪费存储空间，动态分配一个长度为n（字符编码长度一定小于n）的一维数组cd，用来临时存放当前正在求解的第i（1≤i≤n）个字符的编码，当第i个字符的编码求解完毕后，根据数组cd的字符串长度分配HC[i]的空间，然后将数组cd中的编码复制到HC[i]中。

因为求解编码时是从哈夫曼树的叶子出发，向上回溯至根结点。所以对于每个字符，得到的编码顺序是从右向左的，故将编码向数组cd存放的顺序也是从后向前的，即每个字符的第1个编码存放在cd[n-2]中（cd[n-1]存放字符串结束标志’\0’），第2个编码存放在cd[n-3]中，依此类推，直到全部编码存放完毕。

根据哈夫曼树求哈夫曼编码的算法步骤为：

分配存储n个字符编码的编码表空间HC，其长度为n+1；分配临时存储每个字符编码的动态数组空间cd，cd[n-1]置为‘\0’。
逐个求解n个字符的编码。循环n次，执行以下操作：
- 设置变量start用于记录编码在cd中存放的位置，start初始时指向最后，即编码结束符的位置n-1；
- 设置变量c用于记录从叶子结点向上回溯至根结点所经过的结点下标，c初始时为当前待编码字符的下标i，f用于记录i的双亲结点的下标；
- 从叶子结点向上回溯至根结点，求得字符i的编码，当f没有到达根结点时，循环执行以下操作：
  - 回溯一次start向前指一个位置，即–start；
  - 若结点c是f的左孩子，则生成代码0，否则生成代码1，生成的代码0或1保存在cd[start]中；
  - 继续向上回溯，改变c和f的值。
- 根据数组cd的字符串长度为第i个字符编码分配空间HT[i]，然后将数组cd中的编码复制到HT[i]中。

相应的算法描述为：

// 从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) {
    // 分配存储n个字符编码的编码表空间
    HC=new char*[n+1];
    // 分配临时存放每个字符编码的动态数组空间
    cd=new char[n];
    // 编码结束符
    cd[n-1]='\0';

    // 逐个字符求哈夫曼编码
    for(i=1;i<=n;++i) {
        // start开始时指向最后，即编码结束符的位置
        start=n-1;
        // f指向结点c的双亲结点
        c=i;
        f=HT[i].parent;

        // 从叶子结点开始向上回溯，直到根结点
        while(f!=0) {
            // 每回溯一次start向前指一个位置
            --start;
            // 结点c是f的左孩子，则生成代码0，否则生成代码1
            if(HT[f].lchild==c) cd[start]='0';
            else cd[start]='1';
            // 继续向上回溯
            c=f;
            f=HT[f].parent;
        }

        // 为第i个字符的编码分配存储空间
        HC[i]=new char[n-start];
        // 将求得的编码从临时空间cd复制到HC的当前行中
        strcpy(HC[i], &cd[start]);
    }

    // 释放临时空间
    delete cd;
}