本人看了许多数据结构的教材，也翻了一些参考书，发现上面都只是介绍它的构造方法，并没有给出它原理的严格论证，而恰恰哈夫曼树构造方法的数学推导更令人好奇和着迷，究竟是怎样的数学逻辑产生了计算机中这么个“树”？其实本质上这是一个组合极值的问题，某种程度上来说是一种离散量的动态变化，下面就给出严格的数学证明。
        中学竞赛不等式中有一种证明极值的有力方法，就是“调整法”，它的思想就是逐步逼近，我们就用这种办法来证明我们的问题，设t片叶分别带有权W1,W2,W3,...,Wt,定义二叉树的权为W(T)=∑Wi*L(vi),其中Vi是带权Wi的叶，L(vi)是叶Vi的路径长度，接下来我们就求W(T)的最小值。不失一般性，我们不妨设W1≤W2≤W3≤…..≤Wt，并且W1和W2的叶子是兄弟。先随意给出一棵符合条件的二叉树，再逐步把它调整到最佳，设S是分支点中路径最长的一点，假设S的儿子不是V1和V2,而是其他的Vx和Vy，那么L(Vx)≥L(V1),L(Vx)≥L(V2)，L(Vy)≥L(V1), L(Vy)≥L(V1),注意到Vx,Vy≥V1,V2，所以我们交换Vx和V1,Vy和V2,固定其他的量不变，则我们得到的二叉树的权值差为V1*L(Vx)+ V2*L(Vy)+ Vx*L(V1)+ Vy*L(V2)- V1*L(V1)- V2*L(V2)- Vx*L(Vx)- Vy*L(Vy)=(V1- Vx)*(L(Vx)- L(V1))+(V2-Vy)*(L(Vy)-L(V2))≤0，所以调整后权值减小，故S的儿子必定为v1和v2。
        下一步我们再用“降维递推”的思想来解决权最小问题，设Tx是带权W1,W2,W3,...,Wt的二叉树，在Tx中用一片叶子代替W1，W2这两片树叶和它们的双亲组成的子树，并对它赋权值为W1+W2，设Tx'表示带权W1+W2，W3，W4，...,Wt的二叉树，则显然有W(Tx)=W(Tx')+W1+W2，所以若Tx是最优树，则Tx'也是最优树，所以逐步往下调整可以把带有t个权的最优树简化到t-1个，再从t-1个简化到t-2个，...,最后降到带有2个权的最优树，所以哈弗曼树就这样出来了。这样就能很好地理解哈弗曼树的构造了。