Binärer Baum, Blätter durchegehen

[Der_Unwissende]

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