霍夫曼编码算法给怪树（Java）

我一直在尝试很多不同的东西在这里，似乎无法得到它的工作。输入是“abbcccddddeeeee”，它给出了链接列表a，b，c，d，e，其频率分别为1,2,3,4,5。霍夫曼编码算法给怪树（Java）

出于某种原因，不过，这似乎是给我基于很多不同的测试下面的树我已经运行：

    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); 
}

这将是绝对惊人的，如果有人可以帮助我，我令人难以置信的令人难以置信的沮丧。

谢谢！

来源

2011-10-05 Andrew Latham

问题出在getSortedLinkedList。看起来你正在交换频率值而不是节点本身，所以指针不会随频率值移动。

一般来说，当你在处理链表它真的有用提请各阶段的照片：

a1->b2->c3->d4->e5

第一步：

f3->c3->d4->e5 
    /\ 
a1 b2

排序：没有变化

下一个步骤：

f6->d4->e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

排序做到这一点：

d4->e5->f6 (forgot to move child nodes with frequency) 
    /\ 
    f3 c3 
    /\ 
a1 b2

下一步：

 f9->f6 
     /\ 
    d4 e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

排序：

 f6->f9 (forgetting to move child nodes with frequency) 
     /\ 
    d4 e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

最后一步：

来源

2011-10-05 07:48:41 Skizz

太感谢你了！ :) –

霍夫曼编码算法给怪树（Java）

回答

相关问题