怎么画出哈夫曼树

怎么画出哈夫曼树

在大学中学习计算机专业的 学生都会接触到 一种算法叫做哈夫曼树，在一些计算机等级认证中也会用到，很多人不会构造哈夫曼树，今天月下教给大家怎么构建(感谢网友的提醒 错误已经更正)

哈夫曼树，类似于算法中的二叉树，说白了哈夫曼树就是一种二叉树，只是是一种最优二叉树。我们准备一组数以 1，7，3，4，9，8为例子吧，请忽略12

第一步，我们对这一组数字进行排序。规则是从小到大排列。排列之后的顺序是 1，3，4，7，8，9，请忽略12

第二步就是 在这些数中 选择两个最小的数字（哈夫曼树是从下往上排列的）写在纸上。如下图所示

用一个类似于树杈的“树枝”连接上两个最小的数。在顶点处计算出这两个数字的和 并写在上面。然后再比较剩下的数字和这个和的大小，再取出两个最小的数字进行排列

如果两个数的和正好是下一步的两个最小数的其中的一个那么这个树直接往上生长就可以了。如果这两个数的和比较大不是下一步的两个最小数的其中一个那么，就并列生长，如下图所示

类似于步骤四。我们继续用倒V型的树杈，向上延伸。

算出来最后一个结果 就证明我们的哈夫曼树构建成功了。一个节点只能生出两个“枝桠”和数据结构中的“树”不同