Хороший и универсальный способ преобразования списка элементов в дерево

Ответ 1

Если вы хотите иметь универсальный метод, вам понадобится дополнительный класс:

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

Затем используйте его с помощью этого помощника:

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 id</param>
    /// <param name="parent_id_selector">Function extracting item 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))
            };
        }
    }
}

Использование:

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

Тестирование:

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

Выход

Sport
    Balls
    Shoes
Electronics
    Cameras
        Lenses  
        Tripod
    Computers
        Laptops
Empty

Ответ 2

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

Вы получите сложность O(n*n).

Более оптимизированный способ - использовать таблицы Lookup:

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

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

Что дает вам O(2*n) ≈ O(n)

В результате у вас будет следующая структура (показана LinqPad):

Ответ 3

Вы можете использовать ниже запрос базы данных, чтобы получить список категорий с отношениями родитель-потомок:

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

Надеюсь, это поможет вам.

Ответ 4

Вот небольшой пример, который я взбивал. Это довольно "общий".

Можно также сделать общий подход, определив интерфейс (который затем позволит упростить аргументы функции), однако я решил не делать этого. В любом случае функции "mapper" и селектора позволяют это работать в разных типах.

Также обратите внимание, что это не очень эффективная реализация (поскольку она поддерживает все возможные дочерние элементы для всех поддеревьев и многократно повторяет их), но может быть подходящей для данной задачи. В прошлом я также использовал подход Dictionary<key,collection>, который имеет лучшие границы, но мне не хотелось писать его таким образом:)

Это выполняется как "программа LINQPad С#". Наслаждайтесь!

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

Ответ 5

используя алгоритм Илья Иванов (см. выше), я сделал метод более общим.

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

использование:

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