LINQ扩展方法：如何递归地在集合中查找子元素

Question

我已经熟悉Linq，但对扩展方法的理解很少，希望有人能帮助我。所以我有这个层级集合伪代码：

class Product
  prop name
  prop type
  prop id
  prop List<Product> children

我有一个产品列表 List products。

是否有一种方法可以通过扩展方法按 ID 在该集合中查找产品？换句话说，我需要在层次结构中的某个位置找到一个项目。

- sushiBite

---

你的意思是：productsList.Where(x => x.Id == yourId);？ - Kirk Woll

还是使用productsList.FirstOrDefault(x => x.Id == yourId);？这将返回一个单一的对象，如果没有找到匹配的对象则返回null。 - Albin Sunnanbo

不，我的意思是我需要查看ProductsList和ProductList->Product->Children。这就是我的问题，我可以使用递归方法来解决它，但我想知道是否有可能使用linq-extension来解决。 - sushiBite

Answer 1

以下是一种通用解决方案，一旦找到匹配项就会短路遍历层次结构。

public static class MyExtensions
{
    public static T FirstOrDefaultFromMany<T>(
        this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector,
        Predicate<T> condition)
    {
        // return default if no items
        if(source == null || !source.Any()) return default(T);

        // return result if found and stop traversing hierarchy
        var attempt = source.FirstOrDefault(t => condition(t));
        if(!Equals(attempt,default(T))) return attempt;

        // recursively call this function on lower levels of the
        // hierarchy until a match is found or the hierarchy is exhausted
        return source.SelectMany(childrenSelector)
            .FirstOrDefaultFromMany(childrenSelector, condition);
    }
}

在您的情况下使用它：

var matchingProduct = products.FirstOrDefaultFromMany(p => p.children, p => p.Id == 27);

- Jay

---

嗨，我对这段代码进行了一处小改动，现在它可以正常工作了 :) 我将这个 if(Equals(attempt,default(T))) return attempt; 改成了 if(Equals(attempt != null) return attempt;现在它运行得非常好感谢大家的帮助。 - sushiBite

@sushiBite 我认为应该是 if(!Equals(attempt, default(T))) return attempt;，因为 T 的默认值可能不是 null（如果 T 是值类型）。 - Jay

Answer 2

您可以使用此扩展方法平展您的树形结构：

static IEnumerable<Product> Flatten(this IEnumerable<Product> source)
{
    return source.Concat(source.SelectMany(p => p.Children.Flatten()));
}

使用方法：

var product42 = products.Flatten().Single(p => p.Id == 42);

请注意，这可能不是非常快的。如果您需要通过ID重复查找产品，请创建一个字典：

var dict = products.Flatten().ToDictionary(p => p.Id);

var product42 = dict[42];

- dtb

---

很好，我喜欢那个Flatten方法。如果我没有弄错的话，它会进行广度优先迭代（编辑：我错了，它并不是广度优先，但问题仍然是相关的）。这是否意味着如果产品是列表中的第一项，并且您使用First而不是Single，它就不会展开整个层次结构？ LINQ的延迟执行是否会在这里有所帮助？ - Bubblewrap

这看起来是一个不错的解决方案，但它忽略了子列表可能为null的情况。 - Gabe

@Bubblewrap：你说得对。如果你使用First，由于延迟执行的机制，Flatten只会扁平化所需的部分。 - dtb

Answer 3

我正在对dtb的解决方案进行重构，以使其更加通用。请尝试使用此扩展方法：

public static IEnumerable<T> Flatten<T, R>(this IEnumerable<T> source, Func<T, R> recursion) where R : IEnumerable<T>
{
    return source.SelectMany(x => (recursion(x) != null && recursion(x).Any()) ? recursion(x).Flatten(recursion) : null)
                 .Where(x => x != null);
}

你可以像这样使用它：

productList.Flatten(x => x.Children).Where(x => x.ID == id);

- Jonathas Costa

Answer 4

static IEnumerable<Product> FindProductById(this IEnumerable<Product> source, int id) 
{
    return source.FirstOrDefault(product => product.Id = id) ?? source.SelectMany(product => product.Children).FindProductById(id);
}

- Jimmy Hoffa

Answer 5

一种使用yield来优化所需枚举的替代方案。

public static IEnumerable<T> SelectManyRecursive<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector)
{
    if (source == null)
        throw new ArgumentNullException("source");

    foreach (var i in source)
    {
        yield return i;
        var children = childrenSelector(i);
        if (children != null)
        {
            foreach (var child in SelectManyRecursive(children, childrenSelector))
            {
                yield return child;
            }
        }
    }
}

然后你可以通过调用像FirstOrDefault这样的方法来查找匹配项：

    var match = People.SelectManyRecursive(c => c.Children)
                      .FirstOrDefault(x => x.Id == 5);

- kampsj

Answer 6

如果您想要“子迭代”并在产品列表中查找子项：

List<Product>
    Product
       Child
       Child
       Child
       Child
    Product
       Child
       Child *find this one
       Child

您可以使用现有的SelectMany扩展方法。SelectMany可用于“展平”两级层次结构。

这里有一个关于SelectMany的很好的解释：http://team.interknowlogy.com/blogs/danhanan/archive/2008/10/10/use-linq-s-selectmany-method-to-quot-flatten-quot-collections.aspx

您的语法应该像这样：

List<Product> p = GetProducts(); //Get a list of products
var child = from c in p.SelectMany(p => p.Children).Where(c => c.Id == yourID);

- Dave Swersky

---

好的，这很不错，但是每个产品的层次结构可能会有x个级别深度，因此产品A可以有3个子级、5个孙子级和100个曾孙级。而产品B可能只有1个子级和没有孙子级，我无法知道。如果我理解正确的话，我需要为层次结构的每个级别使用SelectMany()函数？ - sushiBite

你可以将SelectMany链接在一起，直到达到所需的级别。 - Dave Swersky