证明:采用归纳法。 ☆n=2, ∧入 结论成立 假设n=k-1结论成立。即用霍夫曼算法得到的带 权w1,w2,,wk1的二分树是最优树。 对于n=k,由归纳假设,用霍夫曼算法得到的带 权w1w2,w3,,wk的二分树是最优树。 由引理2得:对于带权wl+w2,w3,,wk最优树 用子树代替带权w+w的树叶,就是w1,w2,w3, ,wk最优树❖ 证明:采用归纳法。 ❖ n=2, 结论成立 假设n=k-1,结论成立。即用霍夫曼算法得到的带 权w1,w2,,wk-1的二分树是最优树。 对于n=k，由归纳假设，用霍夫曼算法得到的带 权w1+w2,w3,,wk的二分树是最优树。 由引理2得：对于带权w1+w2,w3,,wk最优树， 用子树代替带权w1+w2的树叶，就是w1,w2,w3, ,wk最优树