作者： | 来源：互联网 | 2023-07-11 17:13
如何重新设计霍夫曼树节点的权重，使得权值尽可能小(整数)，而且根据新权值生成的霍夫曼树和原树完全一致？如果可能的话，n个原始数据生成的2n-1个节点的树会不会有个权值上限A？即重新生成的权
如何重新设计霍夫曼树节点的权重，使得权值尽可能小(整数)，而且根据新权值生成的霍夫曼树和原树完全一致？
如果可能的话，n个原始数据生成的2n-1个节点的树会不会有个权值上限A？即重新生成的权值不可能会大于这个数A？
16 个解决方案
我看了半天也不太明白你的意思，可否将你的问题说得再详细一点，
================================================================
CSDN 论坛助手 Ver 1.0 B0402提供下载。 改进了很多，功能完备！
★ 浏览帖子速度极快！[建议系统使用ie5.5以上]。 ★ 多种帖子实现界面。
★ 保存帖子到本地[html格式]★ 监视您关注帖子的回复更新。
★ 可以直接发贴、回复帖子★ 采用XML接口，可以一次性显示4页帖子,同时支持自定义每次显示帖子数量。可以浏览历史记录！
★ 支持在线检测程序升级情况，可及时获得程序更新的信息。
★★ 签名 ●
可以在您的每个帖子的后面自动加上一个自己设计的签名哟。
Http://www.ChinaOK.net/csdn/csdn.zip
Http://www.ChinaOK.net/csdn/csdn.rar
Http://www.ChinaOK.net/csdn/csdn.exe [自解压]
霍夫曼树生成原理是权值越大的越在上面，每一层的节点的权值都比下一层的大
现在假设有如下原始数据：
6 8 14 25 23 9进行霍夫曼编码
85
/ \
37 48
/ \ / \
23 14 23 25
/ \
14 9
/ \
6 8
但我们知道根据以上权值构建的霍夫曼树不是唯一的
我的问题是：
能否根据已知的霍夫曼树生成每个节点的权值再根据此权值重新构建树
和原来的树完全一样？
还有就是能否让新生成的权值尽可能小
没想到progame会问这样的问题：）
我先说两句吧。
首先，霍夫曼树就是一个权重最小的生成树，尽可能小又从何谈起呢？
其次，霍夫曼树不可能唯一，因为：
1、对换已生成的一个树的任一左、右子树，都会生成不同的霍夫曼树。
2、在已生成的一个霍夫曼树中，对换任两个权重相同的子树也会生成不同的霍夫曼树。
我想你误会我的意思了
霍夫曼树当然生成的总权重是最小的
我的问题是，拿上面的例子说吧：
我可以把生成树后的节点权值替换成：
6 8 14 25 23 9
1 2 3 10 9 4
这样根据此数据重新构建树，树结构和原来是一样的
我要的就是重新生成一个可以重构树的权值集
什么叫“能否让新生成的权值尽可能小”？是说所有整数之和最小么？
85
/ \
37 48
/ \ / \
23 14 23 25
/ \
14 9
/ \
6 8
85
/ \
37 48
/ \ / \
14 23 23 25
/ \
9 14
/ \
6 8
18
/ \
8 10
/ \ / \
4 4 5 5
/ \
2 2
/ \
1 1
偶不知道怎么说，就画了上面的图，第一张图令左子树的权小等于右子树的权，成为第二张数，然后从叶子节点往上推，如第三张图，可以作出最小值18，程序你自己编一下，哎，不知道怎么表达，大概偶的思路就是这样。
/ \
1 1
这样是不行的，因为这两个节点可以互换，生成的树不唯一
/\ /\
4 4 5 5
这样加一编码也不行，万一这层有N个节点
这样的话如果编码为：
x x+1 x+2 ... x+n-1
x+(x+1)还应该大于x+n-1才行
你的意思是这个权值不能相同，那就是说新的权值的整数各不相同，这样行么：
25
/ \
12 13
/ \ / \
5 7 6 7
/ \
4 3
/ \
1 2
27
/ \
14 13
/ \ / \
5 9 6 7
/ \
4 5
/ \
2 3
又错了：
29
/ \
14 15
/ \ / \
5 9 7 8
/ \
4 5
/ \
2 3
你不要把树的左右节点对换
要和原来完成一致的
这样重新编码才能也一致
我的想法是如果有个最顶端的M值
而下一层有N个节点，则：
N*X + N*(N-1)/2 = M
求出X，向下取整，即为此层第一个节点的权值
依此类推，直到最底下一层
可是M值无法获知：(
如果从自底而上的方法处理：
我即使能够保证这一层的节点的父节点都比这一层权值大
如：
X X
/ \ / \
X X X X
我可以X+(X+1)>X+3得到X值为3，即下面一层权值为：3 4 5 6
上一层为 7 11
可是我无法保证上一层节点数会不会大于6个，如下面这样
X X X X X X X X
/ \ / \
X X X X
7~11之间的数是不够分配的
京公网安备 11010802041100号