Falls Du die Tabelle noch erweitern kannst, würde ich in jedem Fall noch die Eigenschaften 'Level' und 'Rank' einführen.
'Level' bezeichnet die Ebene des Knotens (0=Wurzel, 1=1.Ebene, 2=2.Ebene usw.)
'Rank' die Reihenfolge eines Knotens im Zweig. Die ist für das hier beschriebene Verfahren zwar nicht nötig, ich würde sie aber i.a. trotzdem mit angeben, wenn die Reihenfolge eine Rolle spielt.
'Level' erleichtert Dir das Einlesen in einen Baum und 'Rank' stellt die Reihenfolge der Knoten im Zweig sicher.
Dann liest Du die Tabelle ein, sortierst nach Level und Rank und gehst so vor (Pseudocode):
Delphi-Quellcode:
Query.SQL.Text := '
Select ParentID, Level, Rank, ID, Data From Tree Order by Level, Rank';
// Alternativ unsortiert einlesen und in-Memory sortieren, um den SQL-Server zu entlasten
// Geht bei einer TADOTable über die IndexFieldNames-Eigenschaft.
Query.Active := True;
While not Query.Eof
Do Begin
// Suche Eltern-Knoten. Da wir nach Level sortieren, ist der garantiert schon angelegt.
// Der Microsoft-Tree definiert NIL als Wurzelknoten, sodaß eine Suche nach der Wurzel-ID
// hier fehlschlägt bzw. NIL liefert, was aber auch ok ist.
ParentNode := Tree.FindNodeByID(
Query['
ParentID']);
// Lege neuen Baumknoten an
Node := TTreeNode.Create(
Query['
ID'],
Query['
Data']);
// Und hänge ihn an den Eltern-Knoten. Hier vielleicht eine Fallunterscheidung zwischen
// ParentNode=NIL (Wurzelknoten) und anderen Knoten
Tree.AddNode (ParentNode, Node);
// Nächsten Datensatz einlesen
Query.Next
End;
Der Bottleneck ist hier die Suche nach dem Elternknoten, der aber durch Verwendung z.B. einer Hashmap drastisch verkürzt werden kann.
Vorteil ggü. Mediums Variante: Kommt ohne Liste aus und ist einfacher umzusetzen.
Nachteil ggü. Mediums Variante: Es wird ein weiteres Feld ('Level') benötigt. Allerdings ist so eine Level-Information manchmal sehr brauchbar, wenn nämliche die Ebene selbst eine Information darstellt.
Beispiel: Mitarbeiterhierarchie (Chef->Werksleiter->Abteilungsleiter...)
Dann findet man sehr schnell z.B. alle Werksleiter ('Level=2').
Natürlich sollte man auf diese Variante verzichten, wenn Teilbäume frei herumgeschoben werden dürfen
und die Änderungen direkt in der
DB vorgenommen werden sollen. Denn dann müssten auch alle Level neu durchnummeriert werden, wenn ein Teilbaum verschoben wird.
Ich würde erst festlegen, ob die hier vorgeschlagenen Zusatzinformationen wichtig sind und dann das Verfahren wählen. Wenn Du also die Ebeneninformation brauchst, nimm meine Variante, ansonsten die vom Medium.
Wenn man eine Liste/Queue verwenden darf, dann ruhig rekursiv:
Delphi-Quellcode:
Procedure CreateTree (Tree : TTree; Elements : TList);
Begin
// Einfach jedes Element in den Baum eintragen
While not Elements.IsEmpty Do
InsertNode(Tree, Elements, Elements.Items[0]);
End;
Function InsertNode (Tree: TTree; Elements: TList; Element : TElement) : TTreeNode;
Begin
If Element=Nil Then
Result := RootNode
Else Begin
Result := TTreeNode.Create(Element);
Elements.Remove (Element);
// Erstmal den Elternknoten finden
ParentNode := Tree.FindNodeByID (Element.ParentID); // Hier wieder optimieren
// Wenn es noch keinen gibt, dann eben den erst anlegen (rekursiv)
If ParentNode=Nil Then
ParentNode := InsertNode (Tree, Elements, Elements.FindElementByID (Element.ParentID));
// Knoten an Elternknoten hängen. Wenn ParentNode=Nil, an die Wurzel hängen
Tree.AddNode (ParentNode, Result);
End;
End
End;
Kurz und knapp. Fix sollte das auch sein.