榆木盖饭的个人空间

哈夫曼编码1.树的带权路径长度：只关心叶子节点的权值， 2 * 1 + 2 * 2 + 3 * 1 = 9； 2.哈夫曼树：带权路径长度最小的二叉树， 3.哈夫曼算法：构建哈夫曼树，根据贪心策略得到 初始化： 把所有叶子节点都看成一棵树 贪心：每次选择权值最小的合并新的二叉树（权值小的放地深），新树的根节点再放回去选择 重复 4.在构造的过程中就可以计算出带权路径长度，每次合并都把左右子树的权值累加起来， 二 ： 证明 ： 引理：n个叶子节点，权值最小的，一定在深度最深的地方，并且可以调整成兄弟（先证明引理，反证法） ​ 如果最小的不在最深，可以交换，一定更优。 因为最小的都在最深，所以计算的路径长度都一样，所以可以随便调整 ​ 有了引理，就可以每次都挑最小的了 有了引理，再用数学归纳法：先假设一个较小的树成立，再假设 n = k 的时候成立，再证明 n = k + 1 的时候成立。 当 n = k + 1 的时候，可以挑出权值最小的两个合并，然后 n = k 了。我们假设成立。 三：哈夫曼编码 编码的方式有很多，...