c# - Cree una lista de tipos de árboles al verificar recursivamente la relación padre-hijo

recursion tree

Question

Tengo una clase que tiene una lista de sí misma para que pueda representarse en una estructura de árbol.

Estoy sacando una lista plana de estas clases y quiero desdoblarla.

public class Group
{
     public int ID {get;set;}

     public int? ParentID {get;set;}

     public List<Group> Children {get;set;}

}

Quiero poder hacer lo siguiente

List<Group> flatList = GetFlatList() //I CAN ALREADY DO THIS
List<Group> tree = BuildTree(flatList);

El ParentID se relacionaba con la propiedad ID en su grupo principal si eso no era obvio.

EDITAR

Existe cierta confusión en cuanto a por qué estoy devolviendo una lista y no un solo objeto.

Estoy creando un elemento de la interfaz de usuario que tiene una lista de elementos, cada uno de por qué tiene un hijo. Así que la lista inicial NO tiene un nodo raíz. Parece que todas las soluciones hasta ahora no funcionan.

Lo que esto significa es que esencialmente necesito una lista de estructuras de tipo de árbol usando la clase de Grupo.

Answer 1

Aquí es cómo puedes hacer esto en una línea:

static void BuildTree(List<Group> items)
{
    items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
}

Puedes llamarlo así:

BuildTree(flatList);

Si al final desea obtener los nodos cuyo padre es nulo (es decir, los nodos de nivel superior), simplemente puede hacer esto:

static List<Group> BuildTree(List<Group> items)
{
    items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
    return items.Where(i => i.ParentID == null).ToList();
}

Y si desea convertirlo en un método de extensión, puede agregar this en la firma del método:

static List<Group> BuildTree(this List<Group> items)

Entonces puedes llamarlo así:

var roots = flatList.BuildTree();

Answer 2

No tengo idea de por qué quiere que su método BuildTree devuelva la List<Group> : el árbol necesita tener un nodo raíz, por lo que debe esperar que devuelva un solo elemento del Group , no una lista.

Me gustaría crear un método de extensión en IEnumerable<Group> :

public static class GroupEnumerable
{
    public static IList<Group> BuildTree(this IEnumerable<Group> source)
    {
        var groups = source.GroupBy(i => i.ParentID);

        var roots = groups.FirstOrDefault(g => g.Key.HasValue == false).ToList();

        if (roots.Count > 0)
        {
            var dict = groups.Where(g => g.Key.HasValue).ToDictionary(g => g.Key.Value, g => g.ToList());
            for (int i = 0; i < roots.Count; i++)
                AddChildren(roots[i], dict);
        }

        return roots;
    }

    private static void AddChildren(Group node, IDictionary<int, List<Group>> source)
    {
        if (source.ContainsKey(node.ID))
        {
            node.Children = source[node.ID];
            for (int i = 0; i < node.Children.Count; i++)
                AddChildren(node.Children[i], source);
        }
        else
        {
            node.Children = new List<Group>();
        }
    }
}

Uso

var flatList = new List<Group>() {
    new Group() { ID = 1, ParentID = null },    // root node
    new Group() { ID = 2, ParentID = 1 },
    new Group() { ID = 3, ParentID = 1 },
    new Group() { ID = 4, ParentID = 3 },
    new Group() { ID = 5, ParentID = 4 },
    new Group() { ID = 6, ParentID = 4 }
};


var tree = flatList.BuildTree();

Answer 3

Probé las soluciones sugeridas y descubrí que nos brindan la complejidad de O (n ^ 2).

En mi caso (tengo alrededor de 50k elementos para ser integrados en el árbol) fue completamente inaceptable.

Llegué a la siguiente solución (asumiendo que cada elemento tiene solo un padre y todos los padres existen en la lista) con complejidad O (n * log (n)) [n veces getById, getById tiene complejidad O (log (n))] :

static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems)
{
    var byIdLookup = flatItems.ToLookup(i => i.Id);
    foreach (var item in flatItems)
    {
        if (item.ParentId != null)
        {
            var parent = byIdLookup[item.ParentId.Value].First();
            parent.Children.Add(item);
        }
    }
    return flatItems.Where(i => i.ParentId == null).ToList();
}

Fragmento de código completo:

class Program
{
    static void Main(string[] args)
    {
        var flatItems = new List<Item>()
        {
            new Item(1),
            new Item(2),
            new Item(3, 1),
            new Item(4, 2),
            new Item(5, 4),
            new Item(6, 3),
            new Item(7, 5),
            new Item(8, 2),
            new Item(9, 3),
            new Item(10, 9),
        };
        var treeNodes = BuildTreeAndReturnRootNodes(flatItems);
        foreach (var n in treeNodes)
        {
            Console.WriteLine(n.Id + " number of children: " + n.Children.Count);
        }
    }
    // Here is the method
    static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems)
    {
        var byIdLookup = flatItems.ToLookup(i => i.Id);
        foreach (var item in flatItems)
        {
            if (item.ParentId != null)
            {
                var parent = byIdLookup[item.ParentId.Value].First();
                parent.Children.Add(item);
            }
        }
        return flatItems.Where(i => i.ParentId == null).ToList();
    }
    class Item
    {
        public readonly int Id;
        public readonly int? ParentId;

        public Item(int id, int? parent = null)
        {
            Id = id;
            ParentId = parent;
        }
        public readonly List<Item> Children = new List<Item>();
    }
}