Binärer Baum, Blätter durchegehen

[Quolz]

Hallo Leute,

Ich habe follgendes Problem, welches der Problematik eines Binären Baum ähnlich kommt:

Ich hab mehrere Objekte welche eine variable Anzahl Unterobjekte besitzen können. Diese Unterobjekte können wiederum eine variable Anzahl Unterobjekte besitzen usw. Nun sollte ich alle Objekte durchlaufen und von jedem Objekt den Namen in ein Textfile speichern.

Ich hab mir das nun irgendwie so vorgestellt:

Delphi-Quellcode:

for i:= 0 to myObject.count-1 do 
begin
  with myObject.Objects[i] do
  begin
    for z:= 0 to count-1 do
    begin
      //usw. ich sollte das irgendwie dynamisch machn, da es eine variable Anzahl Unterobjekte hat
    end;
  end;    
end;

Wäre für einen Denkanstoss dankbar.

~Quolz~

[DGL-luke]

Rekursion, das Wort heißt Rekursion!

Delphi-Quellcode:

procedure WriteObject(Obj: TMyObjectte; AStream: TFileStream);
var i,s: Integer;
   
begin
  s := length(Obj.Name);
  AStream.Write(s,sizeof(s));
  AStream.Write(Obj.Name[1],s);
  for i := 0 to Obj.ChildCount-1 do
    WriteObject(Obj.Childs[i],AStream);
end;

[Quolz]

Super das wars, danke vielmals!

[Der_Unwissende]

Zitat:

Zitat von DGL-luke

Rekursion, das Wort heißt Rekursion!

Rekursion ist nur der elegante, intuitive und einfachere Weg. An sich kannst Du einfach nach Traversieren suchen (also google), da solltest Du schnell recht viele Arten finden einen Baum (oder andere Strukturen) zu durchlaufen. Alle lassen sich immer sehr einfach und elegant mittels Rekursion lösen. Was Du aber auch wissen (im Hinterkopf behalten) solltest ist, dass Rekursion immer dazu neigt deinen Stack zu füllen.
Jeder rekursive Aufruf der gleichen Methode unterbricht an der entsprechenden Stelle die weitere Abarbeitung und führt erst den Aufruf der Methode komplett durch. Da hier jedoch irgendwann eine Rückkehr stattfinden muss, wird eben der Zustand der Methode vorher auf den Stack geschoben und bei Rückkehr wieder vom stack genommen. Lange Rede kurzer Sinn, ist Dein Baum nur breit/hoch genug, so kommt es schnell mal zum Stack-Overflow.

Deshalb ist der weniger schönere, weniger elegantere und auch weniger intuitivere Weg nicht aussen vor zu lassen. Du kannst einfach eine Liste verwenden, in der Du alle noch zu betrachtenden Knoten speicherst. Am Anfang packst Du einfach die Wurzel rein. Nun gehst Du in eine Schleife, die solange ausgeführt wird, bis die Liste leer ist. Hier entnimmst Du einfach das erste Element, trägst den Namen in die Namensliste ein und schaust ob der Kinder hat. Ist dem der Fall, werden die Kinder einfach in die Knotenliste gepackt. Dabei verläst Du nie die Methode und der Stack bleibt auch bei noch so vielen Zugriffen unberührt (wobei ich einfach davon ausgehe, dass Du die Knoten auf dem Heap erzeugst :-))

Delphi-Quellcode:

procedure WriteObjects(Root: TMyObject; out names: TStrings); 
var nodes: TObjectList;
    currentNode: TMyObject;
    i: Integer;
begin
  names := TStringList.Create;
  nodes := TObjectList.Create;
   
  if assigned(Root) then
  begin
    nodes.add(root);
 
    // hier die eigentliche Schleife, solange noch Knoten in der liste sind   
    while nodes.Count > 0 do
    begin
      // ersten knoten aus der Liste entfernen (ohne ihn frei zugeben!)
      currentNode := TMyObject(nodes.extract[nodes.first]);
      // Namen speichern
      names.add(currentNode.Name);
      // Kinder in die Liste der Knoten einfügen
      if currentNode.ChildCount > 0 then
      begin
        for i := 0 to currentNode.ChildCount - 1 do
        begin
          nodes.add(currentNode.Children[i]);
        end; 
      end; 
    end; 
  end; 
end;

Gruß Der Unwissende

[Flax]

Ist der Umstand wirklich gerechtfertig? Für einen Rücksprung wird doch nur sehr wenig Speicher benötigt im Stack. Da müssen schon über 100erte Von Verschachtelungen stattfinden, damit das Probleme macht.

Ich würde erst mal die Rekursion testen und mich fragen, wie weit meine Bäume verzweigt sind.

Den Stack verfügtbaren max. Stack könnte man auch erhöhen in seinem Projekt.