Gewurzelten Baum "abspeichern"

Michl schrieb:

Möchtest du die Objekte selbst abspeichern, oder nur die Referenzen 
darauf (also die Baumstruktur)?
Eine Möglichkeit ist, zu jedem Objekt die Referenz auf das Elternelement 
mitzuspeichern.

Das Ganze nennt sich "Objekte serialisieren". Gibt es meines Wissens 
nach für jede OOP-Sprache Mittel und Wege dazu. Tante Gugel sagt zum 
Beispiel:

c++ objekte serialisieren -->
http://www.highscore.de/cpp/boost/serialisierung.html
http://stackoverflow.com/questions/523872/how-do-you-serialize-an-object-in-c
http://home.f1.htw-berlin.de/scheibl/VCNET/Tutorium/index.htm?./Klasse/SpezielleKlasse.htm$Serialisierung

Oder auch:
http://www.boost.org/doc/libs/1_37_0/libs/serialization/doc/index.html

Michl schrieb:
> Soweit ich das beurteilen kann reichen mir Referenzen.

Michl schrieb:
> Meine SW soll eben in der Lage sein, den "Baum", der sich aus
> Usereingaben ergibt, in einer späteren Sitzung wiederherzustellen.

Wie soll das gehen wenn du nur Referenzen abspeicherst und nicht die 
dazugehörigen Daten?

Das Hauptproblem besteht darin, dass du Information auf dem File 
benötigst, welche dir eine Rekonstruktion der Verpointerung ermöglicht.
Denn das Problem ist natürlich, dass dir die Pointer an sich nicht 
weiter helfen, denn im nächsten Programmlauf haben die keine Bedeutung 
mehr.

Wenn es (in der Implementierung) schnell gehen muss, dann mach ich das 
gerne so, dass ich in der Datenstruktur einen 'reserved' Wert bei jedem 
Knoten habe. Vor dem Speichern werden die Knoten durchnummeriert. Beim 
Schreiben aufs File wird dann bei jedem Knoten die Nummer seines Vaters 
im File mit vermerkt. Wenn ich dafür sorge, dass beim Schreiben immer 
die Väter vor den Söhnen gespeichert werden, dann geht das beim Lesen 
wieder ganz einfach: nächsten Knoten samt Vaternummer einlesen. Mit 
einer Find-Funktion den Vater-Knoten im bisherigen Baum suchen und an 
den wird dann der gerade gelesene Knoten angehängt.
Die Schreibroutine ist also eine einfache Rekursive Funktion, während 
die Lese-Routine eine einfache Schleife darstellt, die jeden gelesenen 
Knoten anhand der Vaternummer in den Baum wieder an der richtigen Stelle 
einhängt.

Eine andere Möglichkeit wäre, wie Amateur schon angesprochen hat, die 
Schreibroutine rekursiv auszuführen, wobei jeder Knoten auch die Anzahl 
seiner Kinder mitspeichert (oder im Falle eines binären Baumes, dann 
eben die Information, dass es dieses Kind nicht gibt). Dann kann man die 
Leseroutine symetrisch dazu ebenfalls rekursiv ausführen.

Aber egal wie: Dreh und Angelpunkt besteht darin, dass die 
Schreibroutine Zusatzinformation auf dem File ablegen muss, die den 
Leseprozess leitet.

Udo Schmitt schrieb:
> Michl schrieb:
>> Meine SW soll eben in der Lage sein, den "Baum", der sich aus
>> Usereingaben ergibt, in einer späteren Sitzung wiederherzustellen.
>
> Wie soll das gehen wenn du nur Referenzen abspeicherst und nicht die
> dazugehörigen Daten?

Das war ja die Frage. Wenn er die Objekte als Stammdaten hat und der 
User diese Objekte nur anordnet, dann genügen die Referenzen. Wenn der 
User allerdings die Objekte selbst erstellt und diese abgespeichert 
werden sollen, dann sollte er serialisieren.

Wenn das ein Binärbaum ist und u.U. etwas Platzverschwendung in Ordnung 
ist, kann der Baum auch sehr einfach in ein Array gepackt werden (Zeiger 
werden da nicht benötigt) und dann mit den üblichen Dateifunktionen 
gespeichert werden.

Übliche Formeln dafür wären:
Wenn der Index des Vaterknotens n ist, dann stehen die Kinder an den 
Positionen 2*n+1 bzw. 2*n+2.
In die andere "Richtung": Index des Kindes = n, dann ist der Vaterknoten 
bei (n-1)/2
Für andere Bäume bzw. allgemein kann man's hier nachlesen
http://en.wikipedia.org/wiki/K-ary_tree