36-算法设计

2.6.2　算法设计

哈夫曼编码的基本思想是以字符的使用频率作为权构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。构造一棵哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中的使用频率作为叶子结点的权值，以自底向上的方式，通过n−1次的“合并”运算后构造出的一棵树，核心思想是权值越大的叶子离根越近。

哈夫曼算法采取的 贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树 ，构造一棵新树，新树根节点的权值为其左右孩子结点权值之和，将新树插入到树的集合中，求解步骤如下。

（1）确定合适的数据结构。编写程序前需要考虑的情况有：

• 哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n−1个结点（n−1次的“合并”，每次产生一个新结点），
• 构成哈夫曼树后，为求编码，需从叶子结点出发走一条从叶子到根的路径。
• 译码需要从根出发走一条从根到叶子的路径，那么我们需要知道每个结点的权值、双亲、左孩子、右孩子和结点的信息。

（2）初始化。构造n棵结点为n个字符的单结点树集合T={t₁，t₂，t₃，…，t_n}，每棵树只有一个带权的根结点，权值为该字符的使用频率。

（3）如果T中只剩下一棵树，则哈夫曼树构造成功，跳到步骤（6）。否则，从集合T中取出没有双亲且权值最小的两棵树t_i和t_j，将它们合并成一棵新树z_k，新树的左孩子为t_i，右孩子为t_j，z_k的权值为t_i和t_j的权值之和。

（4）从集合T中删去t_i，t_j，加入z_k。

（5）重复以上（3）～（4）步。

（6）约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码，从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码。算法结束。