哈夫曼树的路径问题

给定一个数字或字符序列，构建哈夫曼树是非常简单易行的，只需要首先选择两个最小的元素做叶子结点，接着把它们的和与其他元素一起比较选择两个最小的元素结合在一起，直到所有元素都参与进来为止。
哈夫曼树所有的元素都在叶子结点上。

OK，构造树本身不难，但是有些问法就很有创意，比如下面这个：

（2015.3）下列选项给出的从根分别到两个叶子结点路径上的权值序列，能属于同一棵哈夫曼树的是：D.

A.24,10,5 和24,10,7
B. 24,10,5和24,12,7
C. 24,10,10和24,14,11
D. 24,10,5和24,14,6

分析：首先根据两个叶子，以及访问到叶子的前一个结点，这个结点一定是叶子的父亲结点。再根据哈夫曼树的结点一定有兄弟，即不存在度为1的结点。因此可以知道兄弟的权值，这样，给定的一个序列就可以推出两个叶子，两个序列推出四个叶子，这样就可以根据是否选择最小的两个叶子结点组合在一起作为判据，决定这个序列是否成立了。

我们一个一个来看。
首先看D.

首先由第一个序列的10，5可以推出另一个叶子也是5，它们的父亲是10。根据哈夫曼树子树权值和等于父结点权值的特点，我们知道里一个结点权值为14。

再看第二个序列，知道叶子结点6和父亲14，可以知道有个叶子兄弟是8，这个权值是14的结点有意思了，刚好可以和第一个结合成兄弟，且父亲为24，恰恰满足要求。

因此D是符合题目的树形。

再看C.

image.png

同样的分析思路再过一遍。
由第一个序列中的10，10可以得到有个叶子权值是0。第二个序列的14，11知道有个叶子是4.
OK，问题出来了，四个权值10，0，11，4是原始序列中的权值，按理说0，4最小，应该组合在一起，但是这里没有。所以是错误的树形。
当然需要明确的是，0和4不一定要组合在一起，要是序列中有1，那么0，1组合才是更小的。也就是说我们选择的是最小的，在不知道全局的情况下，局部的两个最小值最合理的是组合在一起。局部中不可能出现两个最小的分散的局面。这在哈夫曼树的构造中不可能出现的。

以上D,C从正反角度看了这种问题的解法。
同理B,A不再多说，给出图形如下：

B的树形：

image.png

如果24是第一个序列的，就不可能指到12，所以两个序列不是同一棵树的。

A也是同样的问题。
A的树形：

image.png

哈夫曼树总结：
定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
树的带权路径长度是指从根结点到所有叶结点所经过的边数乘以叶结点权值的和。

特点：

1. 没有度为1的结点，全是0或者2。
2. 两个子结点的权值的和等于父结点的权值
3. 权值最小的组合在一起

原文链接