2

我一直在研究这个霍夫曼树生成器：

// 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 个节点，然后插入具有 2 个出列的组合频率的新根项目进入优先队列。这就是方法应该做的所有事情。

这种方法应该构建霍夫曼树，但它构建不正确我已经按照代码手动构建了树，但我在纸上得到的与程序不同！由不同程序生成的正确答案与我的解决方案不同。输入数据（字母和频率）是：

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

至于我从中读取的文本无关紧要，因为频率已经在这里了。我需要做的 2 就是从这些频率构建树。

4

2 回答 2

2

你能试着用通俗的语言写出你的算法，而忽略任何 Java 细节吗？这可能会帮助您了解哪里出了问题（在算法中或在实现它的代码中），但也可以帮助人们帮助您。

不管算法如何，你真的打算让你的根节点从 ? 中的第二个元素开始ArrayList？Lists 从 0 开始索引，而不是 1。List.get(1)返回第二个元素。

public Frequency buildTree(ArrayList<Frequency> al) {
    Frequency r = al.get(1);
于 2010-07-23T01:50:03.987 回答
0

什么时候到期？我会开始为您实现的每个功能位编写单元测试——您也许可以通过这种方式暴露您的问题。还为这个混乱修复你的格式

“公共频率 buildTree(ArrayList al) { 频率 r = al.get(1); PriorityQueue pq = new PriorityQueue(); for(int i = 0; i < al.size(); i++) { pq.add(al .get(i)); } /while(pq.size() > 0) { System.out.println(pq.remove().getString()); }/"

格式化后编辑-我很难阅读您的代码。使变量名称具有描述性。'r' 没有告诉我任何信息，'al' 也没有。这将有助于了解您正在编码的文本是什么......

于 2010-07-23T00:22:59.770 回答