Also - einmal von anfang an.
Du hast einen recht simplen binärbaum - der besteht nur aus Blättern und Knoten. Jeder Knoten/jeds Blatt kennt seinen Vater und weiss ob er linker oder rechter Sohn ist. Jedes Blatt enthält zusätzlich welches Zeichen es repräsentiert. Willst du nun wissen wie ein bestimmtes Zeichen repräsentiert wird, gehtst du vom Blatt zur Wurzel und für jeden Knoten den du betrittst speicherst du woher du kommst - dabei ist es eine 0 wenn du aus einem linken Sohn kommst bzw. eine 1 wenn du aus einem rechten Sohn kommst. Wenn du diese Folge aus 0llen und 1en nun umdrehst, hast du eine Anweisung wie du im Baum von der Wurzel zum Blatt kommst indem du wenn du eine 0 hast nach links, bei einer 1 nach rechts abzweigst. Diese Folge wird nun gespeichert. Dazu musst du sie in 8bit lange Teilstücke aufteilen bzw. aufkumulieren und als einzelen Bytes speichern. Beim laden gehst du umgekehrt vor. Einfach ein Byte laden, die Bits einzeln durchgehen und immer wenn du auf ein Blatt stößt das Zeichen im Blatt ausgeben, wenn das Byte zuende ist einfach ein neues laden.
Nun zum Baum. Da der Binärcode in den Abzweigungen gespeichert ist, reicht es wenn du die Struktur wieder herstellen kannst und brauchst nicht zu speichern wie jedes einzelne Zeichen codiert ist.
Angenommen wir wollen 1 byte große Zeichen Huffman codieren, dann können die Blätter alle Werte zwischen 0 und 255 annehmen. Das Verfahren das ich jetzt hier vorschlage ist nicht besonders effektiv, aber sollte einfach zu verstehen/implementieren sein. Jedem Knoten im Baum wird eine Integerzahl zugewiesen. Alle inneren Knoten bekommen eine Negative zahl, alle Blätter den Wert den sie repräsentieren (0-255). Nun wandelt man den Baum in 2 Zahlenfolgen um, die eine ist die LWR-Order der Knotennummern, die andere die WLR-Order der Knotennummern. Nun kann man das ganze recht einfach speichern:
Ersten 2 Byte: Anzahl der Zahlen in der LWR-Order.
Bytes 3-x1 LWR-Order des Baumes
x1-x2 WLR-Order des Baumes
ab x2+1: Bitstream der Datei
Damit bekommt man zuerst den Baum aus der Datei und kann dann einfach den Bitstream dekodieren.
Definition LWR-Order:
Wie üblich - Rekursiv:
LWR(Knoten x)=LWR(linker Sohn)xLWR(rechter Sohn)
Definition WLR-Order:
WLR(Knoten x)=xWLR(linker Sohn)WLR(rechter Sohn)
ist ein Sohn nicht vorhanden, so liefert die Funktion nichts zurück.
siehe dazu auch:
http://www.tutorials.de/tutorials159110.html
Alle Klarheiten beseitigt?