Construction d'objets de hiérarchie à partir d'une liste plate de parent / enfant

Question

J'ai une liste d'éléments dans une hiérarchie et j'essaie d'analyser cette liste dans une hiérarchie d'objets. J'utilise la traversée de l'arborescence de pré-commande modifiée pour stocker / itérer à travers cette liste, et donc ce que j’ai est un sous-ensemble de l’arbre, y compris tous les enfants, ordonné par leur "gauche". valeur.

Par exemple, étant donné l'arbre:

• élément A
  • élément A.1
  • élément A.2
    • élément A.2.2
• élément B
  • élément B.1
• élément C

je reçois la liste:

• Article A, article A.1, article A.2, article A.2.2, article B, article B.1, article C

(Ceci est dans l'ordre de la valeur "à gauche" de la configuration d'arborescence de précommande modifiée).

Ce que je veux faire, c'est analyser cela dans des objets contenant la structure actuelle de l'arbre, par exemple:

Class TreeObject {
    String Name;
    Guid ID; 
    Guid ParentID;
    List<TreeObject> Children;
}

La liste non hiérarchique est renvoyée sous forme de liste d'objets TreeObjects - et chaque objet TreeObject a des propriétés pour ID, ParentID, Left et Right. Ce que je recherche, c’est une fonction:

List<TreeObject> FlatToHeirarchy(List<TreeObject> list); 

qui prend la liste à plat et renvoie une liste imbriquée.

En d'autres termes:

List<TreeObject> flatSet = LoadTreeObjectsFromDatabase(); 
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2

Je ne sais pas comment faire cela - garder une trace des parents et être capable de faire face à un saut plus important (par exemple, élément A.2.2 - > élément B).

Éditer: Je cherche ici une solution sans force brute (par exemple, ne pas boucler plusieurs fois, déplacer des éléments dans des nœuds enfants jusqu'à ce qu'il ne reste plus que les parents de niveau supérieur). Je suppose qu’il existe une méthode élégante qui permet de boucler une fois et de placer les éléments au besoin.

N'oubliez pas qu'ils sont toujours dans un ordre hiérarchique (étant donné que j'utilise MPTT), de sorte qu'un élément donné sera toujours un enfant ou un frère de l'élément précédent, ou au moins partage un parent avec l'élément précédent. Il ne va jamais arriver ailleurs dans l'arbre.

Answer 1

Voici la fonction que j'ai finalement écrite. J'utilise MPTT pour stocker des objets. La liste est donc dans l'ordre de la valeur "gauche", ce qui signifie que le parent vient toujours avant un élément donné de la liste. En d'autres termes, l'élément référencé par item.ParentID a toujours déjà été ajouté (sauf dans le cas des nœuds de niveau supérieur ou racine).

public class TreeObject
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
    public IList<TreeObject> Children { get; set; } = new List<TreeObject>();
}

public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list)
{
    // hashtable lookup that allows us to grab references to containers based on id
    var lookup = new Dictionary<int, TreeObject>();
    // actual nested collection to return
    var nested = new List<TreeObject>();

    foreach (TreeObject item in list)
    {
        if (lookup.ContainsKey(item.ParentId))
        {
            // add to the parent's child list 
            lookup[item.ParentId].Children.Add(item);
        }
        else
        {
            // no parent added yet (or this is the first time)
            nested.Add(item);
        }
        lookup.Add(item.Id, item);
    }

    return nested;
}

et un test simple (qui fonctionne dans LinqPad):

void Main()
{
    var list = new List<TreeObject>() {
        new TreeObject() { Id = 1, ParentId = 0, Name = "A" },
        new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" },
        new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" },
        new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" },
        new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" }
    };

    FlatToHierarchy(list).Dump();
}

Résultats:

Étant donné que j'effectue la mise à jour 5 ans plus tard, voici une version LINQ récursive:

public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) {
    return (from i in list 
            where i.ParentId == parentId 
            select new TreeObject {
                Id = i.Id, 
                ParentId = i.ParentId,
                Name = i.Name,
                Children = FlatToHierarchy(list, i.Id)
            }).ToList();
}

Answer 2

Je suppose que vous connaissez déjà le parent de tous les éléments .

Tout ce que vous avez à faire est de parcourir une fois l’ensemble des éléments de la liste et d’ajouter l’élément actuel à la liste des enfants de son parent. Ne conservez que les éléments sans parents dans la liste imbriquée cible.

Voici un pseudo code:

foreach Item item in flatlist
   if item.Parent != null
      Add item to item.Parent.ChildrenList
      Remove item from flatlist
   end if
end for

En ce qui concerne l'obtention des parents, d'après ce que je peux voir dans votre exemple, vous devrez peut-être analyser le nom et créer une pile à mesure que vous avancez dans la liste.

Ce problème semble difficile, mais il ne l’est vraiment pas. Beaucoup de gens voient ce problème sous le mauvais angle; vous ne devez pas essayer de remplir toutes les listes d’enfants, mais plutôt vous débarrasser de leurs articles les plus simples, cela devient alors facile.

Answer 3

Version alternative qui compile normalement, je n'étais pas sûr s'il y avait un problème avec le code ci-dessus.

private List<Page> FlatToHierarchy(List<Page> list) {
      // hashtable lookup that allows us to grab references to the parent containers, based on id
        Dictionary<int, Page> lookup = new Dictionary<int, Page>();
      // actual nested collection to return
      List<Page> nested = new List<Page>();

      foreach(Page item in list) {
        if (lookup.ContainsKey(item.parentId)) {
          // add to the parent's child list 
          lookup[item.parentId].children.Add(item); //add item to parent's childs list
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        } else {
          // no parent added yet (or this is the first time)
          nested.Add(item);     //add item directly to nested list                
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        }
      }
    return nested;
    }

Answer 4

Voici un exemple, espérons que cela vous aidera

class Program
{
    static void Main(string[] args)
    {
        TreeObject a  = new TreeObject() { Name = "Item A" };
        a.Children.Add( new TreeObject() { Name = "Item A.1" });
        a.Children.Add( new TreeObject() { Name = "Item A.2" });

        TreeObject b = new TreeObject() { Name = "Item B" };
        b.Children.Add(new TreeObject() { Name = "Item B.1" });
        b.Children.Add(new TreeObject() { Name = "Item B.2" });

        TreeObject c = new TreeObject() { Name = "Item C" };

        List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c });

        string list = BuildList(nodes);
        Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C

        List<TreeObject> newlist = new List<TreeObject>();
        TreeObject temp = null;

        foreach (string s in list.Split(','))
        {
            if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length)
            {
                temp = new TreeObject() { Name = s };
                newlist.Add(temp);
            }
            else
            {
                temp.Children.Add(new TreeObject() { Name = s });
            }                              
        }

        Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
    }

    static string BuildList(List<TreeObject> nodes)
    {
        StringBuilder output = new StringBuilder();
        BuildList(output, nodes);
        return output.Remove(output.Length - 1, 1).ToString();
    }

    static void BuildList(StringBuilder output, List<TreeObject> nodes)
    {
        foreach (var node in nodes)
        {
            output.AppendFormat("{0},", node.Name);
            BuildList(output, node.Children);
        }
    }
}

public class TreeObject
{
    private List<TreeObject> _children = new List<TreeObject>();

    public string Name { get; set; }
    public Guid Id { get; set; }
    public List<TreeObject> Children { get { return _children; } }
}

}

Answer 5

Correction de l'exemple donné par gregmac

IList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId)
    {
        var q = (from i in list
                where i.parent_id == parentId
                select new
                {
                    id = i.id,
                    parent_id = i.parent_id,
                    kks = i.kks,
                    nome = i.nome
                }).ToList();
        return q.Select(x => new TreeObject
            {
                children = FlatToHierarchy(list, x.id)
            }).ToList();
    }