Results 1 to 16 of 16
  1. #1
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Traversing a Huffman Tree

    I have the code that makes a huffman tree by reading a text file, creating a linked list, sorting it, then building the tree from the list. I have checked and am almost positive this is working correctly. Now i need to traverse the tree in order to assign a binary value to each character (leaf node). I am having trouble with the algorithm to traverse the tree and properly assign the binary values (they just have to b in the form of a string). I know how to do this by looking at the tree, just can't figure out how to implement the code. Any help would be appreciated. Here is my code:

    Java Code:
    import java.util.*;
    import java.io.*;
    
    public class HuffmanEncoding 
    {	
    	public static void main (String[]args) throws IOException
    	{
    		File myFile=new File("textfile.txt");
    		LinkedList<Node> myList=new LinkedList<Node>();
    		makeList(myList, myFile);
    		sortList(myList);
    		makeTree(myList);
    	}
    	
    	/* makes a linked list from the text file
    	 *  reads text file string by string and then each string character by character
    	 * creates a new node for any character that is not already in the list
    	 * adds to th frequency if there is already a node for that character
    	 */
    	public static void makeList(LinkedList<Node> list, File file) throws IOException
    	{		
    		Scanner text=new Scanner(file);
    		while (text.hasNext()==true)
    		{ 			
    			String word=text.next().toLowerCase();			
    			for (int j=0;j<word.length();j++)			
    			{
    				boolean alreadyInList=false;
    				for (int i=0; i<list.size(); i++)
    				{			
    					if (word.charAt(j)==list.get(i).character)
    					{
    						list.get(i).frequency=list.get(i).frequency+1;
    						alreadyInList=true;
    					}					
    				}
    				if (alreadyInList==false)
    				{
    					Node newNode=new Node(word.charAt(j), 1);
    					list.add(newNode);
    				}	
    			}			
    		}		
    	}
    	/* sorts the list in order of least to greatest frequencies
    	 * also goes through the list to assign "next" Nodes to each element in the list
    	 */
    	public static void sortList(LinkedList<Node> list)
    	{
    		for (int i=0;i<list.size()-1;i++)
    		{
    			for (int j=i+1;j<list.size();j++)
    			{
    				if (list.get(i).frequency>list.get(j).frequency)
    				{
    					Node temp=list.get(i);
    					list.set(i, list.get(j));
    					list.set(j, temp);
    				}
    			}
    		}
    		for (int pos=0;pos<list.size()-1;pos++)
    		{
    			list.get(pos).next=list.get(pos+1);
    		}
    	}
    	 /* makes a huffman tree from the sorted list
    	  * gets rid of the pointers to the next node that were in the linked list
    	  */
    	public static void makeTree(LinkedList<Node> list)
    	{
    		int numLeafNodes=list.size();
    		while(list.get(0).next!=null)
    		{
    			int newFreq=list.get(0).frequency+list.get(1).frequency;
    			list.get(0).next=null;
    			list.get(1).next=null;
    			Node tempNode1=list.get(0);
    			Node tempNode2=list.get(1);
    			list.remove(0);
    			list.remove(0);
    			Node newNode=new Node(newFreq, tempNode1, tempNode2);
    			list.add(newNode);
    			if (list.size()>1)
    				list.get(list.size()-2).next=newNode;			
    		}
    	}
    	
    	/* returns the a string containing 0's and 1's that correspond to the characters position in the tree
    	 *
    	 *  DONT KNOW HOW TO IMPLEMENT THIS
    	 */
    	public static String characterCode(Node root, char c)
    	{
    		
    			
    		
    	}
    	
    	/*
    	 * Node class used in linked list as well as tree
    	 */
    	public static class Node
    	{
    		private char character;
    		private int frequency;
    		private Node left;
    		private Node right;
    		private Node next;
    		public Node(char c, int freq)
    		{
    			character=c;
    			frequency=freq;
    		}		
    		public Node (int freq, Node L, Node R)
    		{
    			frequency=freq;
    			left=L;
    			right=R;
    		}
    	}			
    }

  2. #2
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    Trying something like this now, not working correctly though:

    Java Code:
    public static String characterCode(Node root, char c, String code)
    	{
    		if (root!=null)
    		{
    			if (root.left.character==c)
    			{
    				return code+"0";
    			}
    			else if (root.left!=null)
    			{
    				return code+characterCode(root.left, c, code);
    			}
    			if (root.right.character==c)
    			{
    				return code+"1";
    			}
    			else if (root.right!=null)
    			{
    				return code+characterCode(root.right, c, code);
    			}
    			
    		}
    		return "";
    	}

  3. #3
    SJF
    SJF is offline Senior Member
    Join Date
    Oct 2012
    Posts
    108
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    Your algorithm seems a bit off... Namely code never changes.

    Java Code:
    1st call:   root = <root>
                  c = 'C'                     //pretend we're looking for C
                  code = ""
    
    2nd call:  root = <root's left child>
                 c = 'C'
                 code = ""                 //code should = "0" here!
    Java Code:
               else if (root.left != null) {
                    return characterCode(root.left, c, code+"0");
                }
    That still isn't right... but closer.

    Java Code:
    IF left child not null AND character = search character 
        RETURN code + "0"
    ELSE IF right child not null AND character = search character
        RETURN code + "1"
    ELSE IF left child not null AND TRY_LEFT_CHILD(code + "0") != null 
        RETURN TRY_LEFT_CHILD(code + "0")
    ELSE IF right child not null AND TRY_RIGHT_CHILD(code + "0") != null
        RETURN TRY_RIGHT_CHILD(code + "1")
    ELSE 
        RETURN null
    TRY_LEFT_CHILD(code + "0") => characterCode(root.left, c, code + "0")

  4. #4
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    Yeah, I tried it that way and it at least giving me the right amount of bits out, but it will print out whatever path you try first. So if i try the right path first in my code it will print out 111 for any letter i test. Likewise, if i try the left child condition first, it will print out 000 for any letter i test. I need someway to track the path that gets it to the correct letter, and print out just that path. Thinking this might be easier to do iteratively, i'm working on it but still not really sure.

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: Traversing a Huffman Tree

    Recursion is your friend (as always); suppose 'path' is the bit string up to a given node n; if node n has a left child, you know that the path up to that node is path+"0"; similar reasoning applies to the right child where the path is path+"1". The path for the root node is "":

    Java Code:
    void buildPath(Node n, String path) {
       if (n.left != null) buildPath(n.left, path+"0");
       if (n.right != null) buildPath(n.left, path+"1");
       if (n.left == null && n.right == null) { // a child node
          // process the path given to this node
       }
    }
    kind regards,

    Jos
    Last edited by JosAH; 03-21-2013 at 07:47 AM. Reason: stupid typo for the right child node
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    I've been thinking about what to return for a couple hours now and havent made much ground, I get how your recursion method works but I dont know what the general thing to return is when we reach a leaf node, my only thought is to make counters and make conditions for every situation which doesnt seem very efficient, and couldn't account for a large text. Anyways here is what I have so far:

    Java Code:
    public static String characterCode(Node root,char c, String code)
    	{
    		if (root!=null)
    		{
    			if (root.left!=null)
    				characterCode(root.left,c,code+"0");
    			if (root.right!=null)
    				characterCode(root.right,c,code+"1");
    			if (root.left==null && root.right==null && root.character==c)		
    				return code;		
    		}
    		return code+"";
    	}
    Last edited by berb12; 03-21-2013 at 03:44 AM.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: Traversing a Huffman Tree

    Why should you return something? For each character (a leaf node) you want to know its code (path); you can build a table for those tuples (char, path); if you have to read in a bit sequence, all you have to do is move left/right through your tree until you reach a lead node (a character); my suggestion finds the path for each character and you can build the table with it. In short: the table is for encoding and your tree is for decoding.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    I wanted to return something because basically what i have to do is read an input file, make a huffman tree based on characters' frequencies, assign bits to each character and then write an output file using the bits (just as strings) instead of the characters. this is what i want to be able to do in the end using my characterCode method:

    Java Code:
    Scanner text=new Scanner(myInputFile);	       
    {
    		while (text.hasNext()==true)
    		{ 												
    			String word=text.next().toLowerCase();	 
    			for (int j=0;j<word.length();j++)			
    			{
    				String bits="";                       
    				myOutputFile.write(characterCode(myList.get(0), word.charAt(j), bits));
    			}
    		}
    }

  9. #9
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    I understand what you are saying, i just don't know how to process the paths for each character.

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: Traversing a Huffman Tree

    Quote Originally Posted by berb12 View Post
    I understand what you are saying, i just don't know how to process the paths for each character.
    Just implement my algorithm; it 'hits' each and every character (leaf node) in the tree, so you can build up your entire table with it. Again: use the table for encoding and your tree for decoding purposes.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    Yeah, but how do you assign each character the appropriate bits, because the String 'path' doesn't change.

  12. #12
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    like if I print out 'path' anywhere in that method it is the same as what you input it as.

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: Traversing a Huffman Tree

    Quote Originally Posted by berb12 View Post
    Yeah, but how do you assign each character the appropriate bits, because the String 'path' doesn't change.
    Yes it does (either a 0 or a 1 is added at each recursive call).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    Ok I realized what I was doing wrong with that, so when i run this, the right code for the character is printed:

    Java Code:
    public static void characterCode(Node root,String code, char c)
    	{
    		if (root!=null)
    		{	
    			if (root.left!=null)
    				characterCode(root.left, code+"0", c);
    			if (root.right!=null)	
    				characterCode(root.right,code+"1", c);
    			if (root.left==null && root.right==null && root.character==c)
    				System.out.println(code);				
    		}		
    	}
    How do i retrieve this code for each character bc if i just put a 'return code' in place of the s.o.p statement, it says I need another return statement at the end of the method, which was what was causing me problems originally

  15. #15
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: Traversing a Huffman Tree

    Leave out the third parameter 'char c' and change the last to lines of your method to;

    Java Code:
    if (root.left==null && root.right==nulll)
       System.out.println(root.character+": "+code);
    Run it and you'll see your table (in no particular order).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Traversing a Huffman Tree

    thanks a lot, got it working

Similar Threads

  1. Traversing Binary Tree from Root to each Branch
    By vluong in forum Advanced Java
    Replies: 3
    Last Post: 04-16-2012, 05:28 PM
  2. Help: traverse Huffman tree
    By Reploids in forum New To Java
    Replies: 0
    Last Post: 05-24-2011, 10:02 AM
  3. Help: traversing huffman tree
    By Reploids in forum New To Java
    Replies: 0
    Last Post: 05-24-2011, 09:42 AM
  4. Methods in FrequencyTree (or Huffman Tree?)
    By Beginner101 in forum Eclipse
    Replies: 0
    Last Post: 04-04-2011, 09:31 PM
  5. Replies: 2
    Last Post: 10-28-2010, 10:45 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •