Huffman树简单总结+代码(C/C++)

Huffman树,中文霍夫曼树或哈夫曼树,又称最优二叉树,是一种带权路径长最短的树。

  • Huffman树的构建思想:

1.从原始元素集合T中拿出两个频度最小的元素组成一个二叉树,二叉树的根为这两个节点频度的和。

2.然后从集合T中删除这两个元素,把根元素加入到T集合中,如此反复直集合T为空。

  • 构建此过程的数据结构:

1.优先级队列

2.顺序存储结构

3.二叉链表(本文所用)

  • 逐步分析:

1.Huffman树的结构(二叉链表表示):

1
2
3
4
5
6
typedef struct{
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;   //动态分配数组存储哈夫曼树
 
typedef char* HuffmanCode;   //动态分配数组存储哈夫曼编码表

2.SelectMin函数用于筛选最小的两个数,其中s1用于保存最小的,置于左孩子结点,s2保存第二小的,置于右孩子结点:

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
//选出weight最小的两个结点,s1保存最小的,s2保存第二小的
void SelectMin(HuffmanTree HT, int nNode)
{
    int i, j;
    for(i = 1; i <= nNode; i++)
        if(!HT[i].parent)
        {
            s1 = i;
            break;
        }
    for(j = i+1; j <= nNode; j++)
        if(!HT[j].parent)
        {
            s2 = j;
            break;
        }
 
    for(i = 1; i <= nNode; i++)
        if((HT[i].weight < HT[s1].weight) && (!HT[i].parent) && (s2 != i))
            s1 = i;
    for(j = 1; j <= nNode; j++)
        if((HT[j].weight < HT[s2].weight) && (!HT[j].parent) && (s1 != j))
            s2 = j;
    // 以上只筛选出最小的两个,这里保证s1的weight比s2的小
    if(HT[s1].weight > HT[s2].weight)
    {
        int tmp = s1;
        s1 = s2;
        s2 = tmp;
    }
}

3.最后的HaffmanCoding:

可以分为三部分,分别是Huffman树的初始化,创建,以及编码
代码里已经详细注释了:

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
105
// w[]存放nNode个字符的权值(均大于0),构造哈夫曼树HT,
// 并求出nNode个字符的哈夫曼编码HC
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode)
{
    int i, j;
    char *hfcode;
    int p;
    int cdlen;
    if(nNode < 1)
        return;
    m = 2*nNode-1;   //哈夫曼树的结点数
 
    /////////////////////////////以下是求Huffman树的初始化/////////////////////////////
    HT = (HTNode*) malloc ((m+1) *sizeof(HTNode));  //0号单元未用
    for(i = 1; i <= nNode; i++)    //初始化
    {
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for(i = nNode+1; i <= m; i++)
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
 
    puts("\n哈夫曼树的构造过程如下所示: ");
    printf("HT初态:\n 结点 weight parent lchild rchild");
    for(i = 1; i <= nNode; i++)
        printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
 
    printf("按任意键,继续...");
    getchar();
 
    /////////////////////////////以下是求Huffman树的构建/////////////////////////////
    for(i = nNode+1; i <= m; i++)
    {
        // 建立哈夫曼树
        // 在HT[1..i-1]中选择parent为0且weight最小的两个节点
        // 其序号分别是s1和s2
        SelectMin(HT, i-1);
        HT[s1].parent = i;
        HT[s2].parent = i;
        cout << "S1 && S2: " << HT[s1].weight << " " << HT[s2].weight << endl;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        printf("\nselect: s1 = %d s2 = %d\n", s1, s2);
        printf("结点 weight parent lchild rchild");
        for(j = 1; j <= i; j++)
            printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
        printf("按任意键,继续...");
        getchar();
    }
 
 
    /////////////////////////////以下是求Huffman树的编码/////////////////////////////
    // 可以看看算法导论上对于DFS求路径的方法,分三色:白,灰,黑,这里weight=0,1,2和那里思想是类似的
    // 可以拿7,5,2,4这组数据来模拟下面的过程,以求更简单理解
    // 从根出发
    //递归遍历哈夫曼树,求哈夫曼编码
    hfcode = (char *) malloc (nNode * sizeof(char));   //分配求编码的工作空间
    p = m;
    cdlen = 0;
    for(i = 1; i <= m; i++)
        HT[i].weight = 0;   //遍历哈夫曼树时用作结点状态的标志
 
    while(p)        //退出条件:p = 结点m的parent,即为0
    {
        if(HT[p].weight == 0)   //向左
        {
            HT[p].weight = 1;
            if(HT[p].lchild != 0)
            {
                p = HT[p].lchild;
                hfcode[cdlen++] = '0';
            }
            else if(HT[p].rchild == 0)
            {
                HC[p] = (char *) malloc ((cdlen+1) * sizeof(char));
                hfcode[cdlen] = '\0';   //保证后面的不会被复制
                strcpy(HC[p], hfcode);   //复制编码
            }
        }
        else if(HT[p].weight == 1)   //向右
        {
            HT[p].weight = 2;
            if(HT[p].rchild != 0)
            {
                p = HT[p].rchild;
                hfcode[cdlen++] = '1';
            }
        }
        else
        {
            // HT[p].weight == 2 退回到父结点,编码长度减一
            HT[p].weight = 0;
            p = HT[p].parent;
            --cdlen;
        }
    }
}
  • 完整代码:

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*
 * Tanky Woo
 * Blog: www.WuTianQi.com
 * Description: Huffman Tree
 * Date: 2011.12.3
*/
#include <iostream>
using namespace std;
 
int m, s1, s2; // m是总结点个数,s1,s2用于筛选出最小和第二小的两个数
 
typedef struct{
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;   //动态分配数组存储哈夫曼树
 
typedef char* HuffmanCode;   //动态分配数组存储哈夫曼编码表
 
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode);
 
int main()
{
    HuffmanTree HT;   // 哈夫曼树
    HuffmanCode *HC;  // 保存哈夫曼编码
    int *w, nNode, i; // w记录权值
    puts("输入结点数: ");
    scanf("%d", &nNode);
    HC = (HuffmanCode *) malloc (nNode* sizeof(HuffmanCode));
    w = (int *) malloc (nNode * sizeof(int));
    printf("输入 %d 个结点的权值\n", nNode);
    for(i = 0; i < nNode; i++)
        scanf("%d", &w[i]);
    HuffmanCoding(HT, HC, w, nNode);
    puts("\n各结点的哈夫曼编码:");   
    for(i = 1; i <= nNode; i++)
        printf("%2d(%4d):%s\n", i, w[i-1], HC[i]);
    getchar();
}
 
//选出weight最小的两个结点,s1保存最小的,s2保存第二小的
void SelectMin(HuffmanTree HT, int nNode)
{
    int i, j;
    for(i = 1; i <= nNode; i++)
        if(!HT[i].parent)
        {
            s1 = i;
            break;
        }
    for(j = i+1; j <= nNode; j++)
        if(!HT[j].parent)
        {
            s2 = j;
            break;
        }
 
    for(i = 1; i <= nNode; i++)
        if((HT[i].weight < HT[s1].weight) && (!HT[i].parent) && (s2 != i))
            s1 = i;
    for(j = 1; j <= nNode; j++)
        if((HT[j].weight < HT[s2].weight) && (!HT[j].parent) && (s1 != j))
            s2 = j;
    // 以上只筛选出最小的两个,这里保证s1的weight比s2的小
    if(HT[s1].weight > HT[s2].weight)
    {
        int tmp = s1;
        s1 = s2;
        s2 = tmp;
    }
}
 
// w[]存放nNode个字符的权值(均大于0),构造哈夫曼树HT,
// 并求出nNode个字符的哈夫曼编码HC
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode)
{
    int i, j;
    char *hfcode;
    int p;
    int cdlen;
    if(nNode < 1)
        return;
    m = 2*nNode-1;   //哈夫曼树的结点数
 
    /////////////////////////////以下是求Huffman树的初始化/////////////////////////////
    HT = (HTNode*) malloc ((m+1) *sizeof(HTNode));  //0号单元未用
    for(i = 1; i <= nNode; i++)    //初始化
    {
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for(i = nNode+1; i <= m; i++)
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
 
    puts("\n哈夫曼树的构造过程如下所示: ");
    printf("HT初态:\n 结点 weight parent lchild rchild");
    for(i = 1; i <= nNode; i++)
        printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
 
    printf("按任意键,继续...");
    getchar();
 
    /////////////////////////////以下是求Huffman树的构建/////////////////////////////
    for(i = nNode+1; i <= m; i++)
    {
        // 建立哈夫曼树
        // 在HT[1..i-1]中选择parent为0且weight最小的两个节点
        // 其序号分别是s1和s2
        SelectMin(HT, i-1);
        HT[s1].parent = i;
        HT[s2].parent = i;
        cout << "S1 && S2: " << HT[s1].weight << " " << HT[s2].weight << endl;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        printf("\nselect: s1 = %d s2 = %d\n", s1, s2);
        printf("结点 weight parent lchild rchild");
        for(j = 1; j <= i; j++)
            printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
        printf("按任意键,继续...");
        getchar();
    }
 
 
    /////////////////////////////以下是求Huffman树的编码/////////////////////////////
    // 可以看看算法导论上对于DFS求路径的方法,分三色:白,灰,黑,这里weight=0,1,2和那里思想是类似的
    // 可以拿7,5,2,4这组数据来模拟下面的过程,以求更简单理解
    // 从根出发
    //递归遍历哈夫曼树,求哈夫曼编码
    hfcode = (char *) malloc (nNode * sizeof(char));   //分配求编码的工作空间
    p = m;
    cdlen = 0;
    for(i = 1; i <= m; i++)
        HT[i].weight = 0;   //遍历哈夫曼树时用作结点状态的标志
 
    while(p)        //退出条件:p = 结点m的parent,即为0
    {
        if(HT[p].weight == 0)   //向左
        {
            HT[p].weight = 1;
            if(HT[p].lchild != 0)
            {
                p = HT[p].lchild;
                hfcode[cdlen++] = '0';
            }
            else if(HT[p].rchild == 0)
            {
                HC[p] = (char *) malloc ((cdlen+1) * sizeof(char));
                hfcode[cdlen] = '\0';   //保证后面的不会被复制
                strcpy(HC[p], hfcode);   //复制编码
            }
        }
        else if(HT[p].weight == 1)   //向右
        {
            HT[p].weight = 2;
            if(HT[p].rchild != 0)
            {
                p = HT[p].rchild;
                hfcode[cdlen++] = '1';
            }
        }
        else
        {
            // HT[p].weight == 2 退回到父结点,编码长度减一
            HT[p].weight = 0;
            p = HT[p].parent;
            --cdlen;
        }
    }
}

欢迎大家一起探讨。

  • 参考资料:

严蔚敏《数据结构》

最后给出一个题目:
http://acm.hdu.edu.cn/showproblem.php?pid=1053
HuffmanTree的题目,不过没用到求具体编码,所以相对要简单多了。
结题报告:

HDU/HDOJ 1053 Entropy (Huffman树)


http://www.cnblogs.com/Open_Source/archive/2010/07/10/1904936.html(STL优先级队列做法)

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《Huffman树简单总结+代码(C/C++)》有6个想法

  1. 你好,想请教几个问题。

    1. cout << "S1 && S2: " << HT[s1].weight << " " << HT[s2].weight << endl;
    这条语句不知道实现的是什么功能,而且cout和end在前文中也没有出现过。

    2. 为什么HT[p].weight == 0 向左,而等于1则向右呢?

    谢谢。

发表评论

电子邮件地址不会被公开。 必填项已用*标注