# Thread: Traversing a Huffman Tree

1. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## 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");
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++)
{
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;
}
}
{
Node newNode=new Node(word.charAt(j), 1);
}
}
}
}
/* 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
*/
{
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
*/
{
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);
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;
}
}
}```  Reply With Quote

2. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## 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 "";
}```  Reply With Quote

3. Senior Member Join Date
Oct 2012
Posts
108
Rep Power
0

## 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")   Reply With Quote

4. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## 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.  Reply With Quote

5. ## 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  Reply With Quote

6. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## 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.  Reply With Quote

7. ## 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  Reply With Quote

8. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## 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));
}
}
}```  Reply With Quote

9. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## Re: Traversing a Huffman Tree

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

10. ## Re: Traversing a Huffman Tree Originally Posted by berb12 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  Reply With Quote

11. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## Re: Traversing a Huffman Tree

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

12. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## 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.  Reply With Quote

13. ## Re: Traversing a Huffman Tree Originally Posted by berb12 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  Reply With Quote

14. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## 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  Reply With Quote

15. ## 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  Reply With Quote

16. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## Re: Traversing a Huffman Tree

thanks a lot, got it working  Reply With Quote

#### Posting Permissions

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