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
Schon mal Vielen Dank - Daniel