霍夫曼编码算法给出奇怪的树（Java）
我在这里尝试了很多不同的事情，但似乎无法让它发挥作用。输入是“abbcccddddeeeee”，它给出了一个链表a、b、c、d、e，频率分别为1、2、3、4、5。
不过，出于某种原因，它似乎根据我运行的许多不同测试为我提供了以下树：
f15
/ \
f6 f9
/ \
d4 e5
/ \
f3 c3
/ \
a1 b2
public static HTree createHuffmanTree(HLinkedList list)
{
while (list.size() != 1)
{
list = getSortedLinkedList(list);
HTreeNode p = list.head;
HTreeNode q = p.next;
HTreeNode r = new HTreeNode('f');
r.left = p;
r.right = q;
r.frequency = (p.frequency + q.frequency);
list.insertIntoPosition(r, 2);
list.remove(0);
list.remove(0);
list = getSortedLinkedList(list);
}
return new HTree(list.head);
}
如果有人可以帮助我，那将是绝对令人惊奇的，我非常非常沮丧。
谢谢你！
I've been trying a lot of different things here and can't seem to get it to work. The input was "abbcccddddeeeee", which gives a linked list a, b, c, d, e with frequencies 1, 2, 3, 4, 5, respectively.
For some reason, though, it appears to be giving me the following tree based on a lot of different tests I've run:
f15
/ \
f6 f9
/ \
d4 e5
/ \
f3 c3
/ \
a1 b2
public static HTree createHuffmanTree(HLinkedList list)
{
while (list.size() != 1)
{
list = getSortedLinkedList(list);
HTreeNode p = list.head;
HTreeNode q = p.next;
HTreeNode r = new HTreeNode('f');
r.left = p;
r.right = q;
r.frequency = (p.frequency + q.frequency);
list.insertIntoPosition(r, 2);
list.remove(0);
list.remove(0);
list = getSortedLinkedList(list);
}
return new HTree(list.head);
}
It would be absolutely amazing if someone could help me out, I'm incredibly, incredibly frustrated.
Thank you!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
问题出在
getSortedLinkedList中。看来您正在交换频率值而不是节点本身，因此指针不会随频率值移动。一般来说，当你处理链表时，绘制每个阶段的图片确实很有用：
第一步：
排序：无变化
下一步：
排序执行此操作：
下一步：
排序：
最后一步：
The problem is in
getSortedLinkedList. It appears that you are swapping frequency values and not the nodes themselves so the pointers aren't being moved with the frequency value.Generally, when you're dealing with linked lists it's really useful to draw pictures of each stage:
first step:
sort: no change
next step:
sort does this:
next step:
sort:
final step: