Baumartige Struktur in der richtigen Reihenfolge berechnen

[Möbius]

Guten Tag

Der Zweck Deiner Funktion ist nicht ganz klar.
Aber beim erstellen des Baums (also Bottom Up) und berechnen Deiner Werte soltest Du Deinem Baum bzw. seinen Knoten und Blättern einen Zeiger auf den Parent (Elternknoten) Node spendieren.
So kommst Du einfach vom Blatt zur Wurzel.
Der Rückweg ist allerdings etwas schwieriger (falls nötig). Du müsstest bei Deinen Eingabedaten einen Zeiger vermerken wenn Du Dich auf den "Vorwärtsweg" durch den Baum machst (und die Berechnungen durchführst) und so von den Eingangsdaten erneut zum gleichen Blatt/Knoten gelangst (ohne die Berechnung erneut durchzuführen).

So sollte es klappen

LLG
Möbius

[cltom]

Zitat von Möbius:

Guten Tag

Der Zweck Deiner Funktion ist nicht ganz klar.
Aber beim erstellen des Baums (also Bottom Up) und berechnen Deiner Werte soltest Du Deinem Baum bzw. seinen Knoten und Blättern einen Zeiger auf den Parent (Elternknoten) Node spendieren.
So kommst Du einfach vom Blatt zur Wurzel.
Der Rückweg ist allerdings etwas schwieriger (falls nötig). Du müsstest bei Deinen Eingabedaten einen Zeiger vermerken wenn Du Dich auf den "Vorwärtsweg" durch den Baum machst (und die Berechnungen durchführst) und so von den Eingangsdaten erneut zum gleichen Blatt/Knoten gelangst (ohne die Berechnung erneut durchzuführen).

So sollte es klappen

LLG
Möbius

Danke für Deine Überlegungen. Ganz hab ich sie nicht verstanden.

Die Struktur des Baumes ist erst einmal dadurch definiert, dass jeder Zweig einen Ziel-Zweig hat, in den er mündet und einen Wert, an welcher Position im Zielzweig er mündet.


Im letzten Beispiel:

BranchID 1 2 3 4 5 6 7
TargetBranchID 2 3 4 4 4 5 6
TargetPosition a b c d e f g

mit c>e, weil Zweig 3 vor Zweig 5 auf 4 trifft. Der Rest im Grunde beliebig. Und beim Stamm (4) selber ist der Zielwert (d) irrelevant (Null oder die Gesamtzahl des Zweiges).

Das Parent mitgeben hatte ich auch überlegt, ist aber nicht eindeutig für die Struktur, weil in dem Beispiel der Zweig 4 ja aus zwei weiteren Zweigen gespeist wird. Es könnte auch der Fall eintreten, dass ein Zweig selber viele (10+) Zweige hat, die auf ihm sitzen:

BranchID 1 2 3 4 5 6 7
TargetBranchID 7 7 7 7 7 7 7


Hier münden alle Zweige auf 7. 7 könnte also kein eindeutiges Parent haben. Es wäre eine Liste von Parents. Hilft das?

[stahli]

Ich verstehe das Problem als ähnlich einem Puzzle...

Die Zweige liegen in einer eindimensionalen Liste und müssen als Baum interpretiert werden - richtig?
Erst dann hat man eine Baumstruktur, von der Gausi ausgeht - auch richtig?

Vielleicht kannst Du ja Deine Datenstruktur gleich komplett so ändern, dass Du verkettete Listen verwendest?
So hättest Du direkt eine Wurzel, von der Du ausgehen kannst.

[cltom]

Zitat von stahli:

Ich verstehe das Problem als ähnlich einem Puzzle...

Die Zweige liegen in einer eindimensionalen Liste und müssen als Baum interpretiert werden - richtig?
Erst dann hat man eine Baumstruktur, von der Gausi ausgeht - auch richtig?

Vielleicht kannst Du ja Deine Datenstruktur gleich komplett so ändern, dass Du verkettete Listen verwendest?
So hättest Du direkt eine Wurzel, von der Du ausgehen kannst.

richtig und richtig. im Grunde hab ich keine Baumstruktur, sondern nur eine List von Verzweigungen.

Verkettete Listen - hmm, da hat jedes Element genau einen Vorgänger/Nachfolger. Das hab ich aber nicht. Ein Element kann nur einen Nachfolger, aber "beliebig" viele Vorgänger haben.

Die Datenstruktur ist in der Tat aber völlig offen. Es ist letztlich ein Haufen Objekte, die einige ihrer Werte an ein nächstes Objekt übergeben.

[stahli]

Du kannst ja einem Objekt eine Liste spendieren, in der es beliebige andere Objekte (Vorgänger oder Nachfolger ist egal bzw. nur eine Frage der Benennung) verwalten kann.

I.d.R. Geht man von einer Wurzel aus, die sich immer weiter verzweigt. Die Wurzel hat dann weitere Kinder, die ihrerseits wieder weitere Kinder haben. So kannst Du von der Wurzel aus alle Kinder erreichen. Wenn die Kinder wiederum ihren Parent kennen, kannst Du in beide Richtungen navigieren.

Was Du beschreibst, ist eigentlich genau solch eine Struktur, nur eben von Rechts nach links abgebildet anstatt üblicher von links nach rechts oder oben nach unten.

[cltom]

Danke für Eure Tipps. Hab das noch eine Weile durchgekaut und bin auf folgende Lösung gekommen falls mal jemand auf ein ähnliches Thema stößt.

Grundidee:

1. den Stamm finden (der sollte als Zielzweig sich selber haben)
2. für jeden Zweig zu seinem nächsten Zweig gehen
3. prüfen, ob man damit auf dem Stamm gelandet ist. Wenn ja, dann den Zweig aus der zu prüfenden Liste herausnehmen und in der Reihenfolge notieren. Wenn nein, dann wieder zurück zu 2.
4. solange wiederholen bis alle Zweige zum Stamm geführt haben

Weiß nicht, ob es die eleganteste Methode ist, aber es braucht keine zusätzlichen Eigenschaften im Objekt, die ich dann wieder in die Datenbank aufnehmen müsste.

Funktionieren tut es mit zwei Arrays, die ich aus den Zweigen erstelle. Einem mit den "Wanderregeln", einem mit der aktuellen Position.