Gebäude Hierarchie-Objekte aus flacher Liste von Eltern / Kind

Question

Ich habe eine Liste der Elemente in einer Hierarchie, und ich bin versucht, diese Liste zu analysieren, in eine tatsächliche Hierarchie von Objekten. Ich verwende vorbestellen Baum-Traversal speichern / iterate durch diese Liste, und so, was ich habe, ist eine Teilmenge des Baumes, einschließlich aller Kinder, die von ihren „linken“ Wert bestellt.

Zum Beispiel, angesichts den Baum:

• Item A
  • Artikel A.1
  • Item A.2
    • Artikel A.2.2
• Item B
  • Artikel B.1
• Item C

ich die Liste:

• Item A, Punkt A.1, Punkt A.2, Punkt A.2.2, Punkt B, Punkt B.1, Punkt C

(Dies ist in der Reihenfolge des „linken“ Wertes aus dem modifizierten vorbestellen Baum-Setup).

Was ich tun möchte, ist dies in Objekte zu analysieren, die die tatsächliche Struktur des Baumes enthalten, zum Beispiel:

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

Die flache Liste wird als Liste der TreeObjects zurückgekehrt - und jede TreeObject hat Eigenschaften für ID, ParentID, Links und Rechts. Was ich suche, ist eine Funktion:

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

, die in der flachen Liste nimmt und gibt eine verschachtelte Liste.

Mit anderen Worten:

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

ich bin ratlos, wie dies zu tun - die Verfolgung der Eltern, und mit einem größeren Sprung bewältigen zu können. (ZB Artikel A.2.2 -> Item B)

---

Edit: Ich bin für eine nicht-Brute-Force-Lösung hier (zB nicht looping mehrmals, Elemente in untergeordneten Knoten zu bewegen, bis nur noch die Top-Level-Eltern sind links) suchen. Ich vermute, es ist eine elegante Methode, die Schleife einmal kann, und nur Einzelteile setzen je nach Bedarf.

Denken Sie daran, sie immer in hierarchischer Reihenfolge sind (da ich MPTT bin mit), so dass ein bestimmtes Element wird immer ein Kind oder Geschwister des vorherigen Element sein, oder zumindest ein Elternteil mit dem vorherigen Element teilen. Es ist nie irgendwo anders im Baum wird kommen.

Answer 1

Hier ist die Funktion, die ich schreibe endete. Ich verwende MPTT Objekte zu speichern, so dass die Liste ist in der Reihenfolge des Wertes ‚links‘, die im Grunde die Eltern bedeutet, kommt immer vor einem bestimmten Element in der Liste. Mit anderen Worten, hat das Element von item.ParentID verwies immer bereits hinzugefügt worden ist (außer im Fall von Top-Level-oder Root-Knoten).

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

und ein einfacher Test (die in LinqPad funktioniert):

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

Ergebnisse:

Da ich diese 5 Jahre später bin Aktualisierung, hier ist eine rekursive LINQ-Version:

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

Ich nehme an, Sie bereits die Eltern aller Elemente kennen .

Alles, was Sie tun müssen, ist einmal durch alle Artikel aus der Liste iterieren und das aktuelle Element an ihre Mutterkinder Liste hinzufügen. halten nur die Elemente ohne Eltern in der Ziel verschachtelt Liste.

Hier finden Sie einige 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

Wie für die Eltern bekommen, von dem, was ich in Ihrem Beispiel sehen kann, müssen Sie möglicherweise den Namen analysieren und einen Stapel zu bauen, wie Sie in der Liste gelangen.

Diese Probleme sehen hart, aber es ist wirklich nicht. Viele Leute dieses Problem von dem falschen Winkel sehen; Sie dürfen nicht versuchen, jede Kinder Liste zu füllen, sondern die Beseitigung der Kinder Elemente aus der flachen Liste bekommen, dann wird es einfach.

Answer 3

Alternative Version, die normalerweise kompiliert, war ich nicht sicher, ob es ein Problem mit dem Code oben war.

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

Hier ist ein Beispiel, hoffe, das hilft

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

Die Korrektur am Beispiel gegeben durch 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();
    }