Binärbaum in eine Datei speichern

[Teilzeitberlinerin]

Hallo alle zusammen,

ich habe einen Binärbaum, auf dessen Knoten sich je eine dynamische Liste befindet, programmiert. Das ganz soll als "Personendatenbank" funktionieren und daher wäre es auch sinnvoll,wenn ich alle diese Daten speichern und auch wieder einlesen könnte.

Ich kann mir noch nicht so richtig vorstellen, wie ich das realisieren soll.
Ich will gerne ein Typdatei von dem RECORD der Liste anlegen und dann den Baum Schritt für Schritt durchlaufen und alle Listeneinträge in die Datei einschreiben.

Geht das so einfach oder würdet ihr was anderes vorschlagen, was einfacherer zu programmieren ist ?!?! Wie kann ich aus der Datei wieder alles in den Binärbaum eintragen ?

Ich danke euch !

[shmia]

Du kannst einen binären Baum auch in einem Array ablegen.
Der Baum sollte aber schon ausgeglichen sein, sonst wird das Array sehr gross.
Das heisst jetzt aber nicht, dass du wirklich ein Array brauchst; es kommt darauf an, den Baum auf die
richtige Art zu traversieren.

Beispiel

Code:

-
   A
  / \
 B   C

gibt ein Array mit:
A|B|C
Unter B und C können nun jeweils wieder 2 Knoten sein, dann hat Array 7 Einträge.
In dem Buch wird das erklärt:
http://www.amazon.de/Algorithmen-Rob...14/ref=sr_1_12

[Namenloser]

Denk mal an XML. Was du brauchst ist eigentlich nur ein Start-Tag und ein End-Tag. Du musst es ja nicht mit XML machen, aondern kannst das ganze auch binär speichern.
Meine Idee wäre folgende:

Code:

 .--------------------------------------------.
 V                                            |
 [Länge der Daten][Daten][ggf. öffnendes Tag] ' [schließendes Tag]

Das Öffnen- und Schließen-Tag wären im einfachsten Falle Bytes mit vorgegebenem Wert, z.B. 255 für Öffnen und 0 für Schließen.
Das müsste mit Streams ( :love: ) sehr gut lösbar sein.

[mkinzler]

Oder Daten von Index (Baum trennen)

[Namenloser]

Klar, das geht auch. Wobei ich denke, dass meine Methode schneller ist, wenn der gesamte Baum eingelesen werden muss.

[new32]

Code:

typedef struct _DB {         //a simple DataBase
   struct _DB *parent;      //if(parent==0) "root of the db"
   struct _DB *sChild, *bChild;   //sChild->key < key; bChild->key > key
   char *key;
   char *value;
} DB;

static int DBRSave(DB *db, FILE *f){
   size_t lng;
   if(db->key && db->value && strlen(db->key) && strlen(db->value)){
      lng=strlen(db->key);
      fwrite(&lng, sizeof(size_t), 1, f);
      fwrite(db->key, lng, 1, f);

      lng=strlen(db->value);
      fwrite(&lng, sizeof(size_t), 1, f);
      fwrite(db->value, lng, 1, f);
   }
   if(db->sChild) DBRSave(db->sChild, f);
   if(db->bChild) DBRSave(db->bChild, f);
   return 0;
}

int DBSave(DB *root, FILE *f){
   size_t lng;
   DBRSave(root, f);
   lng=0L;
   fwrite(&lng, sizeof(size_t), 1, f);
   return 0;
}

copy&paste aus einem meiner Projekte; vielleicht bringts dir ja was.

Sorry für "C"

[bluesbear]

Es gibt zwei grundsätzliche Methoden, einen Baum Knoten für Knoten durchzugehen.
http://en.wikipedia.org/wiki/Depth-first_search
und
http://en.wikipedia.org/wiki/Breadth-first_search

Wenn man jedem Knoten eine fortlaufende ID gibt, ist es einfach, einen Baum in einer Tabelle oder wie auch immer abzuspeichern und beim einlesen zu rekonstruieren.

[Teilzeitberlinerin]

Hi,

ich danke euch für die viele Anregungen und ihr habt mir sehr weitergeholfen.
So, dann werde ich mal probieren das ganz umzusetzen.

Euch allen ein schönes Wochenende !!!