title: Huffman Tree Encoding
body: <p>My Huffman tree which I had asked about earlier has another problem! Here is the code: </p>
  
  <pre><code>package huffman;
  
  import java.io.FileNotFoundException;
  import java.io.FileReader;
  import java.util.ArrayList;
  import java.util.PriorityQueue;
  import java.util.Scanner;
  
  public class Huffman {
  
      public ArrayList&lt;Frequency&gt; fileReader(String file)
      {
          ArrayList&lt;Frequency&gt; al = new ArrayList&lt;Frequency&gt;();
          Scanner s;
          try {
  
              s = new Scanner(new FileReader(file)).useDelimiter("");
              while (s.hasNext())
              {
                  boolean found = false;
                  int i = 0;
                  String temp = s.next();
                  while(!found)
                  {
  
  
                      if(al.size() == i &amp;&amp; !found)
                      {
                          found = true;
                          al.add(new Frequency(temp, 1));
                      }
                      else if(temp.equals(al.get(i).getString()))
                      {
                          int tempNum = al.get(i).getFreq() + 1;
                          al.get(i).setFreq(tempNum);
                          found = true;
                      }
                      i++;
  
                  }
  
  
  
              }
          } catch (FileNotFoundException e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
          }
          return al;
      }
      public Frequency buildTree(ArrayList&lt;Frequency&gt; al)
      {
          Frequency r = al.get(1);
          PriorityQueue&lt;Frequency&gt; pq = new PriorityQueue&lt;Frequency&gt;();
          for(int i = 0; i &lt; al.size(); i++)
          {
              pq.add(al.get(i));          
          }
          /*while(pq.size() &gt; 0)
          {
              System.out.println(pq.remove().getString());
          }*/
  
          for(int i = 0; i &lt; al.size() - 1; i++)
          {   
             Frequency p = pq.remove(); 
             Frequency q = pq.remove();
             int temp = p.getFreq() + q.getFreq();
             r = new Frequency(null, temp);
             r.left = p; 
             r.right = q;
             pq.add(r);  // put in the correct place in the priority queue
          }
          pq.remove(); // leave the priority queue empty
          return(r); // this is the root of the tree built
  
      }
  
      public void inOrder(Frequency top)
      {
          if(top == null)
          {
              return;
          }
          else
          {
              inOrder(top.left);
              System.out.print(top.getString() +", ");
              inOrder(top.right);
              return;
          }
      }
      public void printFreq(ArrayList&lt;Frequency&gt; al)
      {
          for(int i = 0; i &lt; al.size(); i++)
          {
              System.out.println(al.get(i).getString() + "; " + al.get(i).getFreq());
          }
      }
  
  }
  </code></pre>
  
  <p>What needs to be done now is I need to create a method that will search through the tree to find the binary code (011001 etc) to the specific character. What is the best way to do this? I thought maybe I would do a normal search through the tree as if it were an AVL tree going to the right if its bigger or left if it's smaller. </p>
  
  <p>But because the nodes don't use ints doubles etc. but only using objects that contain characters as strings or null to signify its not a leaf but only a root. The other option would be to do an in-order run through to find the leaf that I'm looking for but at the same time how would I determine if I went right so many times or left so many times to get the character.</p>
  
  <pre><code>package huffman;
  
  public class Frequency implements Comparable  {
      private String s;
      private int n;
      public Frequency left;
      public Frequency right;
  
      Frequency(String s, int n)
      {
          this.s = s;
          this.n = n;
      }
      public String getString()
      {
          return s;
      }
      public int getFreq()
      {
          return n;
      }
      public void setFreq(int n)
      {
          this.n = n;
      }
      @Override
      public int compareTo(Object arg0) {
          Frequency other = (Frequency)arg0;
  
          return n &lt; other.n ? -1 : (n == other.n ? 0 : 1);
      }
  }
  </code></pre>
  
  <p>What I'm trying to do is find the binary code to actually get to each character. So if I were trying to encode <code>aabbbcccc</code> how would I create a string holding the binary code for a going left is 0 and going right is 1. </p>
  
  <p>What has me confused is because you can't determine where anything is because the tree is obviously unbalanced and there is no determining if a character is right or left of where you are. So you have to search through the whole tree but if you get to a node that isn't what you are looking for, you have backtrack to another root to get to the other leaves.</p>