哈夫曼树

2025-12-15 00:37:12

推荐回答（1个）

回答1：

编写哈夫曼树的意义是为了进行编码，如有一段话总共有四种字母（这里假设A B C D），出现次数是2 3 5 10，用01表示的话，正常情况，4个字符需要两位0,1来表示即可，A 00 B 01 C10 D11。那么总编码长度便是出现次数*长度2 = 40。
仔细观察发现，A 字符出现的次数2远远小于D 10，我们试想，出现次数少的编码短一些，出现次数多的编码长一些，是不是总编码会少一些呢？看如下
20
/ \
10 D10
/ \
5 C5
/ \
A2 B3
编码的默认方式，左子树0 右子树为1，如D，是右子树， C 先左再右， A左左左 B左左右
编码为 A 000 B001 C01 D1
总编码长度是 A出现的次数*A的编码长度 + B出现的次数*B的编码长度 + C出现的次数*C的编码长度+ D出现的次数*D的编码长度 = 2*3 +3*3 + 5*2 + 10 *1 = 35
编码长度短一些，这样就起到了压缩的目的。