Creazione di un albero utilizzando un elenco di oggetti

Question

Ho un elenco di oggetti con ID proprietà e parent_id.
Voglio costruire un albero per collegare quei bambini e genitori.
1 genitore può avere più figli e c'è un oggetto che sarà l'antenato di tutti gli oggetti.

Qual è l'algoritmo più veloce per implementarlo?
Io uso C# come linguaggio di programmazione, ma anche altre lingue sono accettabili.

Answer 1

Qualcosa del genere dovrebbe fare il trucco:

public List<Node> MakeTreeFromFlatList(IEnumerable<Node> flatList) 
{ 
    var dic = flatList.ToDictionary(n => n.Id, n => n); 
    var rootNodes = new List<Node>(); 
    foreach(var node in flatList) 
    { 
     if (node.ParentId.HasValue) 
     { 
      Node parent = dic[node.ParentId.Value]; 
      node.Parent = parent; 
      parent.Children.Add(node); 
     } 
     else 
     { 
      rootNodes.Add(node); 
     } 
    } 
    return rootNodes; 
} 

(assumendo che ParentId è un Nullable<int>, ed è nullo per i nodi di root)

Answer 2

È possibile utilizzare un dizionario:

var dict = new Dictionary<Id, Node>(); 

foreach (var item in items) 
{ 
    dict[item.Id] = new Node(item); 
} 

foreach (var item in items) 
{ 
    dict[item.ParentId].AddChild(dict[item.Id]); 
} 

Answer 3

Preferisco di gran lunga questo tipo di struttura. Mantenendo un singolo elenco (si consiglia di utilizzare un dizionario o simile per velocità) di articoli e passandolo nella funzione GetChildItems si ha maggiore flessibilità e facilità di ordinamento, aggiunta, rimozione, salvataggio in un db ecc.

Hai davvero bisogno della funzione GetChildItem solo quando esegui il rendering dell'elenco su una vista e vuoi che la struttura ad albero sia facilmente modificabile come dici tu. In questo caso si può avere un modello di visualizzazione con l'elenco completo e la voce che è passato in ogni vista voce

public class Item 
{ 
    public string Id { get; set; } 
    public string ParentId { get; set; } 

    public IEnumerable<Item> GetChildItems(List<Item> allItems) 
    { 
     return allItems.Where(i => i.Id == this.ParentId); 
    } 
} 

public class Tree 
{ 
    public List<Item> Items { get; set; } 

    public IEnumerable<Item> RootItems(List<Item> allItems) 
    { 
     return allItems.Where(i => i.ParentId == null); 
    } 
} 

Nota: la struttura di classe di cui sopra è stato progettato per imitare il modello oggetto complesso tradizionale. in questi giorni si verificherebbe solo GetChildItems (Elenca tutti gli elementi, Oggetto genitore) nel modello di vista