Kitty喜欢小鱼干 发表于 2018-10-24 14:48:37

请问遇到多关键字时怎么构建Huffman树？求 解此题。

       13个权值为5, 18, 12, 13, 4, 6, 7, 9, 28, 16, 20, 30, 2，请给出Huffman树。谢谢！{:5_108:}

claws0n 发表于 2018-10-24 14:48:38

本帖最后由 claws0n 于 2018-10-25 23:01 编辑

Kitty喜欢小鱼干 发表于 2018-10-25 22:11
对的，Huffman树：从关键字中总是选取最小的两个数，从底下往上走，但不是堆哦（因为堆是一棵完全二叉树 ...

先大到小或小到大排序（可以不需要，比较好理解而已，但是排序后方便遍历），然后以最小生产的权值配对
30 28 20 18 16 13 12 9 7 6 5 4 2
4 + 2 = 6
5 + 6 = 11
--------------------try 11 + 7 = 18, 6 + 7 = 13, 9 + 7 = 16
6 + 7 = 13
11 + 9 = 20
13 + 12 = 25
--------------------try 25 + 13 = 38, 20 + 13 = 33, 13 + 16 = 29
13 + 16 = 29
... 以此类推

claws0n 发表于 2018-10-25 19:10:14

可以试试，c 还是 cpp？

Kitty喜欢小鱼干 发表于 2018-10-25 21:47:45

claws0n 发表于 2018-10-25 19:10
可以试试，c 还是 cpp？

版主你好，这其实是一道试题（笔试，画图），因为想不出答案（题中关键字确实有点多{:5_104:}），所以向请教一下大家有什么合理的答案。

claws0n 发表于 2018-10-25 21:52:26

Kitty喜欢小鱼干 发表于 2018-10-25 21:47
版主你好，这其实是一道试题（笔试，画图），因为想不出答案（题中关键字确实有点多），所以向 ...

没有错的话，应该是大顶堆

Kitty喜欢小鱼干 发表于 2018-10-25 22:11:20

claws0n 发表于 2018-10-25 21:52
没有错的话，应该是大顶堆

对的，Huffman树：从关键字中总是选取最小的两个数，从底下往上走，但不是堆哦（因为堆是一棵完全二叉树，而Huffman树并不是。）！辛苦版主了！{:5_91:}

Kitty喜欢小鱼干 发表于 2018-10-26 11:45:16

claws0n 发表于 2018-10-24 14:48
先大到小或小到大排序（可以不需要，比较好理解而已，但是排序后方便遍历），然后以最小生产的权值配对 ...

哇！非常感谢版主！突然顿悟了。哈哈哈。{:5_109:}

claws0n 发表于 2018-10-26 11:48:25

Kitty喜欢小鱼干 发表于 2018-10-26 11:45
哇！非常感谢版主！突然顿悟了。哈哈哈。

复习复习 ^_^

Kitty喜欢小鱼干 发表于 2018-10-26 14:01:07

claws0n 发表于 2018-10-26 11:48
复习复习 ^_^

对了版主，能教教我怎么发图片吗？我想发个图片。谢谢！

claws0n 发表于 2018-10-26 14:02:16

Kitty喜欢小鱼干 发表于 2018-10-26 14:01
对了版主，能教教我怎么发图片吗？我想发个图片。谢谢！

如图

Kitty喜欢小鱼干 发表于 2018-10-26 14:03:28

claws0n 发表于 2018-10-26 14:02
如图

好的，谢谢！

Kitty喜欢小鱼干 发表于 2018-10-26 14:04:26

claws0n 发表于 2018-10-24 14:48
先大到小或小到大排序（可以不需要，比较好理解而已，但是排序后方便遍历），然后以最小生产的权值配对 ...

claws0n 发表于 2018-10-26 14:15:37

Kitty喜欢小鱼干 发表于 2018-10-26 14:04


小版只是业余爱好者，不是很懂这表达方法。{:5_99:}
没有错，是需要遍历的，然后配成最小生成树

Kitty喜欢小鱼干 发表于 2018-10-26 22:37:16

claws0n 发表于 2018-10-26 14:15
小版只是业余爱好者，不是很懂这表达方法。
没有错，是需要遍历的，然后配成最小生成树

真的很感谢版主，您的方法让我得到启发。{:5_95:}
页: [1]
查看完整版本: 请问遇到多关键字时怎么构建Huffman树？求 解此题。