Baumartige Struktur in der richtigen Reihenfolge berechnen

[cltom]

Zitat von cltom:

Zitat von stahli:

Reicht es evtl. sogar, einfach alle Records nach TargetBranchPosition zu sortieren?
Nach Deiner Skizze würde es wohl reichen (wenn man die absoluten Rechts-Werte der Linien betrachtet), aber ob das für alle Varianten gilt, ist natürlich nicht sicher.

Zumindest könntest Du darüber vermutlich die ersten Zweige finden und Dich von dort durchhangeln. Jeden schon genutzten Zweig dann aus der Liste streichen.

Guter Gedanke. Allerdings ist TargetBranchPosition kein absoluter Wert, der über alle Zweige hinweg gilt sondern nur eine relative Angabe für jeden Zweig. Ich müsste mal sehen, ob ich einen solchen absoluten Wert ableiten könnte.

Was ich inzwischen gefunden habe:
https://en.wikipedia.org/wiki/Tree_traversal
https://towardsdatascience.com/4-typ...s-d56328450846

offenbar hat es wieder nur den richtigen Suchbegriff gebraucht ... Post-order traversal for non-binary trees ist die Antwort - jetzt noch eine nachvollziehbare Implementierung finden ... omg ... was für ein Hornissennest

Selbstkorrektur: Tree Traversal ist nicht die Antwort, weil dort die Knoten/Kinder gleichberechtigt sind. Das ist hier aber nicht der Fall, da ich zusätzlich ja noch die Information berücksichtigen muss, an welchem Punkt die Zweige ansetzen und die Reihenfolge stimmen muss. Es sind also die Zweige eines Astes (Childrenn eines Parent) zusätzlich zu sortieren ...

[Gausi]

Eine Baumstruktur in den Daten verwaltet man ja eigentlich nicht als "Zweige" sondern als einzelne "Knoten". In einem Baum gibt es dann genau einen Wurzelknoten. An diesem hängen dann Kindknoten, die dann weitere Kindknoten haben können. Bei Binärbäumen kann man die Kindknoten in zwei Knoten-Variablen speichern (die dann ggf. left und right heißen), bei Bäumen mit höherem Grad verwaltet man die Kindknoten in einer Liste/Array/Dictionary/whatever, die man nach eigenem Ermessen sortieren kann (oder auch nicht). Jeder Kindknoten hat meist noch eine Referenz auf den Parent.

Zum Berechnen von irgendwas auf dem Baum ruft man dann eine Methode "Calculate" des RootKnoten auf, die dann z.B. so aussehen könnte.

Delphi-Quellcode:

function TMyNode.Calculate: Integer;
var i, sum: Integer
begin
  sum := 0;
  for i := 0 to ChildNodes.Count - 1 do
    sum := sum + ChildNodes[i].Calculate; 
  fSubNodeCount := sum
  result := sum + 1;
end;

Diese Funktion würde z.B. die Anzahl der Elemente in dem Baum angeben (wenn ich mich auf die Schnelle nicht vertan habe), aber da kann man natürlich beliebige Dinge berechnen.

Oder anschaulich: Du musst den Wurzelknoten kennen - also den "Stamm". Wenn der etwas berechnen will, kümmert sich der Stamm darum, dass alle nötigen Daten vorliegen. Wenn er dazu Daten von seinen Kindknoten bzw. den daran hängenden Zweigen kennen muss, dann teilt er diesen das mit. Und wenn diese dafür wieder weitere Daten von Unterzweigen brauchen, dann läuft das automatisch nach unten durch.

Wenn die Reihenfolge der Kindknoten relevant ist (z.B. 5 muss vor 3 berechnet werden), dann kann man das erreichen, indem man die Kindknotenliste eines Knotens vor der Berechnung entsprechend sortiert.