title: Huffman Tree: Traversing
body: <p>I'm not sure how I'm going to attack the traversing of my Huffman Tree. The tree is correct, I just have a hard time figuring out how to traverse it in a good way. For some reason, my traversing method gives no result...</p>
  
  <p>UPDATE: Cleaned up the code, made it more Object Oriented</p>
  
  <p>Node class:</p>
  
  <pre><code>public class Node
  {
      public int frekvens; //Frequency
      public char tegn; //Symbol
      public Node venstre; //Left child
      public Node høyre; //Right child
      public string s; //result string
      public string resultat;
      public Node (char c) // Node constructor containing symbol.
      {
          frekvens = 1;
          tegn = c;
      }
  
      public Node (int f, Node venstre, Node høyre) // Node Constructor containing frequency and children
          {
              frekvens = f;
              this.venstre = venstre;
              this.høyre = høyre;
          }
  
      public Node (Node node) // Node constructor containing a node
          {
              frekvens = node.frekvens;
              tegn = node.tegn;
              this.venstre = venstre;
              this.høyre = høyre;
          }
  
      public void ØkMed1() // Inkrement frequency by one
      {
          frekvens = frekvens + 1;
      }
  
  
      public char getVenstreTegn ()
      {
          return venstre.tegn;
      }
  
      public char getHøyreTegn ()
      {
          return venstre.tegn;
      }
  
      public int getVenstreFrekvens ()
      {
          return venstre.frekvens;
      }
  
      public int getHøyreFrekvens ()
      {
          return høyre.frekvens;
      }
  
      public int getFrekvens()
      {
          return frekvens;
      }
  
  
      public bool ErTegn(char c)
      {
          if ( c == tegn)
          {
              return false;
          }
          else
          {
              return true;
          }
      }
  
      //Pretty sure this does not work as intended
      public string traverser (Node n) //Traverse the tree
      {
          if (n.tegn != '\0') //If the node containes a symbol --&gt; a leaf
          {
              resultat += s;  
          }
          else
          {
              if (n.getVenstreTegn() == '\0') //If left child does not have a symbol
              {
                  s += "0";
                  traverser(n.venstre);
              }
              if (n.getHøyreTegn() == '\0') //If right child does not have a symbol
              {
                  s += "1";
                  traverser(n.høyre);
              }
          }
          return resultat;
      }
      public string Resultat() //Used priviously to check if i got the correct huffman tree
      {
          string resultat;
          resultat = "Tegn: " + Convert.ToString(tegn) +"  frekvens: " + Convert.ToString(frekvens) + "\n";
          return resultat;
      }
  }
  </code></pre>
  
  <p>Huffman_Tree Class:</p>
  
  <pre><code>public class Huffman_Tre
  {
      string treString;
      List&lt;Node&gt; noder = new List&lt;Node&gt;();
      public Node rot;
      public void bygg (string input)
      {
          bool funnet; //Found
          char karakter; //character
  
          for (int i = 0; i &lt; input.Length;i++) //Loops through string and sets character
              //with coresponding freqeuncy in the node list
          {   
              karakter = input[i];
              funnet = false; //default
              for (int j = 0; j&lt; noder.Count; j++)
              {
                  if (noder[j].ErTegn(karakter) == false) //if the character already exists
                  {
                      noder[j].ØkMed1(); //inkrement frequency by one
                      funnet = true; 
                      break;
                  }
              }
              if (!funnet) //if the character does not exist 
              {
                  noder.Add(new Node(karakter)); //add the character to list
              }
          }
          //Sorting node list acending by frequency
          var sortertListe = noder.OrderBy(c =&gt; c.frekvens).ToList();
  
          noder = sortertListe; 
  
          do
          {
              noder.Add(new Node((noder[0].frekvens + noder[1].frekvens), noder[0],noder[1]));
  
              //Remove the leaf nodes
              noder.RemoveAt(0);
              noder.RemoveAt(0); 
          } while(noder.Count &gt;= 2);
  
      }
  
      public Node getRot()
      {
          return rot;
      }
  
      public string visTre()
      {
  
          foreach (Node node in noder)
          {
              treString += node.Resultat();
          }
          return treString;
      }
      public bool erNull()
      {
          if (noder[0].tegn == '\0')
          {
              return true;
          }
          else
              return false;
      }
  }
  </code></pre>
  
  <p>Main Program:</p>
  
  <pre><code>private void btnKomprimer_Click(object sender, System.Windows.RoutedEventArgs e)
      {
          string input; //The string input I want to compress
          input = txtInput.Text; //initialize input to text input
          input = input.ToLower(); 
          txtOutput.Text = "";
  
          Huffman_Tre tre = new Huffman_Tre();
  
          tre.bygg(input);
  
          Node rot = new Node(tre.getRot());
  
          txtOutput.Text += rot.traverser(rot);
      }
  }
  </code></pre>