哈夫曼树

组别：入门级
难度：4
OJ平台：LQ1009

当我们想传递一个字符串”shannon”从一台电脑到另一台电脑，我们需要对”shannon”的第一个字符做编码，转换成二进制传输，在四种编码中，只有a->000, h->001, n->1 , o->011, s->010这个编码方式所需要传输的量最小，这就是哈夫曼编码，如何寻找合适的哈夫曼编码就构建哈夫曼树。

哈夫曼（David Albert Huffman, 1925年8月9日 – 1999年10月7日）是一位美国计算机科学家，因其发明的哈夫曼编码（Huffman Coding）而闻名于世。

WPL (Weighted Path Length, 带权路径长度)

定义：

在一棵树中，带权路径长度是指从根节点到所有叶子节点的路径长度与对应叶子节点权值的乘积之和。
公式为：WPL=\(\sum_{i=1}^{n}w_il_i\)

其中：
n 是叶子节点的数量。
wi​ 是第 i个叶子节点的权值。
li是第 i 个叶子节点到根节点的路径长度。

WPL=4*2+1*3+2*3+3*2+7*1+5*1=35

哈夫曼树

哈夫曼树又称最优二叉树，给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度(WPL)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

例   有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树，第三个二叉树的WPL最小。要使二叉树WPL小,就须在构造树时, 将权值大的结点靠近根。

哈夫曼编码

哈夫曼编码是一种压缩编码的编码算法，是基于哈夫曼树的一种编码方式。哈夫曼树又称为带权路径长度最短的二叉树。

如何构建哈夫曼树及生成哈夫曼编码，是采用贪心策略。见图示。

注：哈夫曼树和哈夫曼编码不唯一，由于元素放左或放右的区别导致树的结构不同，但 WPL依然相同
N=2n-1, N为总结点数, n为叶子结点。

哈夫曼树

代码实现一：

 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
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-11 20:20
 * 最后修改: 2026-05-23 18:06
 * 文件描述: 生成 HuffmanTree，并输出每个字符的哈夫曼编码。
 * 核心算法: 使用优先队列反复合并当前权值最小的两个结点构造哈夫曼树。
****************************************************************/
#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct HuffmanTreeNode{
        char data;
        int  freq;
        HuffmanTreeNode* left;
        HuffmanTreeNode* right;

        HuffmanTreeNode(char c, int f) {
            data = c;
            freq = f;
            left = right = nullptr;
        }
};

struct Compare{
        bool operator()(HuffmanTreeNode* a, HuffmanTreeNode* b){
              return a->freq>b->freq;   // 让 priority_queue 按权值从小到大弹出
        }
};

void printCodes(HuffmanTreeNode* root, string path){
    if(!root) return;

    if(!root->left && !root->right){
        cout<<root->data<<" "<<path<<endl;
        return;
    }

    // 左边记 0，右边记 1，沿根到叶子的路径就是该字符的 Huffman 编码
    printCodes(root->left, path + "0");
    printCodes(root->right, path + "1");
}

void deleteTree(HuffmanTreeNode* root) {
    if (!root) return;
    // 后序删除，先删左右子树，再删当前结点
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

void HuffmanCodes(char data[], int freq[], int size){
    priority_queue<HuffmanTreeNode*,vector<HuffmanTreeNode*>,Compare> pq;

    for(int i=0; i<size;i++){
        // 每个字符先作为一棵只有一个结点的小树入队
        pq.push(new HuffmanTreeNode(data[i], freq[i]));
    }

    while(pq.size()!=1){
        // 每次取出当前权值最小的两棵树进行合并
        HuffmanTreeNode* left=pq.top();
        pq.pop();
        HuffmanTreeNode* right=pq.top();
        pq.pop();

        // '$' 只是内部结点的占位字符；该结点不代表原始字符，
        // 它的权值等于左右两棵子树根结点权值之和
        HuffmanTreeNode* node=new HuffmanTreeNode('$', left->freq + right->freq);
        node->left=left;
        node->right=right;
        pq.push(node);
    }

    // 队列中最后剩下的结点就是整棵 Huffman 树的根
    HuffmanTreeNode* root=pq.top();

    printCodes(root,"");
    deleteTree(root);
}



int main(){

    char data[]={'a', 'b', 'c', 'd', 'e', 'f','g','h'};
    int freq[]={5, 29, 7, 8, 14, 23, 3, 11};
    int size=sizeof(data)/sizeof(data[0]);

    HuffmanCodes(data, freq,size);

  
    return 0;
}

代码实现二：

 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
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-11 20:20
 * 最后修改: 2026-05-23 18:06
 * 文件描述: 生成 HuffmanTree，使用 pair 数据结构输入并输出哈夫曼编码。
 * 核心算法: 使用优先队列反复合并当前权值最小的两个结点构造哈夫曼树。
****************************************************************/
#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct HuffmanTreeNode{
    
        char data;
        int  freq;
        HuffmanTreeNode* left;
        HuffmanTreeNode* right;
     HuffmanTreeNode(char character,int frequency){
        data = character;
        freq = frequency;
        left = right = nullptr;
    }
};

struct Compare{
        bool operator()(HuffmanTreeNode* a, HuffmanTreeNode* b){
              return a->freq>b->freq;
        }
};

void printCodes(HuffmanTreeNode* root, string path){
    if(!root) return;

    if(!root->left && !root->right){
        cout<<root->data<<" "<<path<<endl;
        return;
    }

    printCodes(root->left, path + "0");
    printCodes(root->right, path + "1");
}

void deleteTree(HuffmanTreeNode* root) {
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

void HuffmanCodes(vector<pair<char,int>>  HuffTree, int size){
    priority_queue<HuffmanTreeNode*,vector<HuffmanTreeNode*>,Compare> pq;

    for(int i=0; i<size;i++){
        pq.push(new HuffmanTreeNode(HuffTree[i].first, HuffTree[i].second));
    }

    while(pq.size()!=1){
        HuffmanTreeNode* left=pq.top();
        pq.pop();
        HuffmanTreeNode* right=pq.top();
        pq.pop();

        HuffmanTreeNode* node=new HuffmanTreeNode('$', left->freq + right->freq);
        node->left=left;
        node->right=right;
        pq.push(node);
    }

    HuffmanTreeNode* root=pq.top();

    printCodes(root,"");
    deleteTree(root);
}



int main(){
    
    vector<pair<char,int> >  HuffTree={
    {'a', 5},
    {'b', 29},
    {'c', 7},
    {'d', 8},
    {'e', 14},
    {'f', 23},
    {'g', 3},
    {'h', 11}
};
    
    HuffmanCodes(HuffTree,HuffTree.size());

  
    return 0;
}

LQ1009

LQ1009
LQ1009_1
Quizzes
Previous Topic
Back to Lesson
Next Quiz