Trouble understanding Huffman Tree algorithm

Question

I am working on a Huffman Tree based off of a frequency table. The frequency table is generated from counting the frequency of characters in a given string and placing the respective item (character and frequency) in a LinkedList. I then need to place the items in a Huffman Tree in order of their frequency. I get that the logic behind it is to make sure there are right and left nodes to each subtree, add their frequencies, create a root node with their added frequencies, place the next frequencies in the left and right trees respectively and repeat this process until there are no more frequencies and the subtrees are connected with a root that adds their frequencies; the trouble I am having is figuring out how to implement the code.

The code is rather extensive so I would rather avoid posting all of it, the general layout is that I have a HuffmanFrequencyTable class that allows me to build the table, a HuffmanTreeNode class that allows us to create nodes to place in the tree, and a HuffmanTree class that helps us create the actual tree. An encode class then inputs a string and builds the tree from the string using the HuffmanFrequencyTable it creates. This is a homework problem so please do not provide solutions, I am just hoping for some help in figuring out the logic in the code of it.

Right now, I am creating an array of characters that have been placed in the tree, finding the lowest frequency among characters remaining in the table that aren't in the array, and attempting to place them in leafs. When the base leafs are full in the subtrees I am trying to add those values, create a node, and continue up the tree. I am using a for loop for this. Does this seem like the right start?

Answer 1

Yes. you are on the right track.

And for decoding you use the same tree and and traverse left or right till you reach a leaf node and that is the character.

Answer 2

As Sajit says, you are on the right way. Maybe you define an additional class HuffmannTuple with something like

public class HuffmannTuple{

    public char character;
    public double frequency;

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

}

and create a sort List of them for lather calculation of the values like average wordlength and so on. Or even

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

}

for setting the corresponding code later.