Algorithm for Huffman Tree not working

Question

I'm trying to create a Huffman Tree zipper. I started to create the List with the class Node as type, and the characters in the input string should be added to the list? But how come I cannot print the list (the char and frequency of the char in the string)?

private void btnKomprimer_Click(object sender, System.Windows.RoutedEventArgs e)
{
    int k = 0;
    string input;
    char karakter;
    input = txtInput.Text;
    input = input.ToLower();
    txtOutput.Text = "";

    List<Node> noder = new List<Node>();
    for (int i = 0; i < input.Length; i++)
    {   
        karakter = input[i];

        for (int j = 0; j < noder.Count; j++)
        {
            if (noder[j].ErTegn(karakter) == true)
            {
                noder.Add(new Node(karakter));
            }
            else
            {
                noder[j].ØkMed1();
            }
        }
    }
    while (noder[k] != null)
    {
        txtOutput.Text += noder[k].Resultat();
        k++;
    }
}

public class Node
{
    public int frekvens;
    public char tegn;

    public Node (char c)
    {
        frekvens = 1;
        tegn = c;
    }

    public void ØkMed1()
    {
        frekvens = frekvens + 1;
    }

    public bool ErTegn(char c)
    {
        if ( c == tegn)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

    public string Resultat()
    {
        string resultat;
        resultat = Convert.ToString(tegn) + Convert.ToString(frekvens) + "\n";
        return resultat;
    }
}

Answer 1

You messed up your algorithm. You must add to the noder list when the character is not in the list. The number of items (noder.Count) will always be 0 since you only add a Node in that for-loop which iterates from 0 to noder.Count:

for (int j = 0; j < noder.Count; j++) // noder.Count is always 0

Try this instead:

List<Node> noder = new List<Node>();
for (int i = 0; i < input.Length;i++)
{   
    karakter = input[i];

    bool found = false;
    for (int j = 0; j < noder.Count;j++)
    {
        if (noder[j].ErTegn(karakter) == false)
        {
            noder[j].ØkMed1();
            found = true;
            break;
        }
    }
    if(!found)
    {
        noder.Add(new Node(karakter));
    }
}
foreach(Node n in noder)
{
    txtOutput.Text += n.Resultat();
}

Answer 2

I would recommend a Dictionary instead of a list. You could store the character against the number of occurrences of it in the input text. For example:

Dictionary<char, int> occurrences = new Dictionary<char, int>();

foreach (char c in input)
{
    if (occurrences.ContainsKey(c))
    {
        occurrences[c]++;
    }
    else
    {
        occurrences[c] = 1;
    }
}

The dictionary is made up of Key/Value pairings (the types of those are set in the angle brackets). You can iterate through them by doing something like this:

txtOutput.Text = "";
foreach (KeyValuePair<char, int> pair in occurrences)
{
    txtOutput.Text += pair.Key + " : " + pair.Value + 
        Environment.NewLine;
}

This will give you an unordered list, however. To order it you can look into LINQ's OrderBy functionality, which is very cool:

http://msdn.microsoft.com/en-us/library/vstudio/bb534966%28v=vs.100%29.aspx

This means you could write the foreach line as:

foreach (KeyValuePair<char, int> pair in occurrences.OrderBy(pair => pair.Key))

This orders the dictionary by the character key.

I hope this helps and best of luck in your studies :)