Budowanie drzewa przy użyciu listy obiektów

Question

Mam listę obiektów z id nieruchomości i nadrzędny_id.
Chcę zbudować drzewo, aby połączyć te dzieci i rodziców.
1 rodzic może mieć kilkoro potomków i jest obiekt, który będzie przodkiem wszystkich obiektów.

Jaki jest najszybszy algorytm do wdrożenia?
Używam C# jako języka programowania, ale inne języki też są w porządku.

Answer 1

Coś takiego powinno wystarczyć:

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

(zakładając, że parentId jest Nullable<int> i jest zerowy dla węzłów korzeniowych)

Answer 2

Można użyć słownika:

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

Wolę ten rodzaj struktury. Utrzymując pojedynczą listę (możesz użyć słownika lub podobnego do szybkości) elementów i przekazując ją do funkcji GetChildItems, masz większą elastyczność i łatwość sortowania, dodawania, usuwania, zapisywania do bazy danych itp.

Naprawdę potrzebujesz tylko funkcji GetChildItem, gdy renderujesz listę do widoku i chcesz, aby struktura drzewa była łatwa do edycji, jak mówisz. W tym przypadku można mieć widok modelu z pełną listą i element, który jest przekazywany do każdego widoku poz

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

Uwaga: struktura klasy powyżej jest przeznaczony do naśladowania tradycyjny kompleks obiektów wzór. w dzisiejszych czasach miałbyś prawdopodobnie tylko GetChildItems (List allItems, Item parentItem) w widoku modelu