哈尔滨工程大学计算机院考研专业课题型讲解第三篇——画哈夫曼树

求哈夫曼树

期末题一：
假设字符a、b、c、d、e、f的应用频率分别是0.07、0.09、0.12、0.22、0.23、0.27，请画出相应的编码哈夫曼树，并求其哈夫曼编码。

求哈夫曼编码就是每次选择最小的两个数字作为左右子树，加起来的为父节点，加起来的数字也算一个数字放进候选列表。再选择其中最小的两个加起来。
比如第一步是选择7和9，加起来是16。此时候选列表为{12，16，22，23，27}
选择12和16，加起来为28。此时候选列表为{22，23，27，28}
选择22和23，加起来为45。此时候选列表为{27，28，45}
选择27和28，加起来为55。最后将45和55加起来，完成。
画完哈夫曼树后进行编码，左侧方向均为0，右侧方向均为1。比如f是从根节点向左走了两步到的，编码为00。c是左右左，即010。以此类推。