哈夫曼树的实现

数据结构

哈夫曼树，又称带权路径长度最短的二叉树。那么什么是带权路径长度最短的二叉树呢？这里我引用维基百科的解释：哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明霍夫曼树的WPL是最小的。光看文字可能看不明白，接下来我们就用图来说明下。

huff1

上面这幅图中，a-g这几个字符是待编码的字符，而后面的数字是每个字符的权值。首先，我们在这7个字符中，挑选出两个最小的出来，分别是（b，3）和（e，9），这两个的权值相加的和构成一个新的节点，（b，3）和（e，9）分别是这个节点的左孩子和有孩子节点【在这里我们规定，先出现的字符在左，后出现的在右】，如下图所示

huff2

之后，这个新的节点插入到上面的序列中参与新的哈夫曼子树的构建，之后我们重复上面的一个步骤，不断找到两个最小权值且没有父节点的节点。就是这样的过程：

huff3

huff4

最后，我们将这两个子树合并，就这样，我们就完成了这个字符集的哈夫曼树的构建

huff5

那么现在我们来考虑代码实现了。在这我们在用静态数组实现这个哈夫曼树，而且是一个三叉链表的形式，在前面我们知道一个节点要知道它的左右子树信息，同时还要知道它的父节点信息。贴上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstring>

using namespace std;
#define MAX 10000

struct HuffTreeNode {
    char ch;
    int weight, parent, lchild, rchild;
};

struct HuffmanTree {
    HuffTreeNode *ht;       //静态哈夫曼树基地址指针
    int hsize;      //哈夫曼树的树节点个数
};

/**
 * 哈夫曼树的节点个数为树叶节点个数的2倍 - 1
 * @param Ht
 * @param n
 */
void InitHuffmanTree(HuffmanTree &Ht, int n) {
    Ht.ht = new HuffTreeNode[2 * n - 1];
    Ht.hsize = 2 * n - 1;
}

/**
 * 销毁哈夫曼树
 * 先删除哈夫曼树的静态树节点数组
 * 然后将哈夫曼树的大小赋值为0
 * @param Ht
 */
void DestoryHuffmanTree(HuffmanTree &Ht) {
    delete[] Ht.ht;
    Ht.hsize = 0;
}

/**
 * 在前i个节点中找出parent为0切权值最小的节点，获取其序号
 * @param Ht
 * @param i
 * @return
 */
int MinVal(HuffmanTree &Ht, int i) {
    int j, k, Min = MAX;
    for (j = 0; j < i; ++j) {
        if (Ht.ht[j].parent == -1 && Ht.ht[j].weight < Min) {
            Min = Ht.ht[j].weight;
            k = j;
        }
    }
    Ht.ht[k].parent = MAX;
    return k;
}

/**
 * 找出两个parent为其权值最小的两个节点构成一个哈夫曼树节点
 * 规定左子树的序号小于右子树的序号
 * @param Ht
 * @param i
 * @param s1
 * @param s2
 */
void Select(HuffmanTree &Ht, int i, int &s1, int &s2) {
    int s;
    s1 = MinVal(Ht, i);
    s2 = MinVal(Ht, i);
    if (s1 > s2) {
        s = s1;
        s1 = s2;
        s2 = s;
    }
}

/**
 * 创建哈夫曼树
 * @param Ht
 * @param n
 * @param ch
 * @param weight
 */
void CreateHuffmanTree(HuffmanTree &Ht, int n, char ch[], int weight[]) {
    int i, s1, s2;
    if (n > 1) {
        for (i = 0; i < n; i ++) {
            Ht.ht[i].ch = ch[i];
            Ht.ht[i].weight = weight[i];
            Ht.ht[i].parent = -1;
            Ht.ht[i].lchild = Ht.ht[i].rchild = -1;
        }
        for (; i < Ht.hsize; i ++) {
            Select(Ht, i, s1, s2);
            Ht.ht[s1].parent = Ht.ht[s2].parent = i;
            Ht.ht[i].lchild = s1;
            Ht.ht[i].rchild = s2;
            Ht.ht[i].weight = Ht.ht[s1].weight + Ht.ht[s2].weight;
            Ht.ht[i].parent = -1;
            Ht.ht[i].ch = '';
        }
    }
    std::cout << "哈夫曼树建立完毕" << std::endl;
}