online - test dome c#

Manera agradable y universal de convertir la lista de artículos al árbol

Question

Tengo lista de categorias:

╔════╦═════════════╦═════════════╗
║ Id ║ Name        ║ Parent_id   ║
╠════╬═════════════╬═════════════╣
║ 1  ║ Sports      ║ 0           ║
║ 2  ║ Balls       ║ 1           ║
║ 3  ║ Shoes       ║ 1           ║
║ 4  ║ Electronics ║ 0           ║
║ 5  ║ Cameras     ║ 4           ║
║ 6  ║ Lenses      ║ 5           ║
║ 7  ║ Tripod      ║ 5           ║
║ 8  ║ Computers   ║ 4           ║
║ 9  ║ Laptops     ║ 8           ║
║ 10 ║ Empty       ║ 0           ║
║ -1 ║ Broken      ║ 999         ║
╚════╩═════════════╩═════════════╝ 

Cada categoría tiene un padre. Cuando el padre es 0, eso significa que es la categoría raíz.

¿Cuál es la mejor manera de convertirlo en estructura de árbol como abajo?

En otras palabras, cómo traer datos de esta estructura:

class category
{
    public int Id;
    public int ParentId;
    public string Name;
}

En este:

class category
{
    public int Id;
    public int ParentId;
    public string Name;

    public List<Category> Subcategories;
}

de manera universal? // Universal significa no solo para la clase mencionada.

¿Tienes algunas ideas inteligentes? ;)

Datos:

var categories = new List<category>() {
    new category(1, "Sport", 0),
    new category(2, "Balls", 1),
    new category(3, "Shoes", 1),
    new category(4, "Electronics", 0),
    new category(5, "Cameras", 4),
    new category(6, "Lenses", 5),  
    new category(7, "Tripod", 5), 
    new category(8, "Computers", 4),
    new category(9, "Laptops", 8),
    new category(10, "Empty", 0),
    new category(-1, "Broken", 999),
};

Answer 1

Aquí hay un pequeño ejemplo que hice. Es bastante "genérico".

También se podría hacer un enfoque genérico definiendo una interfaz (que luego permitiría simplificar los argumentos de la función); sin embargo, elegí no hacerlo. En cualquier caso, las funciones de "mapeador" y selector permiten que funcione en distintos tipos.

También tenga en cuenta que esta no es una implementación muy eficiente (ya que se mantiene alrededor de todos los hijos posibles para todos los subárboles y se repite repetidamente), pero puede ser adecuada para la tarea dada. En el pasado, también he usado un enfoque de Dictionary<key,collection> , que tiene mejores límites, pero no tenía ganas de escribirlo así :)

Esto se ejecuta como un "Programa LINQPad C #". ¡Disfrutar!

public static IEnumerable<TJ> GenerateTree<T, TK, TJ>(this IEnumerable<T> items,
                                                      Func<T, TK> idSelector,
                                                      Func<T, TK> parentSelector,
                                                      Func<T, IEnumerable<T>, TJ> outSelector)
{
       IList<T> mlist = items.ToList();

       ILookup<TK, T> mcl = mlist.ToLookup(parentSelector);

       return mlist.Select(cat => outSelector(cat, mcl[idSelector(cat)]));
}

Answer 2

Puede usar la siguiente consulta de base de datos para obtener la lista de categorías con relaciones padre-hijo:

WITH tree (categoryId, parentId, level, categoryName, rn) as 
(
   SELECT categoryId, parentid, 0 as level, categoryName,

       convert(varchar(max),right(row_number() over (order by categoryId),10)) rn
   FROM Categories
   WHERE parentid = 0

   UNION ALL

   SELECT c2.categoryId, c2.parentid, tree.level + 1, c2.categoryName,

       rn + ''/'' + convert(varchar(max),right(row_number() over 
       (order by tree.categoryId),10))
   FROM Categories c2 

     INNER JOIN tree ON tree.categoryId = c2.parentid
)

SELECT *
FROM tree
order by RN

Espero que esto lo pueda ayudar.

Answer 3

Si quieres tener un método universal necesitarás una clase adicional:

public class TreeItem<T>
{
    public T Item { get; set; }
    public IEnumerable<TreeItem<T>> Children { get; set; }
}

Entonces utilízalo con este ayudante:

internal static class GenericHelpers
{
    /// <summary>
    /// Generates tree of items from item list
    /// </summary>
    /// 
    /// <typeparam name="T">Type of item in collection</typeparam>
    /// <typeparam name="K">Type of parent_id</typeparam>
    /// 
    /// <param name="collection">Collection of items</param>
    /// <param name="id_selector">Function extracting item''s id</param>
    /// <param name="parent_id_selector">Function extracting item''s parent_id</param>
    /// <param name="root_id">Root element id</param>
    /// 
    /// <returns>Tree of items</returns>
    public static IEnumerable<TreeItem<T>> GenerateTree<T, K>(
        this IEnumerable<T> collection,
        Func<T, K> id_selector,
        Func<T, K> parent_id_selector,
        K root_id = default(K))
    {
        foreach (var c in collection.Where(c => parent_id_selector(c).Equals(root_id)))
        {
            yield return new TreeItem<T>
            {
                Item = c,
                Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c))
            };
        }
    }
}

Uso:

var root = categories.GenerateTree(c => c.Id, c => c.ParentId);

Pruebas:

static void Test(IEnumerable<TreeItem<category>> categories, int deep = 0)
{
    foreach (var c in categories)
    {
        Console.WriteLine(new String(''/t'', deep) + c.Item.Name);
        Test(c.Children, deep + 1);
    }
}
// ...
Test(root);

Salida

Sport
    Balls
    Shoes
Electronics
    Cameras
        Lenses  
        Tripod
    Computers
        Laptops
Empty

Answer 4

Usando el algoritmo Ilya Ivanov ( ver arriba ), hice el método más genérico.

IEnumerable<Category> mlc = GenerateTree(categories,
                                         c => c.Id, 
                                         c => c.ParentId,
                                         (c, ci) => new Category
                                         {
                                              Id = c.Id,
                                              Name = c.Name,
                                              ParentId = c.ParentId ,
                                              Subcategories = ci
                                         });

uso:

// F - flat type
// H - hiearchial type
IEnumerable<H> MakeHierarchy<F,H>(
    // Remaining items to process
    IEnumerable<F> flat,
    // Current "parent" to look for
    object parentKey,
    // Find key for given F-type
    Func<F,object> key,
    // Convert between types
    Func<F,IEnumerable<H>,H> mapper,
    // Should this be added as immediate child?
    Func<F,object,bool> isImmediateChild) {

    var remainder = flat.Where(f => !isImmediateChild(f, parentKey))
        .ToList();

    return flat
        .Where(f => isImmediateChild(f, parentKey))
        .Select(f => {
            var children = MakeHierarchy(remainder, key(f), key, mapper, isImmediateChild);
            return mapper(f, children);
        });
}

class category1
{
    public int Id;
    public int ParentId;
    public string Name;

    public category1(int id, string name, int parentId) {
        Id = id;
        Name = name;
        ParentId = parentId;
    }
};

class category2
{
    public int Id;
    public int ParentId;
    public string Name;

    public IEnumerable<category2> Subcategories;
};

List<category1> categories = new List<category1>() {
    new category1(1, "Sport", 0),
    new category1(2, "Balls", 1),
    new category1(3, "Shoes", 1),
    new category1(4, "Electronics", 0),
    new category1(5, "Cameras", 4),
    new category1(6, "Lenses", 5),  
    new category1(7, "Tripod", 5), 
    new category1(8, "Computers", 4),
    new category1(9, "Laptops", 8),
    new category1(10, "Empty", 0),
    new category1(-1, "Broken", 999),
};

object KeyForCategory (category1 c1) {
    return c1.Id;
}

category2 MapCategories (category1 c1, IEnumerable<category2> subs) {
    return new category2 {
        Id = c1.Id,
        Name = c1.Name,
        ParentId = c1.ParentId,
        Subcategories = subs,
    };
}

bool IsImmediateChild (category1 c1, object id) {
    return c1.ParentId.Equals(id);
}

void Main()
{
    var h = MakeHierarchy<category1,category2>(categories, 0,
        // These make it "Generic". You can use lambdas or whatever;
        // here I am using method groups.
        KeyForCategory, MapCategories, IsImmediateChild);
    h.Dump();
}

Answer 5

foreach (var cat in categories)
{
    cat.Subcategories = categories.Where(child => child.ParentId == cat.Id)
                                  .ToList();
}

Obtendrás O(n*n) complejidad.

Una forma más optimizada es usar tablas de búsqueda:

var childsHash = categories.ToLookup(cat => cat.ParentId);

foreach (var cat in categories)
{
    cat.Subcategories = childsHash[cat.Id].ToList();
}

Lo que te da O(2*n) ≈ O(n)

Como resultado, tendrás la siguiente estructura (que se muestra desde LinqPad):