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