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

Question

我正在使用Entity Framework（版本6）将数据映射到递归层次结构中，它映射得很好。

我的问题是，我想要递归地获取层次结构中特定节点的所有子节点。

我可以很容易地使用Linq获取子节点：

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

有没有人知道一个干净的实现方法，可以递归地获取所有子元素？

- Keith Doran

---

可能是如何使用Entity Framework进行递归加载？的重复问题。 - BartoszKP

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

- Servy

---

谢谢 - 你能提供一个调用这个方法的例子吗？我已经尝试过：var descendents = db.ProcessHierarchyItems.Traverse(x => x.Id == id); - Keith Doran

@user3168594 lambda需要根据签名返回该节点的所有子节点，因此根据您的问题，它看起来应该是：x => x.Children。 - Servy

几乎完成了 - 我的 Linq 现在是：'var descendents = db.ProcessHierarchyItems.Where(x=>x.id == idOfParentNode).Traverse(x=>x.Children);' - Traverse 现在返回了所有子节点，但也包括父节点 - 这正确吗？ - Keith Doran

@user3168594 您完全可以根据自己的需求调整代码；我相信您能够根据这个答案找到解决方案。 - Servy

@Maxim 这个方法接受IEnumerable，而不是IQueryable，因此只能操作内存中的集合。它无法被转换为数据库查询。 - Servy

Answer 2

感谢Servy，我在您的代码基础上进行了扩展，以允许遍历单个项目以及集合。我找到这个方法是为了找出异常或任何内部异常是否属于某种类型，但它将有很多用途。

这里有一个包含示例、测试用例等的fiddle。 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);
        }
    }
}

- Duane McKinney

---

不确定我是否遵循适当的礼仪。我不知道根据另一个答案，编辑是否比新答案更合适。 - Duane McKinney

好的，我感觉我在重新发明轮子，而事实上确实如此。结合这个答案 Passing a single item as IEnumerable<T>，你可以使用SelectMany仅返回子项，并使用SelectMany().Contat(root)。 - Duane McKinney

而且SelectMany不是递归的，所以我的原始解决方案仍然有效。 - Duane McKinney

我尝试了你的解决方案并稍作修改以支持可空子项。也许你应该更新你的答案，以帮助一些遇到同样可空问题的人，但是做得很好！ - DirtyNative

Answer 3

试一试这个。虽然其他答案在建立枚举时会枚举枚举，但我们应该考虑在不枚举枚举的情况下构建它。

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

- shtse8

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

- ggrocco

---

看起来很酷，但我对参数（item、select和recurrence）有点困惑。您能否简要地描述一下它们是什么？谢谢。 - Mustafa Mohammadi

Answer 5

最简单的解决方案似乎是引入递归方法。仅使用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));

- BartoszKP

---

我定义了GetChildren如下：IEnumerable<ProcessHierarchyItem> GetChildren(ProcessHierarchyItem x) - 但是我收到了一个错误信息：“LINQ to Entities不认识方法'System.Collections.Generic.IEnumerable`1[RedOwlMvc.Models.ProcessHierarchyItem] GetChildren(RedOwlMvc.Models.ProcessHierarchyItem)'，这个方法无法转换为存储表达式。” - Keith Doran

@user3168594 哦，那么在这种情况下，我已将您的问题标记为重复。请阅读自动发布在您的问题下方的链接中的答案。 - BartoszKP

@user3168594 你也可以尝试我的简单修复 - 请查看编辑后的答案。 - BartoszKP

只有在我在“foreach”后添加了“yield return x”时，这才对我起作用。 - g t

@gt 是的，这取决于您是只想要叶子节点还是中间节点也要包括在内。 - BartoszKP