Comment construire efficacement un arbre à partir d'une structure plate?

Question

J'ai un tas d'objets dans une structure plate. Ces objets ont un ID et ParentID de la propriété de sorte qu'ils peuvent être organisées dans les arbres. Ils sont dans aucun ordre particulier. Chaque ParentID de la propriété n'est pas nécessairement correspond à un ID dans la structure. Par conséquent, leur pourrait être de plusieurs arbres qui se dégage de ces objets.

Comment voulez-vous traiter ces objets pour créer la résultante des arbres ?

Je ne suis pas loin d'être une solution, mais je suis sûr que c'est loin d'être optimale...

Merci !

[MODIFIER] @OrbMan : j'ai besoin de créer ces arbres pour ensuite insérer des Données dans une base de données, dans le bon ordre.

@JPunyon : Il n'y a pas de références circulaires. Un Nœud est un RootNode quand ParentID == null ou lorsque ParentID ne peut pas être trouvé dans les autres objets

Answer 1

Enregistre les identifiants des objets dans une table de hachage mappée sur l'objet spécifique. Énumérez tous les objets et recherchez leur parent s'il existe, puis mettez à jour son pointeur parent en conséquence.

 class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}
 

Answer 2

Voici un algorithme JavaScript simple permettant d'analyser une table plate dans une arborescence parent / enfant s'exécutant dans un temps N:

 var table = [
    {parent_id: 0, id: 1, children: []},
    {parent_id: 0, id: 2, children: []},
    {parent_id: 0, id: 3, children: []},
    {parent_id: 1, id: 4, children: []},
    {parent_id: 1, id: 5, children: []},
    {parent_id: 1, id: 6, children: []},
    {parent_id: 2, id: 7, children: []},
    {parent_id: 7, id: 8, children: []},
    {parent_id: 8, id: 9, children: []},
    {parent_id: 3, id: 10, children: []}
];

var root = {id:0, parent_id: null, children: []};
var node_list = { 0 : root};

for (var i = 0; i < table.length; i++) {
    node_list[table[i].id] = table[i];
    node_list[table[i].parent_id].children.push(node_list[table[i].id]);
}

console.log(root);
 

Answer 3

Aussi vague que la question me paraisse, je créerais probablement une carte de l'identifiant à l'objet réel. En pseudo-java (je n'ai pas vérifié si ça marche / compile), ça pourrait être quelque chose comme:

 Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>();

for (FlatObject object: flatStructure) {
    flatObjectMap.put(object.ID, object);
}
 

Et pour chercher chaque parent:

 private FlatObject getParent(FlatObject object) {
    getRealObject(object.ParentID);
}

private FlatObject getRealObject(ID objectID) {
    flatObjectMap.get(objectID);
}
 

En réutilisant getRealObject(ID) et en créant une carte d'un objet à une collection d'objets (ou leurs ID), vous obtenez également une carte parent-> enfants.

Answer 4

Êtes-vous coincé en utilisant uniquement ces attributs? Si ce n'est pas le cas, il peut être intéressant de créer un tableau de nœuds enfants dans lequel vous pouvez parcourir tous ces objets une fois pour créer ces attributs. A partir de là, sélectionnez le noeud avec les enfants mais pas les parents et construisez votre arbre de manière itérative du haut vers le bas.

Answer 5

Vous ne savez pas ce que vous essayez d'accomplir? Habituellement, vous utilisez une structure de données arborescente pour la recherche, le tri, etc. - mais si vous allez placer les données directement dans une base de données .. ?? .. Je ne sais pas quel est le raisonnement? Souhaitez-vous créer une interface arborescente? puis enregistrer dans une base de données? Chaque nœud ayant un identifiant unique et un identifiant parent ... vous avez en principe une structure et la structure de base peut être gérée via la référence de l'objet (en fonction de la configuration choisie)