Recursively searching a tree to get the binary coding for a character

Hi im trying to figure out how to recursively search a tree to find a character and the binary code to get to that character. basically the goal is to go find the code for the character and then write it to a file. the file writer part i can do no problem but the real problem is putting the binary code into a string. while im searching for the character. please help!

this is the code for the recursive m开发者_StackOverflow社区ethod:

public String biNum(Frequency root, String temp, String letter)
{
    //String temp = "";
    boolean wentLeft = false;
    if(root.getString() == null && !wentLeft)
    {
        if(root.left.getString() == null)
        {
            temp = temp + "0";
            return biNum(root.left, temp, letter);
        }
        if(root.left.getString().equals(letter))
        {
            return temp = temp + "0";
        }
        else
        {
            wentLeft = true;
            temp = temp.substring(0, temp.length() - 1);
            return temp;
        }
    }
    if(root.getString() == null && wentLeft)
    {
        if(root.right.getString() == null)
        {
            temp = temp + "1";
            return (biNum(root.right, temp, letter));
        }
        if(root.right.getString().equals(letter))
        {
            return temp = temp + "1";
        }
        else
        {
            wentLeft = false;
            temp = temp.substring(0, temp.length() - 1);
            return temp;
        }

    }
    return temp;


}

and this is the Frequency class:

package huffman;

public class Frequency implements Comparable { private String s; private int n; public Frequency left; public Frequency right; private String biNum; private String leaf;

Frequency(String s, int n, String biNum)
{
    this.s = s;
    this.n = n;
    this.biNum = biNum;
}
public String getString()
{
    return s;
}
public int getFreq()
{
    return n;
}
public void setFreq(int n)
{
    this.n = n;
}
public String getLeaf()
{
    return leaf;
}
public void setLeaf()
{
    this.leaf = "leaf";
}
@Override
public int compareTo(Object arg0) {
    Frequency other = (Frequency)arg0;

    return n < other.n ? -1 : (n == other.n ? 0 : 1);

}

}

In your updated version, I think you should re-examine return biNum(root.left, temp, letter);. Specifically, what happens if the root node of the entire tree has a left child which is not a leaf (and thus root.left.getString() == null) but the value you seek descends from the right child of the root node of the entire tree.

Consider this tree, for example:

          26
         /  \
        /    \
       /      \
      11      15
     /  \    /  \
    /    B  A    \
   6     5  6     9
  / \            / \
 D   \          C  sp
 3    3         4  5
     / \
    E   F
    2   1

and trace the steps your function will follow looking for the letter C.

Perhaps you should consider traversing the entire tree (and building up the pattern of 1s and 0s as you go) without looking for any specific letter but taking a particular action when you find a leaf node?