数据结构中三叉树的霍夫曼算法
一个简单的算法
准备了n个初始霍夫曼树的集合，每个树都是一个叶子节点。将n棵树放在按权重（频率）组织的优先级队列中。
删除或删除前两棵树（重量最小的树）。合并这两个树以创建新树，其根与这两个树作为子树相关联，其权重是两个子树的权重之和。
将此新树放入优先级队列。
重复步骤2-3，直到和除非所有部分霍夫曼树都已合并为一棵。
这是一个贪婪算法：在每次迭代中，该算法都会创建一个“贪婪”决策，以合并权重最小的两个子树。算法是否可能给出期望的结果？
引理：设x和y为两个最低的频繁字符。有一个最佳代码树，其中x和y是同级树，与树中任何其他叶节点一样深度最小。
定理：霍夫曼码被视为最佳的无前缀二进制码（贪婪算法以给定字母集的最小外部路径权重构造霍夫曼树）。