java - 哈夫曼树算法难以理解

Question

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

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

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

Answer 1

正如 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;
    }

}

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