26考研408真题,数据结构部分:哈夫曼树带权路径最短

大家好，我是「阑梦清川」

今天浅浅地看一道题目。因为这道题其实不是很难，我也不会写很多笔记，就简单地谈一谈。

这道题是考研数据结构中关于**"带权路径长度最小"「的第五题。实际上我看到这个题目时，想到的就是」哈夫曼树（Huffman Tree）**。我是软件工程专业的，我们专业有一门课叫《离散数学》，在那门课上我们就学习过哈夫曼树。虽然当时还没学数据结构，但后来学到这里时，离散数学的知识还是发挥了作用。

在离散数学课上，老师会给一堆节点，让我们构建哈夫曼树并写出相关序列，本质上和数据结构这门课没有太大差别。这道题要求的是**"带权路径长度最小时，与节点 E 相同深度的节点"**，实际上也需要构建哈夫曼树。题目给定了一些二叉树节点，我们要做的就是利用这些节点构建哈夫曼树。如果你学过离散数学，即使没上过数据结构专业课，只要掌握了带权路径长度相关的知识，也是可以解决这个题目的。

这道题的具体做法是：

1. 「将二叉树节点权值按照从小到大的顺序排列」。
2. 发现题目给出的数据本身就是排好序的，所以可以直接开始求解。
3. 「选取两个最小的权值组成一棵二叉树」。也就是 1 和 2 组成一棵树，相加之和等于 3。
4. 「去掉原序列中的 A 和 B，将和加入到序列中重新排序，再次选择两个最小的，以此类推」。

具体过程如下：

1. 3 加入后，3 和 4 是最小的，相加等于 7，组成一棵新树。
2. 把 7 加入序列重新排列，此时序列为：5, 7, 8, 10, 12。
3. 5 和 7 是最小的，组成 12。
4. 把 12 放回去，序列变为：8, 10, 12, 12。
5. 继续对这四个数据重新排列，选择最小的两个继续构建。

构建二叉树时「具体的摆放方式」，决定了我们最终能否找出与节点 E 相同深度的节点。下面我通过白板大致画一下这个过程，帮助大家理解。

首先是把 1 和 2 组成 3，然后把 3 放到序列里面去，如下所示：

然后将3和4组成7，把7放到序列里面继续填充这个二叉树。

遵循**"小的在左边，大的在右边"**的原则：

1. 3在左边，4在右边，组成一个新的二叉树
2. 把3的左节点和右节点继续原封不动地画上去就可以了

然后，5 和 7 组成了 12，把 12 加到序列中。

在 Huffman 树（原流）的上一步二叉树基础上，因为 5 比 7 小，所以 5 在左边，7 在右边，组成了 12。至于 7 下面的部分，直接把上面的内容原封不动地挪下来就可以了。

接下来你会发现，最小的数字是 10 和 8。

10 和 8 组成了 18，所以这个时候需要重新构建一棵二叉树，并将 18 添加到序列中。此时序列中包含两棵二叉树，剩下的三个数值分别是 12、12 和 18。

如下所示：

接下来是最小的两个数，也就是 12 和 12。由这两个 12 组合成 24。

现在剩下最后两个数：18 和 24。将 18 放在左边，24 放在右边。到此为止，这个二叉树（也就是哈夫曼树）就完整地构建出来了。

这个时候再回到题目要求：寻找与"8"位于同一层的节点。

非常显然，8 应该处于第三层。各层结构如下：

1. 第二层是 18 和 24
2. 「第三层是 8、10、12 和 12」

但是，第三个 12（也就是 24 的左节点那个 12）显然是由 5 和 7 构建出来的，「所以它并不在我们原始的序列中」。

「在我们的原始序列里，与 8 在同一层的节点就是 10 和 12」。因此，对应的选项答案就显而易见了。

我是「阑梦清川」，希望得到您的关注