Budowanie obiektów hierarchii z płaskiej listy elementów nadrzędnych/podrzędnych

Question

Mam listę elementów w hierarchii, a ja próbuję przeanalizować tę listę w rzeczywistą hierarchię obiektów. Używam modified pre-order tree traversal do przechowywania/iteracji za pomocą tej listy, więc to, co mam, to podzbiór drzewa, w tym wszystkie dzieci, uporządkowane według ich "lewej" wartości.

Na przykład, ze względu na drzewo:

• Pozycja A
  • Pozycja A.1
  • Pozycja A.2
    • Przedmiot A.2.2
• Pozycja B
  • Przedmiot B.1
• Pozycja C

uzyskać listę:

• pkt a, pkt A.1, pkt A.2, Pozycja A.2.2, pozycja B, pozycja B.1, pozycja C

(Jest to w porządku "lewej" wartości ze zmodyfikowanego ustawienia drzewa zamówień przed zamówieniem).

Co chcę zrobić to przeanalizować to pod obiektami, które zawierają rzeczywistą strukturę drzewa, np:

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

Lista płaskie zwracana jest jako lista TreeObjects - a każdy TreeObject ma właściwości ID , ParentID, Left i Right. To, czego szukam, to funkcja:

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

, która przyjmuje listę płaską i zwraca listę zagnieżdżoną.

Innymi słowy:

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

Jestem w rozterce, jak to zrobić - śledzenie rodziców, i jest w stanie poradzić sobie z większym skoku (np, poz A.2.2 -> Przedmiot B).

---

Edycja: szukam rozwiązania niż brute-force tutaj (na przykład, nie zapętlenie kilka razy, przenosząc elementy do węzłów potomnych, dopóki istnieją tylko rodzice najwyższego poziomu w lewo). Zgaduję, że istnieje elegancka metoda, która może jednorazowo wykonać pętlę i po prostu umieścić elementy w razie potrzeby.

Pamiętaj, że są zawsze w porządku hierarchicznym (od kiedy używam MPTT), więc daną rzeczą zawsze będzie dziecko lub rodzeństwo poprzedniego przedmiotu, lub przynajmniej podzielenie się rodzicem z poprzednim przedmiotem . Nigdy nie pojawi się gdzie indziej w drzewie.

Answer 1

Oto funkcja skończyło się na piśmie. Używam MPTT do przechowywania obiektów, więc lista jest w kolejności "lewej" wartości, co w zasadzie oznacza, że ​​rodzic zawsze pojawia się przed jakimkolwiek danym elementem na liście. Innymi słowy, element, do którego odwołuje się item.ParentID, zawsze był już dodany (z wyjątkiem węzłów najwyższego poziomu lub root).

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

i prosty test (który działa w 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(); 
} 

Wyniki:

Odkąd jestem aktualizowania to 5 lat później, oto rekurencyjne LINQ wersja:

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

Zakładam, że znasz już rodzica wszystkich pozycji.

Wszystko, co musisz zrobić, to powtórzyć cały element listy i dodać bieżący element do listy dzieci jego rodzica. Przechowuj tylko elementy bez rodziców na docelowej liście zagnieżdżonej.

Oto niektóre pseudo kod:

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

chodzi o uzyskanie rodziców, z tego co widzę na swoim przykładzie, może trzeba analizować nazwę i zbudować stos jak wcześniej na liście.

Ten problem jest trudny, ale tak naprawdę nie jest. Wiele osób widzi ten problem pod niewłaściwym kątem; nie wolno próbować zapełniać każdej listy dzieci, ale raczej pozbyć się przedmiotów dzieci z listy płaskiej, wtedy staje się to łatwe.

Answer 3

Oto przykład, mam nadzieję, że to pomaga

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 4

Alternatywna wersja, która kompiluje się normalnie, nie byłem pewien, czy wystąpił problem z powyższym kodem.

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 5

Korygowanie przykład podany przez 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(); 
    }