Baumartige Struktur in der richtigen Reihenfolge berechnen

[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.