LINQ递归函数？

Question

让我们以这种n层深层结构为例:

public class SomeItem 
{
     public Guid ID { get;set; }
     public string Name { get; set; }
     public bool HasChildren { get;set; }
     public IEnumerable<SomeItem> Children { get; set; }
}

如果我希望得到的ID(在任何地方结构)的特定项目是有一些LINQ上帝,我可以用它来轻松搞定它在单个语句或做我必须如下使用一些递归函数:

   private SomeItem GetSomeItem(IEnumerable<SomeItem> items, Guid ID)
    {
        foreach (var item in items)
        {
            if (item.ID == ID)
            {
                return item;
            }
            else if (item.HasChildren)
            {
                return GetSomeItem(item.Children, ID);
            }
        }
        return null;
    }

Answer 1

LINQ并不能很好地"做"递归.你的解决方案看起来很合适 - 虽然我不确定HasChildren是否真的需要......为什么不用一个没有孩子的项目的空列表呢？

另一种方法是编写一个DescendantsAndSelf方法,它将返回所有后代(包括项目本身),类似这样的东西;

// Warning: potentially expensive!
public IEnumerable<SomeItem> DescendantsAndSelf()
{
    yield return this;
    foreach (var item in Children.SelectMany(x => x.DescendantsAndSelf()))
    {
        yield return item;
    }
}

但是,如果树很深,最终效率非常低,因为每个项目都需要"通过"其祖先的所有迭代器.Wes Dyer在博客中写到了这一点,显示了更高效的实施.

无论如何,如果你有这样的方法(但所实现的),你可以只用一个正常的"其中"条款找到一个项目(或第一/ FirstOrDefault等).

Answer 2

这是一个没有递归的。这避免了通过多层迭代器的成本，所以我认为它和它们一样有效。

    public static IEnumerable<T> IterateTree<T>(this T root, Func<T, IEnumerable<T>> childrenF)
    {
        var q = new List<T>() { root };
        while (q.Any())
        {
            var c = q[0];
            q.RemoveAt(0);
            q.AddRange(childrenF(c) ?? Enumerable.Empty<T>());
            yield return c;
        }
    }

像这样调用：

            var subtree = root.IterateTree(x => x. Children).ToList();