我要招人

去企业版

首页 > 试题广场 >

已知三叉树T 中 6 个叶结点的权分别是 2，3，4，5，6

[单选题]

已知三叉树T中6个叶结点的权分别是 2, 3, 4, 5, 6, 7，T 的带权（外部）路径长度最小是（）

```
27
```
```
46
```
```
54
```
```
56
```

查看正确选项

InGodWeTrust

开始做错了，后来算算确实是46

发表于 2017-04-09 16:12:29 回复(0)

Sunny_ivy

(2+3)*3+(4+5)*2+6+7=46

发表于 2016-11-27 16:37:42 回复(5)

我不是匠人

m表示节点个数

k表示K叉树

若（m-1）%(k-1) = 0说明不需要虚段，否则需要（K-1）-（m-1）%(k-1)个虚段。

本题m=6,k=3。

则（6-1）%（3-1）=1

需要虚段 2 - 1 = 1添加的虚段可视为0。然后按照优先取最小的三个的原则，构造三叉树。

结果为5+14+27=46.

发表于 2017-01-10 23:33:49 回复(7)

philian

我本以为是Huffman编码算法的变种，但是没那么简单…因为这里是三叉树，所以每次可以选2个或者3个节点，为使总的带权路径最短，应尽可能把权值大的元素都置于上层，也就是说上层应选择3作为分支数，然后依次向下层转移。

发表于 2016-12-16 12:05:19 回复(3)

葬爱家族小鑫鑫

这是我第二次做错了，简直无语。

简单点来说就是补齐需要的0，然后按照二叉树的样子计算就好了。

发表于 2019-04-08 20:23:42 回复(0)

为你扣下F键

我觉得理论上应当是模拟霍夫曼最优二叉树的编码方法，考虑到最后一步编码应当是三个元素一起编码，因此编码开始之前在最底层添加一个权为"0"的节点，从下至上以三元组编码，最后可得该最优三叉树。如答友所画。[复制别人的，做笔记]

发表于 2018-08-13 20:41:57 回复(1)

MnM~

哈夫曼树是严格二叉树，只有度为0和2的节点。所以，满足的关系。对节点度为下标n0，n2。 2*n2 =n0+n2-1 n2=n0-1 我们知道n0为整数，所以可以直接求n2. 而严格k叉树，只有度为k和0的节点。 n0.nk k* nk＝nk+n0-1 nk=（n0-1）/（k-1）通过调整n0的值使nk取整。调整的增加的n0的值就是需要补充的0节点的个数。然后借助0节点的个数进行类似二差哈夫曼树的构造。这里，k＝3，n0=6 nk等于=（6-1）/（3-1）=5/2 所以，5+1 增加一个权重为0的节点。

发表于 2022-04-12 20:37:54 回复(0)

haichuangxia

带权路径最小的n叉树,理论上只有叶子节点和度为n的节点,此处三叉树,则N₃+N0-1=3N₃,即N₃= $\frac{1}{2}\times(N_0-1)$

因此,节点数需要是奇数,而此处只有6个,因此需要再加一个权值为0的节点.

因此,需要对权值为0,2,3,4,5,6,7的7个节点构造类哈夫曼树.

发表于 2021-11-23 16:06:55 回复(0)

_no_name

这道题的考点是哈夫曼树的一个性质：权值越大的结点距离根节点越近。

所以只要从上往下，按三叉树的样式先把数值大的结点排好，就可以了。

发表于 2019-11-01 14:54:02 回复(0)

NG14

我自己画画画就画出来了，谁能告诉我个正规的方法啊~

发表于 2016-12-04 20:11:10 回复(0)

格物方能致知

这题就看节点是否能够组成三叉树，如果不够，补齐相应的0，再以此组成相应的哈夫曼树，对于本题来说，应该加一个0，首先0,2,3，组合之后根节点是5，然后与4,5再次组合，根节点是14，最后和6,7一起组合，成为一棵深度为3的哈夫曼树，计算过程:(2+3) * 3+（4+5）*2+（6+7）=15+18+13=46

发表于 2022-11-12 16:51:40 回复(0)