This discussion is archived
4 Replies Latest reply: Dec 22, 2009 10:47 AM by DrClap RSS

Print empty nodes in a Huffman binary Tree

843789 Newbie
Currently Being Moderated
Hi,

I have constructed a binary huffman tree, and I need to print the empty nodes as a character '-'. As I am using the array structure to build the huffman tree, I am very confused how I can go about it. This is my code. Any help will be appreciated:
import java.util.*;
import java.io.*;
import java.lang.*;

public class Huffman
{
    static char letters;
    static int frequency;
    static char frequency1;
    static int alphabet;
    static char frqtable [][];
    static char treetable[][];
    static TreeNode myTree[];
    static int i = 0;
    static int j = 0;
    static Scanner in = new Scanner(System.in);
    static int index = 0;
    static Vector temp = new Vector(); 
    static String finalarray[];
 
    
    public static void main (String args[])throws IOException{

        setFrequencyTable();
        treetable = frqtable;
        sortArray(treetable);
        buildHuffmanTree(treetable, alphabet);
       // printGeneralTree();
        
    }
    
     public static void setFrequencyTable() throws IOException{
        System.out.println ("Please enter number of distinct alphabet");
        alphabet = in.nextInt();
        frqtable = new char[alphabet][2];
        
        
       for (int count = 0; count<alphabet; count++){
            System.out.println ("Enter the character");
            letters = (char) System.in.read();
            frqtable[i][j] = letters;
            System.out.println ("Enter frequency");
            frequency = in.nextInt();
            frequency1 = Integer.toString(frequency).charAt(0); ;
            frqtable[i][j+1] = frequency1;
            i = i+1;
            j = 0;
        }
    }
    
    public static void sortArray (char[][]treetable){
        char templetter;
        char tempfrq;
    
      for (int j=0; j < frqtable.length; j++) {
        for (int i=0; i < frqtable.length-1; i++) {

              if((treetable[1]) < (treetable[i+1][1])){
tempfrq = (treetable[i][1]);
templetter = (treetable[i][0]);
(treetable[i][1]) = (treetable[i+1][1]);
(treetable[i][0]) = (treetable[i+1][0]);
(treetable[i+1][1]) = tempfrq;
(treetable[i+1][0]) =templetter;
}
}
}



}
public static void levelorderTraversal(TreeNode root) {
levelorderHelper( root);
System.out.println();
}


private static void levelorderHelper( TreeNode node ) {
if( node == null )
return;

queue( node ); // queues root
qLeftqRight( index ); // queues Left/Right node of the node at 'index'
printIt(); // prints contents of queue
}

private static boolean queue( TreeNode n ) {
if( n != null ){ // if child exists, queue it
temp.addElement( n );

return true;
}else{

return false;
}
}

private static void qLeftqRight( int i ) { // for each queued node, queue its children
while( i < temp.size() ) {
TreeNode tmp = (TreeNode) temp.elementAt( i );
if (tmp.leaf == false){
queue( tmp.left );
queue( tmp.right );
}
i++;
}
}

private static void printIt() {
finalarray = new String[temp.size()];
for( int x = 0; x < temp.size(); x++ ) {
TreeNode t = (TreeNode) temp.elementAt( x );
if(t.ch == '\0'){
finalarray[x] = Integer.toString(t.count);
}else{
finalarray[x]=Character.toString(t.ch);
}
}
}





public static void buildHuffmanTree(char [][] treetable, int alphabet){
myTree = new TreeNode [alphabet];
TreeNode leftNode, rightNode;
TreeNode newNode = null;


for ( int i = 0; i < alphabet; i++ ){
myTree[i] = new TreeNode (treetable[i][0], Character.getNumericValue(treetable[i][1]));
}


for (int j =((myTree.length)-1); j>0; j--){
newNode = new TreeNode(myTree[j], myTree[j-1]);
myTree[j] = null;
myTree[j-1] =null;
if(j!=1){
for(int c = 0; c<(j-1); c++){
if(myTree[c].count <= newNode.count){
for(int x = alphabet-1; x>c; x--){
myTree[x] = myTree[x-1];

}
myTree[c] = newNode;
c= j-1;

}


}
}else{
myTree[0] = newNode;
}
}


levelorderTraversal(myTree[0]);

for(int i = 0; i < finalarray.length; i++){
System.out.println(finalarray[i]);
}


}
}
public class TreeNode{ 
final boolean leaf;
int count;
final char ch;
final TreeNode left,
right;

public TreeNode ( char ch, int count )
{  this.leaf  = true;
this.count = count;
this.ch = ch;
this.left = null;
this.right = null;

}

public char getChar(){
return ch;
}

public TreeNode ( TreeNode left, TreeNode right)
{  this.leaf  = false;
this.count = left.count + right.count;
this.left = left;
this.right = right;
this.ch ='\0';

}


}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
  • 1. Re: Print empty nodes in a Huffman binary Tree
    DrClap Expert
    Currently Being Moderated
    As far as I can see you don't have any code which prints nodes, empty or otherwise. So instead of just dumping a heap of loosely-related code and expecting us to figure out what it does, could you point to some specific code which you think is supposed to be printing an empty node and ask about that code?
  • 2. Re: Print empty nodes in a Huffman binary Tree
    843789 Newbie
    Currently Being Moderated
    The finalarray actually prints the array. The problem I think is with the TreeNode class where a leaf states the left and right nodes as null, but if I instantiate them to '-' they will continue to assign empty nodes until the program runs out of memory!!
  • 3. Re: Print empty nodes in a Huffman binary Tree
    3004 Newbie
    Currently Being Moderated
    doobybug wrote:
    The finalarray actually prints the array.
    No, finalarray IS and array. It doesn't print anything.
    The problem I think is with the TreeNode class where a leaf states the left and right nodes as null, but if I instantiate them to '-' they will continue to assign empty nodes until the program runs out of memory!!
    I don't know what you're saying here, but it sounds like you think that you have to set the Node to '-' in order to be able to print '-'. Really all you have to do is
    for each node {
      if the node is empty {
        print -
      }
      else {
        print whatever you print for non-empty nodes
      }
    }
    Or if an "empty" node is still a Node object, just with certain attribute values, then just create a toString method in the Node class that returns "-" when the Node is empty.

    Really, if you know how to iterate over your nodes, and you know how to determine whether a node is empty, then your problem is solved, there's nothing else to it.
  • 4. Re: Print empty nodes in a Huffman binary Tree
    DrClap Expert
    Currently Being Moderated
    doobybug wrote:
    The finalarray actually prints the array.
    No, it doesn't. It's just an array of Strings. All it does is to contain some Strings.
    The problem I think is with the TreeNode class where a leaf states the left and right nodes as null, but if I instantiate them to '-' they will continue to assign empty nodes until the program runs out of memory!!
    So at some point you print a String, and if it's null you want to print a dash instead? Then like this:
    if (someString == null) {
      print("-");
    } else {
      print(someString);
    }