Aus einer unsortierten Liste mit Parent-Child Beziehungen möchte ich eine Baumstruktur erzeugen.
Nehmen wir an ich habe folgende Liste:
Parent: | Child:
100 | 101
101 | 201
101 | 301
101 | 401
401 | 421
100 | 205
100 | 305
305 | 421
...
Ich möchte nun einen Algorithmus in C# implementieren mit dessen Hilfe ich bei Angabe einer Parent-Nr. einen Baum erzeuge, der alle darunterliegenden Parent-Child-Beziehungen enthält.
Also wenn ich z.B. Parent-ID: 101 als Startwert (Root) angebe, so soll folgende Baumstruktur erzeugt werden:
101
...|_ 201
...|_ 301
...|_ 401
........|_421

Je nach dem welche Parent-ID ich angebe, kann ich unterschieldiche Baumstrukturen erhalten.
Wie muss dieser Algorithmus aussehn?

Du brauchst eine Datenstruktur, die einen Knoten repräsentiert. Ein Knoten hat eine ID und eine Liste von Kindknoten. Außerdem brauchst Du ein Verzeichnis, in dem du zu einer ID den zugehörigen Knoten nachschlagen kannst.

Dann läufst Du alle ID-Paare ab. Für jede ID holst Du Dir den Knoten aus dem Verzeichnis. Wenn es ihn noch nicht gibt, erzeugst Du ihn und legst ihn im Verzeichnis ab. Dann fügst Du den Kindknoten der Kinder-Liste des Elternknoten hinzu. Dann weiter mit dem nächsten ID-Paar.

Am Ende schlägst Du im Verzeichnis den Knoten mit der gegebenen ID nach.

Soweit die einfache Variante, und jetzt zu den Knackpunkten. Kompliziert wird es, wenn

• Du den Komplett-Baum aller Knoten nicht erzeugen kannst/willst (z.B. weil es zuviele Knoten sind)
  
• Du überprüfen mußt, ob Deine Eingangsdaten überhaupt einen Baum ergeben, z.B. weil es einen Kreis darin gibt:
  1 2
  2 3
  3 1
  oder Knoten mit mehreren Eltern vorkommen:
  1 2
  1 3
  2 4
  3 4
  

Wenn Du solche Anforderungen hast, dann ergänze bitte noch Deine Frage um entsprechende Hinweise.

Ich habe hier kurz etwas skizziert, bitte nur als Pseudocode verstehen, ungetestet:

using System;

public class Node
{
    public Guid Id;
    public Guid ParentId;
    public Node Parent;
    public List<Node> Children = new List<Node>();

    public static Node TreeFromNode(Guid rootId, List<Node> unsortedList)
    {
        foreach (Node node in unsortedList)
        {
            if (node.Id == rootId)
            {
                AddSubNodes(node, unsortedList);
            }
        }
    }

    public static void AddSubNodes(Node currentNode, List<Node> allNodes)
    {
        foreach (Node node in allNodes)
        {
            if (node.ParentId == currentNode.Id) // child found
            {
                currentNode.Children.Add(node);
                node.Parent = currentNode;
            }
            if(!IsNodeInPath(currentNode, node.Id))
                AddSubNodes(node, allNodes);
        }
    }

    public static bool IsNodeInPath(Node node, Guid id)
    {
        if (node.Id == id) return true;
        if (node.Parent != null)
            return IsNodeInPath(node.Parent, id);
        return false;
    }
}

Mit der Methode TreeFromNode wird der Graph ab rootId aufgebaut. AddSubNodes() und der Kreis-Test IsInNodePath() arbeiten jeweils rekursiv.
Das kann dir evtl. als Anregung helfen. Ich bin sicher, die Profis hier im Forum liefern in Kürze noch eine elegantere (und vermutlich fehlerbereinigte) Variante :-)

Gruß
Daniel

Hallo,

ich würde zuerst alle items in einem Dictionary (ID, Item) laden.

Anschließend kannst du über die Items iterieren, über die ParentID das entsprechende parentItem aus dem Dictionary holen und dem parentItem das aktuelle item als child zuweisen.

Alle items ohne parentID bilden die Wurzelelemente.


Viele Grüße,
Tachyon