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

Question

我正在使用实体框架(版本6)映射到递归层次结构,它很好地映射.

我的问题是我想以递归方式获取层次结构中特定节点的所有子节点.

我使用Linq很容易得到子节点:

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

有人知道一个干净的实现,会递归地让所有孩子？

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

Answer 2

感谢Servy,我对你的代码进行了一些扩展,以允许迭代单个项目以及集合.我在寻找一种方法来查明异常或任何内部异常是否属于某种类型时遇到过,但这会有很多用途.

这里有一个小例子,测试用例等 .netnetfiddle 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);
        }
    }
}