🏷️ 知识点：带权路径长度
已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度最小是（ ）。
A.27
B.46
C.54
D.56
[tag_link] 正确答案：B将 哈夫曼树 的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为 0 的虚叶结点，对于严格的三叉树(n0−1)%(3−1)=u=1\=0，需要添加m−u−1=3−1−1个叶结点，说明 7 个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则，权为 0 的叶结点应离树根最远构造最小带权生成树的过程如下：最小的带权路径长度为(2+3)×3+(4+5)×2+(6+7)×1=46。
若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是（ ）。
A. 89 B. 200 C. 208 D. 289
[tag_link]
正确答案：B
根据 Huffman 构建过程 来构建得到如下二叉树：
89
/ \
52 37
/ \ / \
22 30 16 21
/ \
10 12
带权路径长度 为：(10+12)×3+(30+16+21)×2=200
(10分)二叉树的带权路径长度( WPL) 是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉 树T, 采用二叉链表存储，结点结构为：
| left | weight | right |
|---|
其中叶结点的weight 域保存该结点的非负权值。设root为指向T 的根结点的指针，请设计求T的 WPL 的算法，要求：
(1)给出算法的基本设计思想；
(2)使用C 或 C++语言，给出二叉树结点的数据类型定义；
(3)根据设计思想，采用C 或 C++语言描述算法，关键之处给出注释。
[tag_link]
算法的基本设计思想： ①基于先序递归遍历的算法思想是用一个 static 变量记录 wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下： 若该结点是叶子结点，则变量 wpl 加上该结点的深度与权值之积； 若该结点非叶子结点，则若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加 1； 最后返回计算出的 wpl 即可。 ② 若考生给出能够满足题目要求的其他算法且正确，可同样给分。 ②考生答案无论使用 C 或者 C++ 语言，只要答案正确同样给分。 ③ 的标准给分。 ④若考生给出的二叉树结点的数据类型定义和算法实现中，使用的是除整型之外的其他数值，可视同使用整型类型。 ⑤若考生给出的答案中算法主要设计思想或算法中部分正确，可酌情给分。