CODEWITHSUNDEEP
java
Samson
Samson

Reputation: 133

Huffman tree wrong output

this is my first time using stackoverflow to ask a question and i hope you guys can help me out :)

i am working on a projecting to implement Huffman code. The problem is that i got a wrong result when i try to print the code.

Here is the input file and correct result:

Symbol    A     B   C   D    _
frequency 0.35 0.1 0.2 0.2 0.15
Code      11   100 00  01  101

the result i got:

Symbol    A     B   C   D    _
frequency 0.35 0.1 0.2 0.2 0.15
Code      00   011  10  11  010

Here is the class file:

import java.util.*;
import java.io.*;
import java.util.PriorityQueue;

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

    public Node(String textIn, Float frequencies) {
        text = textIn;
        frequency = frequencies;
    }

    public Node(Float d) {
        text = "";
        frequency = d;
    }

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

    public static void buildPath(Node root,String code)
{
    if (root!=null)
    {   
        if (root.left!=null)
            buildPath(root.left, code+"0");
        if (root.right!=null)   
          buildPath(root.right,code+"1");
        if (root.left==null && root.right==null)
            System.out.println(root.text+": "+code);               
    }       
}



    public static Node makeHuffmanTree(Float[] 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;
    }

I think there is something wrong with my printing method?

and heres my main

public static void main(String[] args)
String[] Symbol = {"A","B","C","D","_"};
Float[] frequency = (0.35,0.1,0.2,0.2,0.15};

        Node root = Node.makeHuffmanTree(frequency, Symbol);
        Node.buildPath(root, "");

Upvotes: 1

Views: 311

Answers (1)

Dennis Meng
Dennis Meng

Reputation: 5187

In your output, the lengths of the individual codes look fine, so I'm less convinced it's a tree traversal issue now.

The discrepancy could very well be in how you're building the tree. When you pop off two elements from your queue and make a new tree with those two as subtrees, the choice of which subtree is the "left" subtree affects the resulting codes.

Looking at your while loop, I see

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

I haven't worked through the example fully, but Having worked through your example, I think just changing to combined.left = least1 and combined.right = least2 instead of the other way around will give the codes you're expecting.

Upvotes: 1

Related Questions