Huffman Tree with Given Frequency Confuse as how to start? Java

Question

I’m trying to understand what to do with my homework problem. I am trying to create a Huffman Tree that will encode and decode messages in Java. I am given Strings and Frequency.

[a=10, b=15, c=12, e=3, nl=4, sp=13, t=1]. 

I know that with Huffman Tree you take the two lowest Frequencies and make them into a tree with the sum of their Frequency as the parent. I understand that using a Priority Queue I can insert all the Frequency into it and use the remove() method to take out the 2 lowest Frequency. Then add them together to get the Weight of them both, then insert that Weight back into the Queue and repeat.

The final Tree should hold weight of

[58=root, root.left = 33, root.right = 25]   
[33.left = 18,  18.left = 8,  8.left = 4] 

I am not sure exactly how to even begin to implement a Huffman Tree code that will be able to create the tree with the Frequency and display the Tree. I’ve look at other codes and it seem like they all are creating from Streaming Input Code or so.

Any help would be great in getting me going. Thanks in advance!

I’m suppose to print out with a format like : (pre-order traversal)

58  
- 33  
- - 18  
- - - 8  
- - - - 4  
- - - - - 1:t  
- - - - - 3:e  
- - - -  4:nl  
- - - 10:a  
- - 15:b  
- 25  
- - 12:c  
- - 13:sp  

Answer 1

import java.util.PriorityQueue;

public class Node implements Comparable<Node> {
    Node left;
    Node right;
    Node parent;
    String text;
    int frequency;

    public Node(String textIn, int frequencyIn) {
        text = textIn;
        frequency = frequencyIn;
    }

    public Node(int frequencyIn) {
        text = "";
        frequency = frequencyIn;
    }

    public int compareTo(Node n) {
        if (frequency < n.frequency) {
            return -1;
        }
        else if(frequency > n.frequency) {
            return 1;
        }
        return 0;
    }

    public static void printFromPreOrder(Node n, String dashes) {
        // print with colon if leaf node
        if (n.text != "") {
            System.out.println(dashes + n.frequency + ":" + n.text);
        }
        else {
            System.out.println(dashes + n.frequency);
        }

        // Start recursive on left child then right
        if (n.left != null) {
            printFromPreOrder(n.left, dashes + "-");
        }
        if (n.right != null) {
            printFromPreOrder(n.right, dashes + "-");
        }
    }

    // Returns root node to pass to printFromPreOrder
    public static Node makeHuffmanTree(int frequencies[], String text[]) {
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
        for (int i = 0; i < text.length; i++) {
            Node n = new Node(text[i], frequencies[i]);
            queue.add(n);
        }
        Node root = null;
        while (queue.size() > 1)  {
            Node least1 = queue.poll();
            Node least2 = queue.poll();
            Node combined = new Node(least1.frequency + least2.frequency);
            combined.right = least1;
            combined.left = least2;
            least1.parent = combined;
            least2.parent = combined;
            queue.add(combined);
            // Keep track until we actually find the root
            root = combined;
        }
        return root;
    }

    public static void main(String[] args) {
        int frequencies[] = {10, 15, 12, 3, 4, 13, 1};
        String text[] = {"a", "b", "c", "e", "nl", "sp", "t"};
        Node root = Node.makeHuffmanTree(frequencies, text);
        Node.printFromPreOrder(root, "");
    }
}

This will work for you. I have included your example, but it should work for any number of frequencies and text. Just make sure the frequencies and text are of the same size because I did no error checking.