哈夫曼树路径问题

哈夫曼树路径问题

哈夫曼树构造

哈夫曼树的构造并不难，无非就是从给定的权值集合中选择最小的结点作为子树（哈夫曼几叉树就选几个）先进来构造，然后将选择的结点之和添加到原集合，接着重复上述步骤即可。

最近遇到了一个很有意思的题目：
下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是 （） 。（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的结点，所以可以推算出其兄弟结点的权值。话不多说，一个个选项进行判断。

A选项中，A的树形状为：

根本无法构造成一个树，并且构造也错误并不是首先选择3和5两个结点构造。

B选项中也和A相似，树的形状为：

也无法构造成一个树

C选项中，树的形状为：

是一颗树了，不过，构造又出错了，真让人头大，为什么不让最小的两个顶点（0，3）在一起呢？真的是拆散了一对相亲相爱。

最后就是正确选项了，树的形状是：
你看这优美的树状，养眼的构造，真的是完美。

最后最后

废话就这样说完了，点个赞再走可好？