给定一组权值:23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58，试构造一 棵具有最 小带权外部路径长度的扩充4叉树,要求该4叉树中所有内部结点的度都是4，所有 外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?
解 权值个数n=11，扩充4叉树的内结点的度都为4，而外结点的度都为0。设内结点个数为[tex=1.0x1.0]q+OmjBGfTRyR5QMrkDjA6Q==[/tex],外结点个数为[tex=1.0x1.0]rPe8HD1B57rI64A6lUKVGg==[/tex],则可证明有关系[tex=4.857x1.286]QWOu4ABFQVdoboF/vEpwYMsuy3Gwjbk86ZadF0C9JFU=[/tex]。由于在本题中[tex=5.357x1.286]/Z/glGZL+WlB7l3M3cnQlbPtOOcKkK85S/hrEn81BczVkYG/FAcPlxBsd/XAMZaX[/tex]+1，需要补2个权值为0的外结点。此时内结点个数[tex=1.0x1.0]q+OmjBGfTRyR5QMrkDjA6Q==[/tex]-4。仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4个结点。[img=686x284]17ae1a1b9563cec.png[/img]此树的带权路径长度WPL= 375+82 +169+ 18= 644。
举一反三
内容
- 0
哈夫曼树的带权路径长度是() A: 所有结点权值之和B．所有叶结点带权路径长度之和C．带权结点的值D．除根以外所有结点权值之和 B: A C: B D: C E: D
- 1
哈夫曼树的带权路径长度WPL为（）。 A: 除根结点之外的所有结点权值之和 B: 所有结点权值之和 C: 根结点的值 D: 各叶子结点的带权路径长度之和
- 2
由权值分别为9、2、5、7、4的5个叶子结点构造一棵哈夫曼树，则该树的带权路径长度为（ ）。 A: 45 B: 55 C: 60 D: 65
- 3
给定一组权值3.3.7.7.11,13.17试构造一棵哈夫曼树并计算出带权路径长度
- 4
用 4 个权值 { 7, 2, 4, 5 } 构造的哈夫曼（ Huffman ）树的带权路径长度是 。