I was pretty happy when I got my tree done but I encountered a problem with the encoding. The most frequent characters did not get the shortest binary code. My speculations are that there is something wrong with the recursive traversing function, or the initialisation of the Node List
Main Program:
public partial class MainWindow : Window
{
string kode;
public MainWindow()
{
InitializeComponent();
kode = "";
}
public double forhold(int input, int komprimert)
{
int tall1 = input * 8;
int tall2 = komprimert;
return ((double)tall1 / (double)tall2);
}
public void Traverser(Node rot, string kode) //Traverse the tree
{
if (rot != null)
{
if (rot.Venstre != null) //If the current node has a left child
{
Traverser(rot.Venstre, kode+"0");
}
if (rot.Høyre!= null) //If the current node has a right child
{
Traverser(rot.Høyre, kode+"1");
}
//Viser karakter med koresponderende binær kode
if (rot.Venstre == null && rot.Høyre == null) //If the current node is a leaf
{
rot.kode = kode;
txtOutput.Text += rot.Tegn.ToString() + ": " + kode +", ";
}
}
}
//public Node FåKodeMed //
public void btnKomprimer_Click(object sender, System.Windows.RoutedEventArgs e)
{
string input = txtInput.Text;
bool funnet; //Found
char karakter; //Character
int komprimertLengde; //Not important
txtOutput.Text = "";
komprimertLengde = 0;
if (input.Length == 0)
{
txtOutput.Text = "Du må skrive noe i tekst feltet!";
}
else
{
if (input.Length == 1)
{
txtOutput.Text = "0";
}
if (input.Distinct().Count() == 1)
{
foreach (char c in input)
{
txtOutput.Text += "0";
}
}
else
{
List<Node> noder = new List<Node>(); //List containing nodes
for (int i = 0; i < input.Length; i++) //Places nodes in the tree
{
karakter = input[i];
funnet = false;
for (int j = 0; j< noder.Count; j++)
{
if (noder[j].erTegn(karakter) == false) //Hvis tegnet allerede eksisterer
{
noder[j].økMed1();
funnet = true;
break;
}
}
if (!funnet)
{
noder.Add(new Node(karakter));
}
}
//Sorter listen etter frekvens:
var sortertListe = noder.OrderBy(c => c.Frekvens).ToList(); //Sort the list by frequency
//noder = sortertListe;
do
{
noder.Add(new Node((noder[0].Frekvens + noder[1].Frekvens),noder[0],noder[1])); //Parent node
noder.RemoveAt(0);
noder.RemoveAt(0);
noder.OrderBy(c => c.Frekvens).ToList();
}while(noder.Count >= 2);
Node rot = new Node(noder[0]);
Traverser(rot, "");
//Feilen kan ligge her
List<string> output = new List<string>();
foreach (char c in input)
{
for (int i = 0; i < sortertListe.Count;i++)
{
if(sortertListe[i].Tegn == c)
{
output.Add(sortertListe[i].kode);
break;
}
}
}
txtOutput.Text += "\n" + "\n";
foreach (string s in output)
{
txtOutput.Text += s;
}
foreach (string c in output)
{
komprimertLengde += c.Length;
}
txtOutput.Text += "\n" + "\n";
txtOutput.Text += "lengde på input: " + Convert.ToString((input.Length * 8)) + "\n";
txtOutput.Text += "Lengde på komprimert: " + Convert.ToString(komprimertLengde) + "\n";
txtOutput.Text += "Forholdet: " + Convert.ToString(forhold(input.Length,komprimertLengde));
noder.Clear();
}
}
}
Node Class:
public class Node
{
public int Frekvens {get;set;}
public string kode {get;set;}
public char Tegn {get;set;}
public Node Høyre {get;set;}
public Node Venstre {get;set;}
public Node(char c)
{
Frekvens = 1;
Tegn = c;
}
public Node(Node n)
{
Tegn = n.Tegn;
Frekvens = n.Frekvens;
Venstre = n.Venstre;
Høyre = n.Høyre;
}
public Node (int f, Node v, Node h)
{
Frekvens = f;
Venstre = v;
Høyre = h;
}
public void økMed1 ()
{
Frekvens = Frekvens + 1;
}
public bool erTegn(char c)
{
if ( c == Tegn)
{
return false;
}
else
{
return true;
}
}
}
I think the entire solution is already provided here at your other question.
The issues with your code are mostly due to the fact that your sorted list is actually sorted in the wrong order to. You might want to use
However, you could try other solutions too. Think of implementing a priority queue for example.
Note: please use English next time, even Google Translate leaves me confused :-)