哈夫曼树

一. 目的：找出存放一串字符所需的最少的二进制编码

二.  原理：首先统计出每种字符出现的频率！（也可以是概率）//权值

------------------------------------------------------------------------------------------------

           例如：频率表 A：60,    B:45,   C:13   D:69   E:14   F:5  G:3

第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在频率表中删除此次找到的两个数，并加入此次最小两个数的频率和。

F和G最小，因此如图，从字符串频率计数中删除F与G，并返回G与F的和 8给频率表

 重复第一步：

-------------------------------------------------------------------------------------------------

频率表 A：60,    B:45,   C:13   D:69   E:14   FG:8

最小的是 FG：8与C：13，因此如图，并返回FGC的和：21给频率表。

---------------------------------------------------------------------------------------------------

重复第一步：

---------------------------------------------------------------------------------------------------

频率表 A：60    B: 45   D: 69   E: 14   FGC: 21

如图

-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 A：60    B: 45   D: 69  FGCE: 35

-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 A：60   D: 69  FGCEB: 80

-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 AD：129  FGCEB: 80

添加 0 和 1，规则左0 右1

 

频率表 A：60,    B:45,   C:13   D:69   E:14   F:5  G:3

每个 字符 的 二进制编码 为

A：10

B：01

C：0011

D：11

E：000

F：00101

G：00100