Рекурсивная иерархия - рекурсивный запрос с использованием Linq

Я использую Entity Framework (версия 6) для сопоставления с рекурсивной иерархией и хорошо ее рисует.

Моя проблема в том, что я хочу рекурсивно получить ВСЕ дочерние узлы определенного node в иерархии.

Я получаю дочерние узлы довольно легко с помощью Linq:

var recursiveList = db.ProcessHierarchyItems
            .Where(x => x.id == id)
            .SelectMany(x => x.Children);

Кто-нибудь знает о чистой реализации, которая будет рекурсивно получать всех детей?

Спасибо, Кит.

Ответ 1

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

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items, 
    Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>(items);
    while(stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach(var child in childSelector(next))
            stack.Push(child);
    }
}

Ответ 2

Спасибо Servy, я немного расширил ваш код, чтобы разрешить итерации отдельных элементов, а также коллекций. Я наткнулся на поиск способа узнать, было ли исключение или какие-либо внутренние исключения определенного типа, но это будет иметь много применений.

Вот сценарий с примерами, тестовыми примерами и т.д. dotnetfiddle LinqTraversal

Просто помощники:

public static class LinqRecursiveHelper
{
    /// <summary>
    /// Return item and all children recursively.
    /// </summary>
    /// <typeparam name="T">Type of item.</typeparam>
    /// <param name="item">The item to be traversed.</param>
    /// <param name="childSelector">Child property selector.</param>
    /// <returns></returns>
    public static IEnumerable<T> Traverse<T>(this T item, Func<T, T> childSelector)
    {
        var stack = new Stack<T>(new T[] { item });

        while (stack.Any())
        {
            var next = stack.Pop();
            if (next != null)
            {
                yield return next;
                stack.Push(childSelector(next));
            }
        }
    }

    /// <summary>
    /// Return item and all children recursively.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="item"></param>
    /// <param name="childSelector"></param>
    /// <returns></returns>
    public static IEnumerable<T> Traverse<T>(this T item, Func<T, IEnumerable<T>> childSelector)
    {
        var stack = new Stack<T>(new T[] { item });

        while (stack.Any())
        {
            var next = stack.Pop();
            //if(next != null)
            //{
            yield return next;
            foreach (var child in childSelector(next))
            {
                stack.Push(child);
            }
            //}
        }
    }

    /// <summary>
    /// Return item and all children recursively.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="items"></param>
    /// <param name="childSelector"></param>
    /// <returns></returns>
    public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items,
      Func<T, IEnumerable<T>> childSelector)
    {
        var stack = new Stack<T>(items);
        while (stack.Any())
        {
            var next = stack.Pop();
            yield return next;
            foreach (var child in childSelector(next))
                stack.Push(child);
        }
    }
}

Ответ 3

Простейшее решение, похоже, вводит рекурсивный метод. Вы не можете получить рекурсивный результат только по LINQ:

IEnumerable<X> GetChildren(X x)
{
    foreach (var rChild in x.Children.SelectMany(child => GetChildren(child)))
    {
        yield return rChild;
    }
}

Если у вас есть ленивая загрузка, тогда это должно работать:

var recursiveList = db.ProcessHierarchyItems
        .Where(x => x.id == id)
        .AsEnumerable()
        .SelectMany(x => GetChildren(x));

Ответ 4

Мне больше нравится linq-способ сделать рекурсивный.

public static IEnumerable<TReturn> Recursive<TItem, TReturn>(this TItem item, Func<TItem, IEnumerable<TReturn>> select, Func<TItem, IEnumerable<TItem>> recurrence)
    {
        return select(item).Union(recurrence(item).Recursive(select, recurrence));
    }