Baum-Interator implementieren

[VizeTE]

Hallo,

ich habe ein Baumstruktur und möchte für diese Struktur einen Iterator entwickeln.
Prinzipiell ist mir klar wie ein Iterator funktioniert.
Es soll ein externen Iterator werden, also der Klient steuert den Ablauf.

Was mir noch nicht so richtig klar ist, ist die Implementation des Methode "Next", also der Aufruf des nächsten Elements.

Ich stelle mir das folgendermaßen vor:
- ich übergebe das root-Element
- der erste Aufruf von Next gibt des erste Kind zurück
- der nächste Aufruf gib das erste Kind des Kindes zurück, sofern vorhanden
=> somit wird in die Tiefe gegangen
- hat das aktuelle Kind keine Kinder so wird der nächste Nachbar/Bruder zurückgegeben

Soweit ist mir das erstmal klar. Ich bin mir aber noch nicht sicher wie ich folgende
Situation abbilde:

Der Iterator steht aktuell auf einem Kind, welches das Letzte des Eltern-Elements ist.
Jetzt wird "Next" aufgerufen. Da das aktuelle Kind keine eigenen Kinder hat und selbst
das Letzt des Elternelements ist so muß "Next" den Bruder des Eltern-Elements zurückgeben.

Genau hier liegt mein Problem. Welche Möglichkeiten gibt es den Bruder des Eltern-Elements
herauszubekommen. Mir fallen 2 Möglichkeiten ein, die mir beide nicht 100%ig gefallen.

1. Ich gehe zum Eltern-Element und frage dessen Eltern-Element nach der Liste seine Kinder.
In dieser List suche ich mein Eltern-Element (von dem ich den Bruder haben möchte) und nehme
den Nachfolger. - Hat den Nachteil, daß hier ganz schön viel traversiert werden muß.

2. Beim einfügen des Elements in den Baum speichert dieses Element einen Pointer auf den Nachfoger.
- Diese Lösung hat aber den Nachteil, daß einiges mehr an Verwaltungsaufwand entsteht. Zudem kann ich dann das Element auch nicht in 2 unterschiedlichen Bäumen verwenden.


Ich hoffe ich habe mich nicht zu kompliziert ausgedrückt und ihr habt ne tolle Idee für mich :zwinker:
Schon mal Vielen Dank - Daniel

[Dax]

Wenn du einen Baum hast, nutzt du doch hoffentlich verlinkte Listen für die Elemente? Dann wäre der Bruder ganz einfach rauszubekommen: Parent.Next ;) Dabei speichert Parent in einem Element das Elternelement, Child das Kindelement, Next das nächste und Previous das vorherige Element^^

[BlackJack]

Zitat:

Zitat von VizeTE

Der Iterator steht aktuell auf einem Kind, welches das Letzte des Eltern-Elements ist.
Jetzt wird "Next" aufgerufen. Da das aktuelle Kind keine eigenen Kinder hat und selbst
das Letzt des Elternelements ist so muß "Next" den Bruder des Eltern-Elements zurückgeben.

wenn du .Next eines Knotens aufrufst, der keine Kinder hat, dann sollte doch eigentlich nil zurückgegeben werden, oder? wenn man dann einfach nen anderen knoten (z.b. nachbarn) zurückgibt, dann denkt man doch, der Knoten selber hätte Kinder.

[Hawkeye219]

Hallo Daniel,

Du könntest in einem vorbereitenden Schritt mit einer rekursiven Routine den Baum durchlaufen und dabei Verweise auf alle besuchten Knoten in einem (dynamischen) Array ablegen. Die Next-Routine muß dann dieses Array nur noch sequentiell abarbeiten.

Gruß Hawkeye

[VizeTE]

Zitat:

Zitat von Dax

Wenn du einen Baum hast, nutzt du doch hoffentlich verlinkte Listen für die Elemente? Dann wäre der Bruder ganz einfach rauszubekommen: Parent.Next ;) Dabei speichert Parent in einem Element das Elternelement, Child das Kindelement, Next das nächste und Previous das vorherige Element^^

Bisher keine verlinkte Liste. Das war je meine Idee in Punkt 2 des Eingangs-Posts. Gibt es eine fertige verlinkte Liste in Delphi 7 oder muß ich das selbst implementieren?
Wie würde das dann laufen. Wo werden die Links gespeichert? Ich möchte die Links ungern in den Elementen speichern da ich diese dann nicht in mehreren Bäumen gleichzeitg verwenden kann.
Wenn sich das ohne viel Verwaltungsaufwand lösen läßt ist das sicher eine gute Idee.

Zitat:

Zitat von BlackJack

wenn du .Next eines Knotens aufrufst, der keine Kinder hat, dann sollte doch eigentlich nil zurückgegeben werden, oder? wenn man dann einfach nen anderen knoten (z.b. nachbarn) zurückgibt, dann denkt man doch, der Knoten selber hätte Kinder.

Nicht ganz. Ich möchte dann nicht den Nachbarn des aktuellen Knotens sondern den Nachbarn des Elternknoten zurückgeben, sofern vorhanden. Es handelt sich um einen Baum und nicht um eine flache Liste.

Zitat:

Zitat von Hawkeye219

Du könntest in einem vorbereitenden Schritt mit einer rekursiven Routine den Baum durchlaufen und dabei Verweise auf alle besuchten Knoten in einem (dynamischen) Array ablegen. Die Next-Routine muß dann dieses Array nur noch sequentiell abarbeiten.

Das ist ne Idee. Ich befürchte aber, daß das zu viel Zeit kostet wenn die Bäume sehr groß werden. - Sorry, daß ich hier so negativ eingestellt bin. :zwinker:


Aber mir ist da auch noch was eingefallen. Was haltet ihr davon, wenn man innerhalb des Iterators einen Stack verwaltet. Jedes mal wenn ich eine Ebene in die Tiefe gehe wird ein neues Element auf den Stack gelegt, welches Informationen enthält, welchen Index das Element hat (von dem ich komme). Wenn ich dann wieder eine Ebene aufsteige bekomme ich so einfach den Index des Nachfolgers heraus und lösche das oberste Stack-Element.

[marabu]

Hallo Daniel,

Zitat:

Zitat von VizeTE

Was haltet ihr davon, wenn man innerhalb des Iterators einen Stack verwaltet.

jetzt bist du auf dem richtigen Weg.

Nachtrag: Bei weiterem Nachdenken komme ich zu dem Schluss, dass ich viel zu viele Annahmen mache, wo von deiner Seite fast keine Information über die Implementierung der Baumstruktur vorliegt. Ob du den Stack einsetzt oder besser mit Markierungen arbeitest, das hängt zum Teil auch von der Implementierung der Knoten ab.

Grüße vom marabu

[VizeTE]

Zitat:

Zitat von marabu

Nachtrag: Bei weiterem Nachdenken komme ich zu dem Schluss, dass ich viel zu viele Annahmen mache, wo von deiner Seite fast keine Information über die Implementierung der Baumstruktur vorliegt. Ob du den Stack einsetzt oder besser mit Markierungen arbeitest, das hängt zum Teil auch von der Implementierung der Knoten ab.

Die Definition der Baumstruktur liegt vollständig in meiner Hand. Von daher bin ich dort flexibel. Prinzipiell finde ich es gut wenn man die einzelnen Knoten auch in mehreren Bäumen verwenden kann. Ich weiß nicht genau wie du dir die Umsetzung mit Markierungen gedacht hast. Würde ich dann den Knoten selbst als solchen markieren, daß ich genau an diesem abgestiegen bin?
Könntest du mal kurz Umreißen wie du das Problem mit Markierungen angehen würdest?

Danke!

[Hawkeye219]

Hallo Daniel,

eine Markierung der Knoten hätte meiner Meinung nach den Nachteil, daß bei Änderungen im Baum alle Knoten zurückgesetzt werden müssen. Da Du offenbar mit einer großen Zahl von Knoten arbeitest, ist dies eine sehr teure Operation.

Ist der zusätzliche Aufwand zur Erstellung einer linearen Liste von Knoten wirklich so groß, wenn Du sowieso alle Knoten im Baum besuchen möchtest? Bei riesigen Bäumen fällt da eher der zusätzlich benötgte Speicherplatz ins Gewicht. Das ist dann der Preis, den Du für eine simple Next-Funktion bezahlst.

Dein Vorschlag mit dem Stack läßt sich sicher umsetzen, ohne die Knoten mit zusätzlichen Daten zu belasten. Der folgende Code ist ein Versuch(!), der von folgenden Voraussetzungen ausgeht:

1. Jeder Knoten besitzt eine Methode FirstChild, die einen Zeiger auf das erste Kind des Knotens liefert.
2. jeder Knoten besitzt eine Methode NextSibling, die einen Zeiger auf den rechten Bruder des Knotens liefert.
3. Es existiert ein Stack mit den Methoden Push, Pop und IsEmpty.

Delphi-Quellcode:

type
  TIterator = class
  private
    // Zeiger auf den nächsten zu liefernden Knoten
    FNext : TNode;
    // Zeiger auf die Wurzel des Baums
    FRoot : TNode;
  public
    // Konstruktor
    constructor Create (aRoot: TNode);
    // liefert den nächsten Knoten
    function Next: TNode;
    // Setzt den Iterator zurück
    procedure Reset;
  end; // TIterator

consturctor TIterator.Create (aRoot: TNode);
begin
  FRoot := aRoot;
  Reset;
end;

function TIterator.Next: TNode;
begin

  // Zeiger auf den nächsten abzuarbeitenden Knoten des Baums liefern
  Result := FNext;
  
  // Nächsten abzuarbeitenden Knoten ermitteln, falls noch Knoten vorhanden sind
  if Assigned(FNext) then

    // Prüfe, ob der aktuelle Knoten Kinder besitzt
    if Assigned(FNext.FirstChild) then
      begin
      
        // Der aktuelle Knoten besitzt Kinder.
        // Aktuellen Knoten im Stack speichern, Zeiger auf das erste Kind holen
        Stack.Push (FNext);
        FNext := FNext.FirstChild;
        
      end
    else
      repeat
        begin
      
          // Falls der aktuelle Knoten einen Bruder besitzt, ist dies der nächste Knoten
          FNext := FNext.NextSibling;
          if Assigned(FNext) then
            Break;

          // Der Teilbaum wurde komplett abgearbeitet, zurück zur vorigen Ebene
          if Stack.IsEmpty then
            FNext := NIL
          else
            FNext := Stack.Pop;
          
        end; // while Assigned()
      until (FNext = NIL);

end;

procedure TIterator.Reset;
begin
  FNext := FRoot;
end;

Ich hoffe, es sind nicht allzu viele Fehler drin.

Gruß Hawkeye

[r2c2]

Muss es unbedingt n Iterator sein? Reichts vielleicht auch, einfach nur ne rekursive Funktion zu benutzen:

Delphi-Quellcode:

//Pseudocode:
TNode = class
private
  ...
  FChildren: TNodeList; // Typed TObjectList
public
  ...
  property Chrildren: TNodeList read ... write ...;
end;

TBaum = class
private
  ...
  FRoot: TNode;
public
  ...
  procedure HandleAllNodes(AProc: <CallBackFunction>);
  ...
  property Root read FRoot write FRoot;
end;

procedure TBaum.HandleAllNodes(...);
begin
  // rekursiv alle Nodes durchgehen und die CallBackFunction aufrufen
end;

Wenn du unbedingt n Iterator haben willst, kannst du das so auch machen:

Delphi-Quellcode:

TIterator = class
private
  ...
  FCurrentNode: Integer; // Nummer des Knotens, der zuletzt ermittelt wurde
  FCounter: Integer; // Counter für Next;
public
  ...
  procedure Reset;
  function Next: TNode;
end;

function TIterator.Next: TNode;
begin
  // solange FCounter <= TCurrentNode
  // rekursiv durchsuchen
  // wenn FCounter = TCurrentNode
  // Suche abbrechen und Node zurückliefern
end;

Is vielleicht nicht die Beste Lösung, aber ne einfache... Oder hab ich was vergessen/falsch verstanden?

mfg

Christian

[marabu]

Hallo Daniel,

Zitat:

Zitat von marabu

Ob du den Stack einsetzt oder besser mit anderen Markierungen arbeitest, das hängt zum Teil auch von der Implementierung der Knoten ab.

wie ein einziges unterschlagenes Wort den Sinn entstellen kann. Bei Verwendung eines Stacks hast du bereits einen marking algorithm. Durch meinen Nachtrag wollte ich nur verhindern, dass mein erster Kommentar dich von weiterem Literaturstudium abhält. Grundsätzlich ist der Ansatz über den Stack sehr verbreitet. Andere marking Techniken spielen eher in allgemeinen Graphen eine Rolle.

Grüße vom marabu