冷定理713:霍夫曼算法得到的带权w1W2,wn 的二分树是最优树 分析:采用归纳法。 ☆n=2, ∧入 结论成立 假设n=k-1结论成立。即用霍夫曼算法得到的带权 w1,w2,,wk-1的二分树是最优树。 对于n=k,用霍夫曼算法得到的带权w1,w2,wk的二分 树是最优树 由归纳假设,用霍夫曼算法得到的带权w1+w2,w3,,wvk 的二分树是最优树。 关键证明对于带权wl+w2,w3,,wk最优树,用子树代替 带权wl+w2的树叶,就是w1,w2,w3,,wk最优树❖ 定理7.13:霍夫曼算法得到的带权w1 ,w2 ,,wn 的二分树是最优树。 ❖ 分析:采用归纳法。 ❖ n=2, 结论成立 假设n=k-1,结论成立。即用霍夫曼算法得到的带权 w1,w2,,wk-1的二分树是最优树。 对于n=k，用霍夫曼算法得到的带权w1,w2,,wk的二分 树是最优树 由归纳假设，用霍夫曼算法得到的带权w1+w2,w3,,wk 的二分树是最优树。 关键证明对于带权w1+w2,w3,,wk最优树，用子树代替 带权w1+w2的树叶，就是w1,w2,w3,,wk最优树