Crear objetos de jerarquía a partir de una lista plana de padre / hijo

Question

Tengo una lista de elementos en una jerarquía, y estoy tratando de analizar esta lista en una jerarquía real de objetos. Estoy usando recorrido modificado del árbol de pedidos anticipados para almacenar / iterar a través de esta lista, y lo que tengo es un subconjunto del árbol, incluidos todos los niños, ordenados por su "izquierda" valor.

Por ejemplo, dado el árbol:

• Artículo A
  • Artículo A.1
  • Artículo A.2
    • Elemento A.2.2
• Artículo B
  • Artículo B.1
• Elemento C

Me sale la lista:

• Artículo A, Artículo A.1, Artículo A.2, Artículo A.2.2, Artículo B, Artículo B.1, Artículo C

(Esto está en el orden del valor "izquierda" de la configuración del árbol de preorden modificado).

Lo que quiero hacer es analizar esto en objetos que contengan la estructura real del árbol, por ejemplo:

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

La lista plana se devuelve como una Lista de TreeObjects, y cada TreeObject tiene propiedades para ID, ParentID, Left y Right. Lo que estoy buscando es una función:

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

que toma la lista plana y devuelve una lista anidada.

En otras palabras:

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

No sé cómo hacer esto: hacer un seguimiento de los padres y ser capaz de lidiar con un salto más grande (por ejemplo, Artículo A.2.2 - > Artículo B).

---

Editar: estoy buscando una solución de fuerza no bruta aquí (por ejemplo, no hacer bucles varias veces, mover elementos a nodos secundarios, hasta que solo queden los padres de nivel superior). Supongo que hay un método elegante que puede recorrer una vez, y solo colocar elementos según sea necesario.

Recuerde, siempre están en un orden jerárquico (ya que estoy usando MPTT), por lo que un elemento dado siempre será hijo o hermano del elemento anterior, o al menos compartirá un padre con el elemento anterior. Nunca va a venir a otro lugar del árbol.

Answer 1

Aquí está la función que terminé escribiendo. Estoy usando MPTT para almacenar objetos, por lo que la lista está en el orden del valor 'izquierdo', lo que básicamente significa que el padre siempre aparece antes que cualquier elemento de la lista. En otras palabras, el elemento referenciado por item.ParentID siempre se ha agregado (excepto en el caso de los nodos de nivel superior o raíz).

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

y una prueba simple (que funciona en 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();
}

Resultados:

Como estoy actualizando esto 5 años después, aquí hay una versión recursiva de 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

Supongo que ya conoce el padre de todos los elementos .

Todo lo que necesita hacer es iterar a través de todos los elementos de la lista una vez y agregar el elemento actual a la lista secundaria de sus padres. Solo mantenga los elementos sin padres en la lista anidada de destino.

Aquí hay un pseudocódigo:

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

En cuanto a los padres, por lo que puedo ver en su ejemplo, es posible que necesite analizar el nombre y construir una pila a medida que avanza en la lista.

Este problema parece difícil pero realmente no lo es. Mucha gente ve este problema desde el ángulo equivocado; no debe intentar llenar todas las listas de niños, sino deshacerse de los elementos de la lista plana, entonces se vuelve fácil.

Answer 3

Versión alternativa que se compila normalmente, no estaba seguro de si había un problema con el código anterior.

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

Aquí hay un ejemplo, espero que esto ayude

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

Corregir el ejemplo dado por 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();
    }