赫夫曼树

发表于   |   分类于

赫夫曼(Huffman)树, 又称最优树.

一. 基本概念

赫夫曼树又称最优树. 最优树是一类带权路径长度最短的树, 所有先要知道什么是最优树就要先知道什么是带权以及路径.

1. 路径

两个结点之间的距离称为路径, 可以看成是中间那条线.

2. 路径长度

树结点 A 的路径长度是从根结点到 A 的距离, 比如根节点的子节点的路径长度就是 1. (可以数从根节点到当前结点经过了几条线)

3. 树的路径长度

将所有叶子结点的路径长度相加就得到了树的路径长度.

4. 结点的权

“权”也就是权重, 表示结点的重要程度.

5. 带权路径长度

其实就是将权和路径长度相乘.

6. 树的带权路径长度

把所有叶子结点的带权路径长度加起来就是树的带权路径长度.

二. 什么是最优树

最优树就是带权路径长度最短的树.

问题: 指定 n 个结点, 如何构造出最优树呢?
已知带权路径长度是权值乘以路径长度, 那么理想状况是权值大的结点路径长度小一些, 这样得到带权路径长度的相对较小. (我瞎编的, 推导过程我没看懂)

赫夫曼树就是这种带权长度路径最小的树.

三. 赫夫曼树的作用

通过最优树可以知道赫夫曼树是带权长度路径最小的树, 那么赫夫曼树有什么用?(后面再谈论如何构造出一棵赫夫曼树)

1. 实际问题

假设一段文本要通过网络发送出去, 发送数据出去肯定是要转换成二进制码, 这里就产生了一个问题: 怎么编码呢?

2. 方法一

用固定长度来表示一个字符, 比如 00000001 表示字母 a, 00000010 表示字母 b…这种方式可行, 缺点是太长了, 我为什么不用 1 表示 a, 10 表示 b 呢?

3. 方法二

正因定长编码的缺点, 所以有了变长编码, 假设用 1 表示 a, 10 表示 b, 11 表示 c. 问题在于解码的时候遇到两个 1 怎么办? 这是两个 a 还是一个 c ?

4. 问题一

如何避免遇到两个 1 不知道是什么意思的情况 ?
只要保证一个字符的编码不是其他编码的前缀, 比如 a 的编码是 01, 那么就不存在以 01 开头的编码, 例如 0101 这种是不能存在的.

5. 问题二

既然使用变长编码, 不同字符的编码长度也就不一定相同, 那么那个字符的编码长度最短(编码自然是越短越好)?
答案是: 出现次数最多的那个字符, 出现次数越多的字符使用越短的编码, 就可以减少编码之后的总长度.

变长编码具有优势, 也具有两个问题, 而赫夫曼树就能完美解决这两个问题: 既可以保证一个字符的编码不是另一个字符编码的前缀, 又能保证出现次数最多的字符是使用最短的编码.

四. 如何构造赫夫曼树

这里先用人话说一遍:

1. 第一步

把给定权值的多个结点都看成是一棵二叉树, 组成森林 F

2. 第二步

找出 F 中根结点权值最小的两棵树.

3. 第三步

将这两棵树分别作为左子树和右子树, 创建一棵新的二叉树, 新的二叉树的根结点的权值就是左右子树权值之和. 将这棵新的树加入到 F 中去.

4. 第四步

重复第二, 第三步, 一直到 F 只有一棵树为止.

五. 赫夫曼树的存储结构

赫夫曼树是用一个结构体数组表示的, 每个数组元素存放一个结点, 结点包括左子树, 右子树, 双亲, 权重, 所以数据类型定义如下:

1
2
3
4
5
6
7
8
9
#define N 20  /*叶子结点的最大值*/
#define M 2*N-1  /*所有结点的最大值*/
typedef struct
{
    int weight;
    int parent;
    int LChild;
    int RChild;
}HuffmanTree[M+1];  /*HuffmanTree 是一个结构体数组类型, 0 号单元不用.*/

(二叉树有 n 个叶子结点, 那么总结点最多有 2*n-1 个结点)

六. 构造赫夫曼树

将自然语言转换成代码, 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void CrtHuffmanTree(HuffmanTree ht, int w[], int n)
{
    /*构造赫夫曼树 ht[M+1], w[] 存放 n 个权值. */
    for(i=1; i<=n; i++)
    {
        ht[i] = {w[i], 0, 0, 0};  /*1~n 号单元存放叶子结点, 初始化*/
    }
    for(i=n+1; i<2*n; i++)
    {
        ht[i] = {0, 0, 0, 0}  /*n+1~2*n-1 号单元存放非叶子结点, 初始化*/
    }

    //开始创建赫夫曼树
    for(i=n+1; i<2*n; i++)
    {
        //从 ht[1]~ht[i-1] 中选两个 parent 为 0 而且权值最小的两个数, 赋给 s1, s2
        select(ht, i-1, &s1, &s2);
        ht[i].weight = ht[s1].weight + ht[s2].weight;
        ht[i].LChild = s1;
        ht[i].RChild = s2;
        ht[s1].parent = i;
        ht[s2].parent = i;
    }/*赫夫曼树建立完毕*/
}

七. 完整代码

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
#include <stdio.h>

#define N 20  /*叶子结点的最大值*/
#define M 2*N-1  /*所有结点的最大值*/

typedef struct
{
    int weight;
    int parent;
    int LChild;
    int RChild;
}HuffmanTree[M+1];  /*HuffmanTree 是一个结构体数组类型, 0 号单元不用.*/

void select(HuffmanTree ht, int n, int * s1, int * s2);
void CrtHuffmanTree(HuffmanTree ht, int w[], int n);
void ScanW(int w[], int * n);
void PrintHuffmanTree(HuffmanTree ht, int n);

int main()
{
    HuffmanTree ht;
    int w[N], n;

    ScanW(w, &n);

    CrtHuffmanTree(ht, w, n);

    PrintHuffmanTree(ht, n);

    return 0;
}

void PrintHuffmanTree(HuffmanTree ht, int n)
{
    int i;
    printf("赫夫曼树如下: \n");
    for(i=1; i<2*n; i++)
    {
        printf("权重: %2d, 双亲: %2d, 左子树: %2d, 右子树 %2d .\n", ht[i].weight, ht[i].parent, ht[i].LChild, ht[i].RChild);
    }
}

void ScanW(int w[], int *n)
{
    int i;
    printf("请输入叶子结点的个数: \n");
    scanf("%d", n);
    printf("请输入各结点的权重: \n");
    for(i=0; i<(*n); i++)
    {
        scanf("%d", &w[i]);
    }
}

void select(HuffmanTree ht, int n, int * s1, int * s2)
{
    /*
        这个函数是为了找出 ht[1]~ht[n] 中 parent 等于 0, 而且最小的两个数, 同时保证 s1 小于 s2.
        思路: s2 等于第一个 parent 为 0 的数的下标, s1 等于第二个 parent 为 0 的下标, s1 往后找最小的数, s2 也往后找最小的数.
        这样就保证了 s2 和 s1 不会是同一个数. 最后保证 s1 对应的值 小于 s2对应的值.
    */
    int i, first, second, min;
    *s1 = 0;
    *s2 = 0;
    for(i=1; i<=n; i++)
    {
        if(ht[i].parent != 0)
        {
            continue;
        }
        else
        {
            first = i;
            break;
        }
    }
    *s2 = first;  /*确保它们不会指向同一个元素*/
    for(i=first+1; i<=n; i++)
    {
        if(ht[i].parent != 0)
        {
            continue;
        }
        else
        {
            second = i;
            break;
        }
    }
    *s1 = second;
    for(i=second+1; i<=n; i++)
    {
        if(ht[i].parent != 0)
        {
            continue;
        }
        else
        {
            if(ht[i].weight <= ht[*s1].weight)
            {
                *s1 = i;
            }
        }
    }
    for(i=first+1; i<=n; i++)
    {
        if(ht[i].parent != 0 || i == (*s1))
        {
            continue;
        }
        else
        {
            if(ht[i].weight <= ht[*s2].weight)
            {
                *s2 = i;
            }
        }
    }
    /*判断的是 ht[*s1].weight 和 ht[*s2].weight, 而不是 s1 和 s2*/
    if(ht[*s1].weight > ht[*s2].weight)
    {
        min = *s1;
        *s1 = *s2;
        *s2 = min;
    }
    printf("本次选出: %d %d\n", ht[*s1].weight, ht[*s2].weight);
}

void CrtHuffmanTree(HuffmanTree ht, int w[], int n)
{
    int i, s1, s2;
    /*构造赫夫曼树 ht[M+1], w[] 存放 n 个权值. */
    for(i=1; i<=n; i++)
    {
        /*1~n 号单元存放叶子结点, 初始化*/
        ht[i].weight = w[i-1];
        ht[i].parent = 0;
        ht[i].LChild = 0;
        ht[i].RChild = 0;
    }
    for(i=n+1; i<2*n; i++)
    {
        /*n+1~2*n-1 号单元存放非叶子结点, 初始化*/
        ht[i].weight = 0;
        ht[i].parent = 0;
        ht[i].LChild = 0;
        ht[i].RChild = 0;
    }

    //开始创建赫夫曼树
    for(i=n+1; i<2*n; i++)
    {
        //从 ht[1]~ht[i-1] 中选两个 parent 为 0 而且权值最小的两个数, 赋给 s1, s2
        select(ht, i-1, &s1, &s2);
        ht[i].weight = ht[s1].weight + ht[s2].weight;
        ht[i].LChild = s1;
        ht[i].RChild = s2;
        ht[s1].parent = i;
        ht[s2].parent = i;

    }/*赫夫曼树建立完毕*/
}