2.2.3 哈夫曼编码算法实现

通过上一节的图解，相信大家对哈夫曼编码的构造已经有了了解，接下来我们就要进行实战编程。我们想要将字符串“i want to learn algorithm”进行哈夫曼编码以后，通过计算机发送，那么应该如何实现呢？完整代码如下。

哈夫曼编码算法程序运行结果如图2.13所示。

图2.13 哈夫曼编码算法程序运行结果

可以发现，程序的运行结果和分析结果是一致的。我们已经成功地将字符串“i want to learn algorithm”进行了哈夫曼编码。接下来我们对程序重要的数据结构和方法进行讲解。

下面我们定义一个哈夫曼结点类，该结点类包含如下信息：字符名字、字符频率、左子树、右子树，如下所示。

哈夫曼树的构造需要首先对字符频率进行排序，然后选取频率最低的两个字符构造子树，循环往复，最终剩下一个根结点。

生成哈夫曼树后，需要输出每个字符的结点，从根结点到叶子结点的路径就是该字符的编码，这是一个二叉树的遍历过程，如下所示。