Hydrater un arbre à partir d'une table

Question

J'ai une DataTable contenant tous mes noeuds. Ils ont été sérialisés dans la base de données. Je veux créer une représentation graphique (hiérarchique) des données. Il semble y avoir quelques méthodes pour le faire.

Cet article décrit une méthode d'ordre élevé (ce qui signifie qu'il faut effectuer de nombreuses recherches dans la table de données avant que l'arbre ne soit entièrement construit).

Existe-t-il une approche de type Ordre-N ? Dans mon cas, j'ai pré-trié les nœuds de l'arbre dans la DataTable dans l'ordre. Autrement dit, la première ligne affiche un NULL pour le parent, car il s'agit de la racine. Chaque ligne suivante est triée en notation en ordre .

Il me semble me souvenir d'une approche de l'ordre N de mes jours d'école. Mais je ne m'en souviens pas.

Le schéma de ma DataTable ressemble à ceci :

• NodeID - int
• ParentNodeId - nullable
• Données - chaîne

Answer 1

Voici un algorithme qui devrait faire ce que vous voulez qu'il fasse. Il suppose que vos données sont en ordre, donc il fonctionne en O(n).

Tout d'abord, vous avez besoin d'un nœud qui ressemble à ceci :

class Node {
    Node Parent;
    List<Node> Children = new List<Node>();
    int NodeId;
    string Data;
    public Node(NodeRow row) { ... }
}

1. Chargez la première ligne comme current .
2. Chargement de la ligne suivante ; comparaison newRow.ParentNodeId a current.NodeId .
3. Jusqu'à ce que vous trouviez une correspondance, mettez current = current.Parent
4. Ajouter le newRow a current.Children et mettre current à la nouvelle ligne.
5. Passez à l'étape 2.

C'est tout ! Si vous avez la garantie que vos données sont correctement structurées, vous n'aurez pas besoin d'effectuer des opérations supplémentaires. null des contrôles.

Un échantillon :

Node CreateTree(IEnumerable<NodeRow> rows) {
    Node root = null;
    Node current = null;
    foreach (var row in rows) {
        // Root:
        if (root == null) { 
            root = current = new Node(row);
            continue;
        }
        // Traverse up the tree until the parent is found:
        while (row.ParentNodeId != current.NodeId) {
            current = current.Parent;
        }
        // Add the new node as a child of the current one:
        var rowNode = new Node(row);
        rowNode.Parent = current;
        current.Children.Add(rowNode);
        current = rowNode;
    }
    return root;
}