I have a problem with my Huffman tree code. In the main method I input a String of Symbols and I also input an Integer array containing the frequency of the Symbols. It should print out each Symbol and its Huffman code, but I think its wrong...
Here is the code:
package huffman;
import java.util.*;
abstract class HuffmanTree implements Comparable<HuffmanTree> {
public final int frequency; // the frequency of this tree
public HuffmanTree(int freq) { frequency = freq; }
// compares on the frequency
public int compareTo(HuffmanTree tree) {
return frequency - tree.frequency;
}
}
class HuffmanLeaf extends HuffmanTree {
public final char value; // the character this leaf represents
public HuffmanLeaf(int freq, char val) {
super(freq);
value = val;
}
}
class HuffmanNode extends HuffmanTree {
public final HuffmanTree left, right; // subtrees
public HuffmanNode(HuffmanTree l, HuffmanTree r) {
super(l.frequency + r.frequency);
left = l;
right = r;
}
}
public class Huffman {
// input is an array of frequencies, indexed by character code
public static HuffmanTree buildTree(int[] charFreqs, char[] test2) {
PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
// initially, we have a forest of leaves
// one for each non-empty character
for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[i] > 0)
trees.offer(new HuffmanLeaf(charFreqs[i], test2[i]));
assert trees.size() > 0;
// loop until there is only one tree left
while (trees.size() > 1) {
// two trees with least frequency
HuffmanTree a = trees.poll();
HuffmanTree b = trees.poll();
// put into new node and re-insert into queue
trees.offer(new HuffmanNode(a, b));
}
return trees.poll();
}
public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
assert tree != null;
if (tree instanceof HuffmanLeaf) {
HuffmanLeaf leaf = (HuffmanLeaf)tree;
// print out character, frequency, and code for this leaf (which is just the prefix)
System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);
} else if (tree instanceof HuffmanNode) {
HuffmanNode node = (HuffmanNode)tree;
// traverse left
prefix.append('0');
printCodes(node.left, prefix);
prefix.deleteCharAt(prefix.length()-1);
// traverse right
prefix.append('1');
printCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}
public static void main(String[] args) {
//Symbols:
String str = "12345678";
char[] test2 = str.toCharArray();
//Frequency (of the symbols above):
int[] charFreqs = {36,18,12,9,7,6,5,4};
// build tree
HuffmanTree tree = buildTree(charFreqs,test2);
// print out results
System.out.println("SYMBOL\tFREQ\tHUFFMAN CODE");
printCodes(tree, new StringBuffer());
}
}
The output I get is:
SYMBOL FREQ HUFFMAN CODE
1 36 0
3 12 100
6 6 1010
5 7 1011
2 18 110
4 9 1110
8 4 11110
7 5 11111
Thats weird, for example Symbol 7 should be: 11110 and Symbol 8 should be: 11111
Can you help me please?