哈夫曼树是一种带权路径最小的树，运用于压缩编码算法。

带权路径又称WPL，是所有非叶子节点的路径之和，路径=深度*权值

哈夫曼树的节点个数=2*带权节点个数-1

哈夫曼树的构造过程

在未组成哈夫曼树的节点中寻找权值最小和第二小的节点，作为左右孩子,构造一个新节点作为父节点，父节点的权值为左右孩子的权值之和

哈夫曼树的表示

哈夫曼树用顺序存储的数组表示。

存储结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct TreeNode
{
    int weight;
    int parent;
    int lchild;
    int rchild;
} TreeNode;

typedef struct HaffTree
{
    struct TreeNode *node;
    int length;
} HaffTree;

哈夫曼树的初始化操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
HaffTree *initTree(int *weight, int length)
{
    HaffTree *T = (HaffTree *)malloc(sizeof(HaffTree));
    T->node = (TreeNode *)malloc(sizeof(struct TreeNode) * (2 * length - 1));

    T->length = length;
    for (int i = 0; i < length; i++)
    {
        T->node[i].weight = weight[i];
        T->node[i].parent = -1;
        T->node[i].lchild = -1;
        T->node[i].rchild = -1;
    }
    return T;
}

上面我们已经说明哈夫曼树的节点树为带权节点个数*2-1，所以代码中我们申请了个数为为2 * length-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
25
26
27
28
29
30
31
32
33
int *findMinWeight(HaffTree *T)
{
    int min = 10000;
    int secmin = 10000;
    int minidx = -1;
    int secidx = -1;

    for (int i = 0; i < T->length; i++)
    {
        if (T->node[i].parent == -1)
        {
           if (T->node[i].weight < min)
            {
                secmin = min;            // 次小值变成最小值
                secidx=minidx;

                min = T->node[i].weight; // 最小值更新
                minidx = i;             //最小值索引更新
            }
            else if (T->node[i].weight < secmin)
            {
                secmin = T->node[i].weight;
                secidx = i;
            }
        }
    }
    
    int *arr = (int *)malloc(sizeof(int) * 2);
    arr[0] = minidx;
    arr[1] = secidx;
    return arr;
}

构建哈夫曼树的具体过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void buildHaffTree(HaffTree *T)
{
    int length = T->length * 2 -1;
    
    for (int i = T->length; i < length; i++)
    {
        int *res = findMinWeight(T);
        int lchild = res[0], rchild = res[1];
        /*新节点*/
        T->node[i].weight = T->node[lchild].weight + T->node[rchild].weight;
        T->node[i].lchild = lchild;
        T->node[i].rchild = rchild;
        T->node[i].parent = -1;

        /*设置父节点*/
        T->node[lchild].parent = i;
        T->node[rchild].parent = i;

        T->length++;
    }
    
}

完整代码

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

#define MAXNODE 1024;
typedef struct TreeNode
{
    int weight;
    int parent;
    int lchild;
    int rchild;
} TreeNode;

typedef struct HaffTree
{
    struct TreeNode *node;
    int length;
} HaffTree;


HaffTree *initTree(int *weight, int length)
{
    HaffTree *T = (HaffTree *)malloc(sizeof(HaffTree));
    T->node = (TreeNode *)malloc(sizeof(struct TreeNode) * (2 * length - 1));

    T->length = length;
    for (int i = 0; i < length; i++)
    {
        T->node[i].weight = weight[i];
        T->node[i].parent = -1;
        T->node[i].lchild = -1;
        T->node[i].rchild = -1;
    }
    return T;
}

int *findMinWeight(HaffTree *T)
{
    int min = 10000;
    int secmin = 10000;
    int minidx = -1;
    int secidx = -1;

    for (int i = 0; i < T->length; i++)
    {
        if (T->node[i].parent == -1)
        {
           if (T->node[i].weight < min)
            {
                secmin = min;            // 次小值变成最小值
                secidx=minidx;

                min = T->node[i].weight; // 最小值更新
                minidx = i;             //最小值索引更新
            }
            else if (T->node[i].weight < secmin)
            {
                secmin = T->node[i].weight;
                secidx = i;
            }
        }
    }
    
    int *arr = (int *)malloc(sizeof(int) * 2);
    arr[0] = minidx;
    arr[1] = secidx;
    return arr;
}


void buildHaffTree(HaffTree *T)
{
    int length = T->length * 2 -1;
    
    for (int i = T->length; i < length; i++)
    {
        int *res = findMinWeight(T);
        int lchild = res[0], rchild = res[1];
        /*新节点*/
        T->node[i].weight = T->node[lchild].weight + T->node[rchild].weight;
        T->node[i].lchild = lchild;
        T->node[i].rchild = rchild;
        T->node[i].parent = -1;

        /*设置父节点*/
        T->node[lchild].parent = i;
        T->node[rchild].parent = i;

        T->length++;
    }
    
}
void preOrder(HaffTree *T, int idx)
{
    if (idx != -1){
        printf("%d->", T->node[idx].weight);
        preOrder(T, T->node[idx].lchild);
        preOrder(T, T->node[idx].rchild);
    }
}


int WPL(HaffTree *T){
    int wpl=0;
    for(int i=0;i<T->length-1;i++){
       if(T->node[i].lchild==-1&&T->node[i].rchild==-1){
            int j=i;
            int depth=0;
            while(T->node[j].parent!=0){
                j=T->node[j].parent;
                depth++;
            }
            wpl+=depth*T->node[i].weight;
       }
    }
    return wpl;
}
void secOrder(HaffTree *T, int idx)
{
    if (idx <= -1)
        return;
    preOrder(T, T->node[idx].lchild);
    printf("%d->", T->node[idx].weight);
    preOrder(T, T->node[idx].rchild);
}
int main()
{
    int weight[] = {5, 1, 3, 6, 11, 2, 4};
    HaffTree *T = initTree(weight, 7);
    buildHaffTree(T);
    preOrder(T, T->length - 1);
    printf("wpl=%d\n",WPL(T));
    return 0;
}