0

我正在研究基于频率表的霍夫曼树。频率表是通过计算给定字符串中字符的频率并将相应的项目（字符和频率）放在 LinkedList 中生成的。然后，我需要按照它们的频率顺序将这些项目放在霍夫曼树中。我知道它背后的逻辑是确保每个子树都有左右节点，添加它们的频率，使用它们添加的频率创建一个根节点，将下一个频率分别放在左右树中并重复此过程直到没有更多的频率，并且子树与添加频率的根相连；我遇到的麻烦是弄清楚如何实现代码。

代码相当广泛，所以我宁愿避免发布所有代码，一般布局是我有一个 HuffmanFrequencyTable 类允许我构建表，一个 HuffmanTreeNode 类允许我们创建节点以放置在树中，以及一个帮助我们创建实际树的 HuffmanTree 类。然后，一个编码类输入一个字符串，并使用它创建的 HuffmanFrequencyTable 从该字符串构建树。这是一个家庭作业问题，所以请不要提供解决方案，我只是希望在弄清楚它的代码中的逻辑方面得到一些帮助。

现在，我正在创建一个已放置在树中的字符数组，在表中剩余的不在数组中的字符中找到频率最低的字符，并尝试将它们放在叶子中。当子树中的基本叶子已满时，我试图添加这些值，创建一个节点，然后继续向上树。我为此使用了一个 for 循环。这似乎是正确的开始吗？

4

2 回答 2

2

正如 Sajit 所说，您走在正确的道路上。也许你定义了一个额外的类 HuffmannTuple 类似于

public class HuffmannTuple{

    public char character;
    public double frequency;

    public HuffmannTuple(char char, double freq){
        character = char;
        frequency = freq;
    }

}

并创建它们的排序列表，以计算平均字长等值。甚至

public class HuffmannTriple{

    public char character;
    public double frequency;
    public String code;

    public HuffmannTuple(char char, double freq){
        character = char;
        frequency = freq;
    }

    public void setCode(String c){
        code = c;
    }

}

用于稍后设置相应的代码。

于 2012-10-24T05:32:31.227 回答
1

是的。你在正确的轨道上。

对于解码，您使用同一棵树，然后向左或向右遍历，直到到达叶节点，这就是字符。

于 2012-10-24T05:12:06.157 回答