Binärbäume iterativ speichern

[new32]

Da ich oft genug von Problemen deiser Art gelesen habe und mit den meisten iterativen Lösungen (virtuellen Stack anlegen...) unzufrieden war, hier meine Lösung für dieses Problem:

Der Typ auf dem der Baum basiert:

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;

Die rekursive Lösung:

Code:

int DBRSave(DB *db, FILE *f){      //kann zu Stacküberlauf führen!
   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;
}

Sollte sich selbst erklären.


Die iterative Lösung

Code:

int DBISave(DB *db, FILE *f){
   size_t lng;
   int bigPart=0;
   DB *prevDB;
   while(1){
      do{
         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);
         }
      } while(db->sChild && (db=db->sChild)); //Zweite "Bedingung" wichtig!
      prevDB=NULL;
      while(db->parent && 
               (prevDB==db->bChild ||
                !db->bChild)
          ){
         prevDB=db;
         db=db->parent;
      }   
                
      if(!db->parent){
         if(bigPart) return 0;
         else bigPart=1;
      }
      db=db->bChild;
   }
}

Zum Ablauf:
Zu erst arbeitet sich die Funktion von der Wurzel bis zum kleinsten Eintrag vor.
Dann geht es wieder hoch. So lange bis ein größerer Eintrag (bChild) gefunden wurde.
Von diesem Eintrag ausgehend, wieder zum kleinsten Eintrag dieses Zweiges.
Dieser Vorgang wird solange wiederholt, bis alles abgearbeitet ist!

Vorteile:
Schneller, weniger Arbeitsspeicher, kein Stacküberlauf

Nachteil:
Schwieriger zu verstehen




Und zu guter Letzt die Delphi-Version:

Delphi-Quellcode:

type
   size_t=ulong;
   lpDB=^DBr;
   DBr = record         //a simple DataBase
     parent:lpDB;      //if(parent==0) "root of the db"
     sChild, bChild:lpDB;   //sChild->key < key; bChild->key > key
     key:PCHAR;
     value:PCHAR;
   end;

function DBISave(db:lpDB; var f:FILE):integer;
var
lng:size_t;
bigPart:integer;
prevDB:lpDB;
help:boolean;
begin
   bigPart:=0;
   while true do begin
      repeat
         if(db.key<>nil) and (db.value<>nil) and (strlen(db.key)>0) and (strlen(db.value)>0) then begin
            lng:=strlen(db.key);
            blockwrite(f, lng, sizeof(size_t));
            blockwrite(f, db.key^, lng);

            lng:=strlen(db.value);
            blockwrite(f, lng, sizeof(size_t));
            blockwrite(f, db.value^, lng);
         end;
         if db.sChild<>nil then begin db:=db.sChild; help:=true end else help:=false;
      until help=false;
      prevDB:=nil;
      while((db.parent<>nil) and
               ((prevDB=db.bChild) or
                (db.bChild=nil))
          ) do begin
         prevDB:=db;
         db:=db.parent;
      end;

      if(db.parent=nil) then begin
         if(bigPart=1) then begin
           result:=0;
           exit;
         end else bigPart:=1;
      end;
      db:=db.bChild;
   end;
end;