设我们已经构造出来了最优树\(T_n\)，他的叶子节点分别是\(w_1≤w_2...≤w_n\)
假设\(T_n\)的最长的一条路的倒数第二个节点（即这条路叶子节点的父亲）\(x\)只有一个儿子，那么我们删掉这个节点\(x\)，让他的儿子代替他，答案会变得更优，矛盾，所以\(x\)一定有两个儿子。我们假设这两个儿子不全为\(w_1\)和\(w_2\)，即有一个儿子\(w_y\)且\(w_y≥w_2\)，那我们将\(w_y\)与不在这里的\(w_1\)和\(w_2\)交换，答案不会变得更差，即一定可以构造出来一个最优树\(T_n\)，使得\(x\)的两个儿子为\(w_1\)和\(w_2\)
我们在考虑收缩与展开。
假设\(T_n\)的\(w_1\)和\(w_2\)合并成了一个节点（具体来说，令\(w_1\)和\(w_2\)的父亲节点的权值为\(w_1+w_2\)，然后删掉\(w_1\)和\(w_2\)）,这颗新树为\(T_{n-1}^*\)，那么\(V(T_{n-1}^*)=V(T_n)-w_1-w_2\)
同时，考虑点集\(\{w_3,w_4...w_n,w_1+w_2\}\)的最优树为\(T_{n-1}\)，找到这个最优树权值为\(w_1+w_2\)的叶子节点，并将其展开（就是上面合并过程的逆过程），设得到的新树为\(T_n^*\)，则有\(V(T_{n}^*)=V(T_{n-1})+w_1+w_2\)
那么我们把得到的两个式子相加，有\(V(T_{n-1}^*)-V(T_{n-1})+V(T_{n}^*)-V(T_n)=0\)，由于\(T_{n-1}和T_n\)都是最优的，那么必须有\(V(T_{n-1}^*)=V(T_{n-1})\)和\(V(T_{n}^*)=V(T_n)\)，即合并和展开后仍然是最优树
接下来考虑求\(T_n\)，我们要求\(T_n\)，如果能够将最小权值的两个节点合并并求出\(T_{n-1}\)，那么就可以知道\(T_{n}\)，然后一直递归下去，最后合并只剩一个节点即可
标签：哈夫曼,合并,构造,儿子,最优,证明,节点 From： https://www.cnblogs.com/dingxingdi/p/17892230.html