Huffman Kodierung

[user10567]

Hallo, bin gerade dabei ein Programm zu programmieren,
dass die Zeichen in einer txt Datei mittels der Huffman Kodierung kodiert.
Habe jetzt in Java einen binären Baum programmiert, aber habe Probleme daraus den Code für jedes Zeichen
auszulesen.
Wie muss ich den Baum nach einem Zeichen durchsuchen um gleichzeitig den Code für ein Zeichen erstellen zu können ?
Mit meinen Ansätzen, konnte ich nie zurückverfolgen, wie oft ich links oder rechts an einem Knoten abgebogen bin.
Wäre toll, wenn mir da jmd einen Tipp geben könnte, programmiere noch nicht lange.

 

[XHelp]

Mehr als "rekursiv" fällt mir dazu nicht ein...
Wie genau hast du es schon versucht? Woran genau bist du gescheitert? Wie sieht der Code überhaupt aus?

 

[user10567]

Könntest du mal grob im Pseudocode beschreiben wie du es machen würdest ?
Ich hatte es iterativ versucht, hab dann aber irgendwann aufgehört.
Wenn ich das ganze rekursiv versuche weiß ich nicht woher ich weiß, ob ich an einem linken oder rechten Knoten bin,
ich weiß also ich ob ich eine 1 oder eine 0 zuordnen soll.

Sowas hatte ich versucht, aber ich hab schnell gemerkt, dass das keine Lösung sein kann.

....
....
if( temp.linkesKind != null ){
	System.out.println("gehe nach links");
	temp = temp.linkesKind;
	code[index++] = '0';
}
				
else if( temp.rechtesKind != null ) {
	System.out.println("gehe nach rechts");
	temp = temp.rechtesKind;
	code[index++] = '1';
}
...
...

 

[XHelp]

Es ist einfacher von den Kinder bis zum Wurzelknoten zu gehen, sonst musst du ja jeden Pfad berechnen.
Aber wenn du schon den Blattknoten hast, dann ist es einfach, da es nur einen Elternknoten gibt.

 

[user10567]

Ahh...darin hatte ich noch garnicht gedacht.
Danke, ich werde den Ansatz mal weiter verfolgen

 

[user10567]

Hab es jetzt mit der Methode geschafft,
nochmals vielen Dank.