Rekursive Struktur iterativ abfragen

[Namenloser]

Hallo Matze,

sowas habe ich vor kurzem bei meinem Brainfuck-Compiler auch gebraucht. Hat mich auch etwas Hirnschmalz und Papier gekostet - der Algorithmus, der schließlich herausgekommen ist, ist folgender (hab mal ein paar Kommentare hinzugefügt):

Delphi-Quellcode:

  TElement = class
  private
    {...}
    FParent: TElementList;
    FChildren: TElementList;
    procedure SetParent(const Value: TElementList);
  public
    {...}
    property Parent: TElementList read FParent write SetParent;
    property Children: TElementList read FChildren;
    {...}
  end;

function TBrainFuckCompiler.GetNextElement(Element: TElement): TElement;
var
  Index: integer;
begin
  Result := nil;
  if Element.Children.Count > 0 then
    // Erstes Kindelement zurückliefern, falls vorhanden
    Result := Element.Children[0]
  else while Assigned(Element.Parent) and not Assigned(Result) do
  begin
    Index := Element.Parent.IndexOf(Element);
    // Folgen auf das aktuelle Element in der gleichen Ebene noch weitere Elemente?
    if Element.Parent.Count > Index+1 then
      Result := Element.Parent.Items[Index+1];
    // Eine Ebene höher springen
    Element := Element.Parent.Parent;
  end;
end;

function TBrainFuckCompiler.GetPreviousElement(Element: TElement): TElement;
var
  Index: integer;
begin
  Result := nil;
  if Assigned(Element.Parent) then
  begin
    Index := Element.Parent.IndexOf(Element);
    if Index >= 1 then 
    begin
      // Vorgänger in gleicher Ebene
      Result := Element.Parent.Items[Index-1];
      // Von dort aus zum untersten Kind-Element vorarbeiten
      while Result.Children.Count >= 1 do
        Result := Result.Children.Last;
    end
    else 
      // eine Ebene nach oben springen
      Result := Element.Parent.Parent;
  end;
end;

Das Laufzeitverhalten ließe sich sicherlich noch verbessern, indem man IndexOf umgeht (z.B. durch Cachen des Index in den jeweilen Elementen oder durch Verwendung einer verketteten Liste).