Baum-Interator implementieren

[VizeTE]

Zitat:

Zitat von Hawkeye219

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.

Punkt 2 gefällt mir nicht so richtig. Wenn ich den Knoten auch zeitgleich in einem anderen Baum verwende kann ich mir nicht den rechten Nachbarn des zweiten Baumes merken.

Daher habe ich mir überlegt, daß auf dem Stack nicht der Knoten selbst abgelegt wird sondern dessen Index. So kann ich, wenn ich den nächsten Nachbarn benötige, einfach den Index + 1 Nachbarn verwenden. (und ggf. Maßnahmen ergreifen falls es den nicht gibt)

Da muß ich dann aber wiederrum höllisch aufpassen, daß nicht während des Vorgangs eine Knoten eingefügt wird, der meinen Index durcheinander bringt. Vielleicht sollte ich doch den Knoten in den Stack schreiben und der Knoten gibt dann seinen aktuellen Index zurück. Wenn der Knoten aber in mehreren Bäumen verwendet wird weiß der Knoten auch wieder nicht welchen Index er zurückgeben soll. Da müßte ich noch einen Bezug zum Kontext herstellen können - man ist das kompliziert :zwinker:

Irgendwo habe ich mal gelesen, daß man dafür sogenannte "robuste Iteratoren" implementieren kann. Der registriert sich beim Baum und bekommt dann Infos wenn ein Knoten eingefügt bzw. gelöscht wird. So kann dann entsprechend auf den verschobenen Index reagiert werden.

Ansonsten entspricht dein Versuch auch etwa meinen Vorstellungen.

[VizeTE]

Zitat:

Zitat von r2c2

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

Wahrscheinlich würde es auch mit einer Rekursion gehen. Ich wollte aber gern den Code aus dem Baum raushalten. Außerdem gehts mir auch um den Lerneffekt ;)

Zitat:

Zitat von r2c2

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

In diese Richtung gingen auch meine ersten Überlegungen. Bei dieser Implementierung gibt es aber das Problem, daß die rekursive Suche abgebrochen wird wenn ein Element gefunden wurde. Du schreibst ja in deinem Code-Beispiel selbst: // Suche abbrechen und Node zurückliefern
Wenn ich jetzt also ein Element gefunden habe, welches meinen Kriterien entspricht und ich dann aber weitersuchen möchte ob es noch mehr davon gibt dann beginnt ja eine neue Rekursion. So kann ich weiter nach unten in den Baum suchen aber beim aufsteigen komme ich dann genau zu meinem Problem. Wo weitermachen wenn das Parent-Element nicht seine Nachbarn kennt?

[VizeTE]

Zitat:

Zitat von marabu

wie ein einziges unterschlagenes Wort den Sinn entstellen kann

Das ist vielleicht sowas wie "der Fluch des Programmierers" ;)
Der Teufel liegt eigentlich immer im Detail.

[Hawkeye219]

Möchtest Du wirklich die Knoten in mehreren Bäumen benutzen oder nur die Daten? Bei einer sauberen Trennung zwischen der Verwaltung (Knoten) und den Daten (mit einem Verweis auf die Daten in den Knoten) sollte es doch möglich sein, die Daten mehrfach zu nutzen. Bei der Verwendung von Interfaces bekommst Du die Referenzzählung sogar umsonst. :wink: Von der mehrfachen Verwendung der Knoten würde ich abraten, weil es meiner Meinung nach die Datenstruktur allzu sehr einschränkt.

Gruß Hawkeye

[VizeTE]

Zitat:

Zitat von Hawkeye219

Möchtest Du wirklich die Knoten in mehreren Bäumen benutzen oder nur die Daten?

Eigentlich nur die Daten.
Ich habe mir die Klassen für die Knoten erstellt und davon meine Daten-Klassen abgeleitet. Vielleicht ist es wirklich flexibler wenn ich diese beiden Dinge voneinander trenne.

[r2c2]

Zitat:

Zitat von VizeTE

Außerdem gehts mir auch um den Lerneffekt ;)

Das is immer gut. :thumb:

Zitat:

Zitat:

Zitat von r2c2

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

In diese Richtung gingen auch meine ersten Überlegungen. Bei dieser Implementierung gibt es aber das Problem, daß die rekursive Suche abgebrochen wird wenn ein Element gefunden wurde. Du schreibst ja in deinem Code-Beispiel selbst: // Suche abbrechen und Node zurückliefern
Wenn ich jetzt also ein Element gefunden habe, welches meinen Kriterien entspricht und ich dann aber weitersuchen möchte ob es noch mehr davon gibt dann beginnt ja eine neue Rekursion. So kann ich weiter nach unten in den Baum suchen aber beim aufsteigen komme ich dann genau zu meinem Problem. Wo weitermachen wenn das Parent-Element nicht seine Nachbarn kennt?

Das macht ja mein Trick-17. Indem ich mit die Nummer der des Iterationsknotens merke kann ich durch anhalten davor/danach wieder an die Stelle zurrückkehren und weitermachen. Besonders performant is das nicht; sollte aber funktionieren. Ansonsten werd ich den Thread hier auch weiterverfolgen, da ich auch grad was mit nem Baum anstelle...

mfg

Christian