递归层次结构-使用Linq的递归查询

mitkmikd  于 2023-05-20  发布在  其他
关注(0)|答案(5)|浏览(135)

我使用EntityFramework(版本6)来Map到递归层次结构,它Map得很好。
我的问题是,我想递归地获得层次结构中特定节点的ALL子节点。
我使用Linq很容易地获得子节点:

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

有谁知道一个干净的实现,将递归地获得所有的孩子?

mpgws1up

mpgws1up1#

虽然可以在这里使用递归方法,但您可以使用显式堆栈来遍历此树结构,以避免使用堆栈空间,堆栈空间对于大型树结构并不总是足够的。这样的方法作为迭代器块也非常好,迭代器块在递归时比常规方法昂贵得多,所以这也会表现得更好:

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

zpjtge222#

感谢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);
        }
    }
}
polhcujo

polhcujo3#

试试这个。当其他答案在构建可枚举对象时枚举可枚举对象时,我们应该考虑构建它而不枚举它。

public static IEnumerable<T> SelectRecursively<T>(this T source, Func<T, IEnumerable<T>> selector)
{
        return selector(source).SelectMany(x => x.SelectRecursively(selector).Prepend(x));
}
8i9zcol2

8i9zcol24#

最简单的解决方案似乎是引入递归方法。你不能仅仅通过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));
q5lcpyga

q5lcpyga5#

我更喜欢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));
    }

相关问题