一组权值是不是可以构造很多种哈夫曼树?

来源：百度知道 编辑：UC知道 时间：2024/05/27 01:32:17
例如,a,b,c,d,e他们出现的频率为4,7,5,2,9,试画出对应的哈夫曼树.
这个题是不是有不同的答案?因为哈夫曼树不唯一?
他们分别是什么?不同的哈夫曼树他们有什么不同点和相同点(同一组权值)
2. 根据使用频率为5个字符设计的哈夫曼编码不可能是( )
A 000,001,010,011,1 B 0000,0001,001,01,1
C 000,001,01,10,11 D 00,100,101,1100,111
为什么??
有一份电文中共使用5个字符:a,b,c,d,e,它们的出现频率依次为4,7,5,2,9,试画出对应的哈夫曼树,并求出每个字符的哈夫曼编码.(共有几种答案?)

一组权值对应一个吧。
对于你给出的题目树的样子应该是这样
27
/ \
11 16
/ \ / \
5 6 7 9
/ \
2 4
路经是2*3+3*2=12；
如果你认为左右互换不等的话，那么就是有很多种了，一般的霍夫曼树都有一种规定（隐性的啊），左边的数字比右边的小（对于同一层次上的节点来说）
在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
在 F 中删去这两棵二叉树。
把新的二叉树加入 F
根据这个思路你不难发现，每次找的都是最小的，怎么肯能有多种结构呢？
2 霍夫曼编码就是左边0，右边1了，对于根则没有
你可以看下各个选项
你想一下，对于每次取出两个最小的然后算出他们的和来放到集合里面，5个数字要有4个和，要9个节点的树才行啊，满足的怎么也要高度4吧，一定要注意到，同一层有两个的比如0000，0001，则000必定不是，而001不一定是。
对于A，你可以画出他的图示来，左边子树是完全树，右边只有一个节点可能的
B 同样画出也可能
C 也可能
D是不可能的
叶子只有00，而没有01，是构不成0的，而如果01是两个小数的和的话，应该还要有010，011之类的东西才行

一组权值对应一个哈夫曼二叉树，可能左右子树的节点顺序不同。