title: Reconstuct Huffman Tree for Decoding
body: <p>I have encodings for compressed string data using Huffman Compression 
  i.e "more money needed"</p>
  
  <p>Encoding</p>
  
  <pre><code>\n 0110
     1011
  d  100
  e  11
  m  001
  n  000
  o  010
  r  0111
  y  1010
  **
  001010011111101100101000011101010110001111100111000110
  </code></pre>
  
  <p>I want to reconstruct the Huffman Tree in java to decode the encoding. Any implementation or example for such decoding.</p>
  
  <p>I tried and coded the perfect solution.</p>
  
  <pre><code>public class HuffmanTree {
  
      public Node root;
  
      public HuffmanTree(){
          this.root = new Node();
      }
  
      public void add(char data, String sequence){
  
          Node temp = this.root;
          int i = 0;
          for(i=0;i&lt;sequence.length()-1;i++){
  
            if(sequence.charAt(i)=='0'){
                  if(temp.left == null){
                      temp.left = new Node();
                      temp = temp.left;
                  }
                  else{
                     temp = (Node) temp.left;
                  }
              }
              else
                if(sequence.charAt(i)=='1'){
                  if(temp.right == null){
                      temp.right = new Node();
                      temp = temp.right;
                  }
                  else{
                      temp = (Node) temp.right;
                  }
           }}
  
          if(sequence.charAt(i)=='0'){
  
              temp.left = new Node(data); 
             }
          else{
              temp.right = new Node(data); 
  
          }
          }
  
      public String getDecodedMessage(String encoding){
  
          String output = "";
          Node temp = this.root;
          for(int i = 0;i&lt;encoding.length();i++){
  
              if(encoding.charAt(i) == '0'){
                  temp = temp.left;
  
                  if(temp.left == null &amp;&amp; temp.right == null){
                      output+= temp.getData();
                      temp = this.root;
                  }
              }
              else
              {
                  temp = temp.right;
                  if(temp.left == null &amp;&amp; temp.right == null){
                      output+= temp.getData();
                      temp = this.root;  
                  }
  
              }
          }
          return output;
      }
      // Traversal of reconstructed huffman tree for debugging.
      public void traversal(Node node){
  
          if(node == null)
                return;
          System.out.println(node);
          traversal(node.left);
          traversal(node.right);
  
      }
  
      }
  
  
  class Node{
  
      Node left;
      Node right;
      char data;
  
      public Node(){
  
      }
      public Node(char data){
          this.data = data;
      }
      public void setData(char data){
          this.data = data;
      }
      public char getData(){
          return this.data;
      }
      @Override
      public String toString(){
         if(this.data == Character.UNASSIGNED){
             return "No Value";
         } 
         else
             return ""+this.data;
      }
  }
  </code></pre>
  
  <p>If you have the encoded message in a text file the space character may cause any issue so I have written code for that one also.</p>
  
  <pre><code>import java.io.File;
  import java.io.FileNotFoundException;
  import java.io.FileWriter;
  import java.io.IOException;
  import java.util.Scanner;
  import java.util.logging.Level;
  import java.util.logging.Logger;
  
  
      public class Test {
  
         public static void main(String[] bscs){
  
             HuffmanTree tree = new HuffmanTree();
  
              String inputFile;
              String outputFile;
  
              Scanner kb = new Scanner(System.in);
              System.out.println("Please enter the name of the Input File");
              inputFile = kb.nextLine();
  
              File f = new File(inputFile);
                  Scanner fr = null;
              try {
                  fr = new Scanner(new File(inputFile));
                  fr.nextLine();
                  tree.add('\n', fr.nextLine().trim());
                  String temp = fr.nextLine();
                  if(temp.charAt(0)==' ' &amp;&amp; temp.charAt(1)==' ')
                  {
                      tree.add(' ', temp.trim());
                  }
                  else
                      tree.add(temp.charAt(0), temp.substring(1));
                  while(fr.hasNext()){
                      temp = fr.nextLine();
                      if(temp.equals("**")){
                          break;
                      }
                      else
                          tree.add(temp.charAt(0), temp.substring(1));
                  }
                  FileWriter f0 = new FileWriter(new File("decoded.ou"));
                  f0.write(tree.getDecodedMessage(fr.nextLine()));
                  f0.close();
  
              } catch (Exception ex) {
                 System.out.println(ex.getMessage());
              }
  
  
              }
  
      }
  </code></pre>