构造哈夫曼树和对每个字符进行编码

必备知识

• 哈夫曼树也称为最优二叉树。
• 哈夫曼树并不唯一，但带权路径长度一定是相同的。
• 哈夫曼树中，左子树值必须小于右子树。

下面假设有八个概率数对应八个字母 0.19，0.21，0.02，0.03，0.06，0.07，0.10，0.32

构造思路和实现步骤

1. 从小到大排列权值(图中没有排列)�

   

2. 从19，21，2，3，6，7，10，32中选出权值最小的两个数据2，3，同时算出结点和为5。

   

3. 从19，21，6，7，10，32，5中选出权值最小的两个数据5，6，同时算出结点和为11。

   

4. 从19，21，7，10，32，11中选出权值最小的两个数据7，10。

由于这两个数字都不属于已经构造好的二叉树结点，所以需要重新开一个二叉树;如果两个数的和正好是下一步两个最小数的一个，那继续生长，否则并列生长。

5. 从19，21，32，11，17中选出权值最小的两个数据11，17，同时算出结点和为28。

   

6. 从19，21，32，28中选出权值最小的两个数据19，21，同时算出结点和为40。

   

7. 从32，28，40中选出权值最小的两个数据28，32，同时算出结点和为60。

   

8. 从40，60中选出权值最小的两个数据40，60，同时算出结点和为100。哈夫曼树构建完毕。

   

---

• 接下来我们在每根线上写上0或1，左子树写0右子树写1。那么ABCDEFGH对应的数值0.19，0.21，0.02，0.03，0.06，0.07，0.10，0.32进行哈夫曼编码后分别为：

- A(19):00
- B(21):01
- C(2):10000
- D(3):10001
- E(6):1001
- F(7):1010
- G(10):1011
- H(32):11

参考：

• CSDN博客：blog.csdn.net