构建哈夫曼树

我一直对这个哈夫曼树构建器：构建哈夫曼树

// variable al is an array list that holds all the different characters and their frequencies 
// variable r is a Frequency which is supposed to be the roots for all the leaves which holds a null string and the frequencies of the combined nodes removed from the priority queue 
public Frequency buildTree(ArrayList<Frequency> al) 
{ 
    Frequency r = al.get(0); 
    PriorityQueue<Frequency> pq = new PriorityQueue<Frequency>(); 
    for(int i = 0; i < al.size(); i++) 
    { 
     pq.add(al.get(i));   
    } 
    /*while(pq.size() > 0) 
    { 
     System.out.println(pq.remove().getString()); 
    }*/ 

    for(int i = 0; i < al.size() - 1; i++) 
    { 
     Frequency p = pq.remove(); 
     Frequency q = pq.remove(); 
     int temp = p.getFreq() + q.getFreq(); 
     r = new Frequency(null, temp); 
     r.left = p; 
     r.right = q; 
     pq.add(r); // put in the correct place in the priority queue 
    } 
    pq.remove(); // leave the priority queue empty 
    return(r); // this is the root of the tree built 

}

什么代码试图做英语是

与它们的频率从添加的所有字符的优先级队列最低频率最高。接下来是ArrayList al的大小（其中包含所有字符）将第一个两个字符出列，然后设置一个新的根目录，让左右两个子节点出列，然后插入新组合的频率为2的新根将项目出队列入优先队列。那所有的方法都应该这样做。

这种方法应该是建立霍夫曼树，但它构建得不正确我遵循代码并手工构建树，但是我在纸上得到的结果与程序不同！由不同程序生成的正确答案与我的解决方案不同。输入数据（信件和频率）是：

a 6 
b 5 
space 5 
c 4 
d 3 
e 2 
f 1

作为该即时阅读，从它并不重要，因为频率已经在这里的文字。我所需要的2是从这些频率构建树。

来源

2010-07-23 Zieklecknerizer

大概需要看到Frequency'的'的定义以及 – barrowc 2010-07-23 00:38:38

的'定义Frequency'似乎是在您的其他问题：http://stackoverflow.com/questions/3311432/huffman-tree-encodeing – barrowc 2010-07-23 00:41:13

何时到期？我会开始为您的实现的每个功能位编写单元测试 - 您可能能够以这种方式公开您的问题。也固定格式设置为这种混乱

“公共频率buildTree（ArrayList的人）{频率R = al.get（1）; PQ的PriorityQueue =新的PriorityQueue（）;对（INT I = 0;我<人size（）; i ++）{pq.add（al.get（i））; }/while（pq.size（）> 0）{System.out.println（pq.remove（）。getString（））; “/”

edit-格式化后 - 我很难读取你的代码。使变量名称具有描述性。 'r'不会告诉我任何事情，'al'也不会。这将有助于知道你正在编码的文字是什么......

来源

2010-07-23 00:22:59 hvgotcodes

你可以尝试用简单的语言写出你的算法，忽略任何Java细节？这可以帮助您了解哪里出了问题（无论是在算法中还是在实现它的代码中），还可以帮助人们帮助您。

无论算法如何，您是否真的打算让您的根节点以ArrayList中的第二个元素开头？ List s从0开始索引，而不是1. List.get(1)返回第二个元素。

public Frequency buildTree(ArrayList<Frequency> al) { 
    Frequency r = al.get(1);

来源

2010-07-23 01:50:03

构建哈夫曼树

回答

相关问题