【数据结构】构造哈夫曼树

构造哈夫曼树的基本步骤:

1. 统计每个字符出现的频率,并存储在数组或List中。比如字符集{a, b, c, d, e},出现频率{5, 2, 3, 1, 4}。

2. 将频率当做权值,构造权值结点。比如{a:5, b:2, c:3, d:1, e:4}。

3. 选取两个权值最小的结点,构建一棵二叉树。二叉树的根结点权值是两结点权值之和,左子树是较小权值结点,右子树是较大权值结点。

4. 从未构造入树的权值结点中,再选取两个权值最小的结点构建一棵新的二叉树。

5. 重复步骤4,直到所有权值结点都构造入树为止。

6. 根据构造的完整二叉树,为每个叶子结点标注对应的字符,从根至叶,形成一套变长编码。

编码的长度越小的字符权值越大。所以哈夫曼编码是一种最优编码,能够让数据达到最小的压缩率。

以示例字符集为例,构造过程为:

1. 统计频率:{a:5, b:2, c:3, d:1, e:4}

2. 构造权值结点:{a:5, b:2, c:3, d:1, e:4}

3. 选取b:2和d:1构造一棵二叉树,根结点权值为3,左子树b,右子树d

4. 选取e:4和c:3构造一棵二叉树,根结点权值为7,左子树e,右子树c 

5. 选取a:5和上一步的根结点权值7构造一棵二叉树。

6. 标注叶子结点,形成编码,a:0, b:10, c:111, d:11, e:110。

以上就是构造哈夫曼树的基本过程,通过不断合并权值最小的两个结点,最终得到一个最优的编码方案。