Creazione di oggetti gerarchici da un elenco semplice di padre / figlio

Question

Ho un elenco di elementi in una gerarchia e sto tentando di analizzare questo elenco in una vera gerarchia di oggetti. Sto usando traversal tree pre-order modificato per archiviare / iterare attraverso questo elenco, e quindi quello che ho è un sottoinsieme dell'albero, inclusi tutti i bambini, ordinati dalla loro "sinistra" valore.

Ad esempio, dato l'albero:

• Articolo A
  • Articolo A.1
  • Articolo A.2
    • Articolo A.2.2
• Articolo B
  • Articolo B.1
• Articolo C

Ottengo l'elenco:

• Articolo A, Articolo A.1, Articolo A.2, Articolo A.2.2, Articolo B, Articolo B.1, Articolo C

(Questo è nell'ordine del valore "a sinistra" dalla configurazione dell'albero pre-ordine modificata).

Quello che voglio fare è analizzarlo in oggetti che contengono la struttura reale dell'albero, ad esempio:

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

L'elenco flat viene restituito come Elenco di TreeObjects - e ogni TreeObject ha proprietà per ID, ParentID, Sinistra e Destra. Quello che sto cercando è una funzione:

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

che accetta l'elenco flat e restituisce un elenco nidificato.

In altre parole:

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

Non riesco a farlo: tenere traccia dei genitori e riuscire a fare un salto più grande (ad esempio, Articolo A.2.2 - > Articolo B).

---

Modifica: sto cercando una soluzione senza forza bruta (ad esempio, non eseguire più cicli ripetutamente, spostare elementi in nodi figlio, fino a quando rimangono solo i genitori di livello superiore). Immagino che esista un metodo elegante che può essere ripetuto una volta e posizionare gli oggetti secondo necessità.

Ricorda, sono sempre in un ordine gerarchico (dal momento che sto usando MPTT), quindi un determinato oggetto sarà sempre figlio o fratello dell'elemento precedente, o almeno condividi un genitore con l'elemento precedente. Non verrà mai da qualche altra parte nell'albero.

Answer 1

Ecco la funzione che ho finito per scrivere. Sto usando MPTT per archiviare oggetti, quindi l'elenco è in ordine del valore 'left', il che significa sostanzialmente che il genitore viene sempre prima di ogni dato elemento nell'elenco. In altre parole, l'elemento a cui fa riferimento item.ParentID è sempre stato aggiunto (tranne nel caso di nodi di livello superiore o radice).

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;
}

e un semplice test (che funziona in 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();
}

Risultati:

Da quando lo sto aggiornando 5 anni dopo, ecco una versione ricorsiva di LINQ:

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

Presumo che tu conosca già il genitore di tutti gli elementi .

Tutto ciò che devi fare è iterare una volta tutti gli elementi dell'elenco e aggiungere l'elemento corrente all'elenco figlio del suo genitore. Conserva gli articoli solo senza i genitori nell'elenco nidificato di destinazione.

Ecco un pseudo codice:

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

Per quanto riguarda ottenere i genitori, da quello che posso vedere nel tuo esempio, potresti dover analizzare il nome e costruire uno stack man mano che avanzi nella lista.

Questo problema sembra difficile ma non lo è. Molte persone vedono questo problema da un'angolazione sbagliata; non devi provare a popolare tutti gli elenchi di bambini, ma piuttosto a eliminare gli elementi di figlio dall'elenco piatto, quindi diventa facile.

Answer 3

Versione alternativa che viene compilata normalmente, non ero sicuro che ci fosse un problema con il codice sopra.

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

Ecco un esempio, spero che questo aiuti

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

Correzione dell'esempio fornito da 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();
    }