如何使用 LINQ to Entity 选择递归嵌套实体

Question

我有一个名为 Category 的实体，该实体包含一个名为 ChildCategories 的 IEnumerable。一个类别可以有这些子类别，这些子类别可以有自己的子类别，依此类推。

假设我已经选择了顶级父类别，我想获取所有子类别及其子类别等，以便我拥有该类别的所有分层子类别。我希望将其扁平化并与初始类别一起返回。我尝试过创建类似

    public static IEnumerable<T> AllChildren<T>(this IEnumerable<T> items, 
        Func<T, IEnumerable<T>> children, bool includeSelf)
    {
        foreach (var item in items)
        {
            if (includeSelf)
            {
                yield return item;
            }
            if (children != null)
            {
                foreach (var a in children(item))
                {
                    yield return a;
                    children(a).AllChildren(children, false);
                }
            }
        }
    }

使用 SelectMany 方法后会变得扁平的东西，但还没有完全明白。

Answer 1

仅仅使用 LINQ 是无法完成这样的事情的； LINQ 不支持开箱即用地遍历未知级别的节点。

此外，您没有任何真正的方法来展平结构，所需的属性数量未知（因为它与树深度相关，而树深度也是未知的）。

我建议使用 C# 中的迭代器 来压平树，诸如此类像这样：

static IEnumerable<T> Flatten(this IEnumerable<T> source, 
    Func<T, IEnumerable<T>> childrenSelector)
{
    // Do standard error checking here.

    // Cycle through all of the items.
    foreach (T item in source)
    {
         // Yield the item.
         yield return item;

         // Yield all of the children.
         foreach (T child in childrenSelector(item).
             Flatten(childrenSelector))
         {
             // Yield the item.
             yield return child;
         }            
    }
}

然后，您可以调用扩展方法并将结果放入 List 中；它和你能得到的一样平坦。

请注意，您可以很容易地抛出 StackOverflowException 如果层次结构足够深。为此，您确实想使用这种非递归方法：

static IEnumerable<T> Flatten(this IEnumerable<T> source, 
    Func<T, IEnumerable<T>> childSelector)
{
    // Do standard error checking here.

    // Create a stack for recursion.  Push all of the items
    // onto the stack.
    var stack = new Stack<T>(source);

    // While there are items on the stack.
    while (stack.Count > 0)
    {
        // Pop the item.
        T item = stack.Pop();

        // Yield the item.
        yield return item;

        // Push all of the children on the stack.
        foreach (T child in childSelector(item)) stack.Push(child);
    }
}

Stack 实例位于堆上而不是调用堆栈上，因此您不会耗尽调用堆栈空间。

此外，您还可以将 Stack 更改为 Queue 如果您需要不同的返回语义（或者您可以以不同的方式遍历子级），如果您需要特定的顺序。

如果您需要非常具体的顺序，我建议仅在您有大量需要遍历的项目（这使得调用 OrderBy 对返回值禁止。

Answer 2

在他的博客文章 遍历层次结构LINQ 到层次结构
, Arjan Einbu 描述了一种扁平化层次结构以方便查询的方法：

我可以制作一个通用的扩展方法来扁平化任何层次结构吗？ [...]

为此，我们需要分析该方法的哪些部分需要被换出。这就是 TreeNode 的 Nodes 属性。我们可以通过其他方式访问它吗？是的，我认为代表可以帮助我们，所以让我们尝试一下：

public static IEnumerable; FlattenHierarchy（这个 T 节点， 
                             Func> getChildEnumerator)
{
    产量返回节点；
    if(getChildEnumerator(节点)！= null)
    {
        foreach（getChildEnumerator（节点）中的var child）
        {
            foreach(var childOr后代 
                      在 child.FlattenHierarchy(getChildEnumerator))
            {
                产量返回子或后代；
            }
        }
    }
}

casperOne 在他的回答中也描述了这一点，以及尝试使用 LINQ 直接遍历层次结构所固有的问题。

Answer 3

casperOnes 代码存在一些问题。这有效：

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector)
    {
        // Do standard error checking here.

        // Cycle through all of the items.
        foreach (T item in source)
        {
            // Yield the item.
            yield return item;

            // Yield all of the children.
            foreach (T child in childrenSelector(item).Flatten(childrenSelector))
            {
                // Yield the item.
                yield return child;
            }
        }
    }