logo标签列表

如何使用Linq搜索分层数据

c#linq
16

我需要在一棵树中搜索可能在任何位置的数据。如何使用linq实现？

class Program
{
    static void Main(string[] args) {

        var familyRoot = new Family() {Name = "FamilyRoot"};

        var familyB = new Family() {Name = "FamilyB"};
        familyRoot.Children.Add(familyB);

        var familyC = new Family() {Name = "FamilyC"};
        familyB.Children.Add(familyC);

        var familyD = new Family() {Name = "FamilyD"};
        familyC.Children.Add(familyD);

        //There can be from 1 to n levels of families.
        //Search all children, grandchildren, great grandchildren etc, for "FamilyD" and return the object.


    }
}

public class Family {
    public string Name { get; set; }
    List<Family> _children = new List<Family>();

    public List<Family> Children {
        get { return _children; }
    }
}
8个回答
10

That's an extension to It'sNotALie.s answer.

public static class Linq
{
    public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector)
    {
        return selector(source).SelectMany(c => Flatten(c, selector))
                               .Concat(new[] { source });
    }
}

示例测试用法：

var result = familyRoot.Flatten(x => x.Children).FirstOrDefault(x => x.Name == "FamilyD");

返回familyD对象。

您也可以在IEnumerable<T>源上使用它：

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
{
    return source.SelectMany(x => Flatten(x, selector))
        .Concat(source);
}
1
@GregHollywood 我写了一篇关于这个问题和解决方案的博客文章。你可以在这里查看：http://mjuraszek.blogspot.com/2013/08/querying-hierarchical-data-using-linq.html - MarcinJuraszek
尽管您博客中的内容是正确的，但在IEnumerable<T>上实现“flatten”并不正确。这将创建重复项... - Rashack
@Rashack，我没有看到这个问题，尽管每个返回的节点对象仍将具有其完整的子级。 - Marc L.
@Rashack，我收回之前的话，最后一个例子会重复根节点；正在编辑。 - Marc L.
8

另一种不使用递归的解决方案...

var result = FamilyToEnumerable(familyRoot)
                .Where(f => f.Name == "FamilyD");


IEnumerable<Family> FamilyToEnumerable(Family f)
{
    Stack<Family> stack = new Stack<Family>();
    stack.Push(f);
    while (stack.Count > 0)
    {
        var family =  stack.Pop();
        yield return family;
        foreach (var child in family.Children)
            stack.Push(child);
    }
}
3

简单：

familyRoot.Flatten(f => f.Children);
//you can do whatever you want with that sequence there.
//for example you could use Where on it and find the specific families, etc.

IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector)
{
    return selector(source).SelectMany(c => Flatten(selector(c), selector))
                           .Concat(new[]{source});
}
这看起来非常不错，我正在尝试让它工作。但是它告诉我：“无法从使用中推断类型参数。请明确指定类型参数。” - Greg Gum
@GregHollywood，你能给我展示一些实际的代码吗？我感觉顶层对象和子对象不是同一种类型... - It'sNotALie.
我只是在尝试在示例应用程序中使用它。我刚刚将您的答案添加到上面。如果您将其粘贴到VS中，您将看到编译器消息。 - Greg Gum
1
我喜欢Kenneth Bo Christensen使用堆栈的答案，它很好用，易于阅读，速度快（而且不使用递归）。唯一不好的是它会颠倒子项的顺序（因为堆栈是先进先出）。如果排序顺序对您不重要，那么没问题。如果有需要，可以在foreach循环中使用selector(current).Reverse()轻松实现排序（其余代码与Kenneth的原始帖子相同）...
public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector)
{            
    var stack = new Stack<T>();
    stack.Push(source);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var child in selector(current).Reverse())
            stack.Push(child);
    }
}
1
所以，最简单的选择是编写一个函数来遍历您的层次结构并生成单个序列。然后将其放置在LINQ操作的开头，例如：
    IEnumerable<T> Flatten<T>(this T source)
    {
      foreach(var item in source) {
        yield item;
        foreach(var child in Flatten(item.Children)
          yield child;
      }
    }

要简单调用：familyRoot.Flatten().Where(n => n.Name == "Bob");
稍微改一下，就可以让你快速忽略整个分支：
    IEnumerable<T> Flatten<T>(this T source, Func<T, bool> predicate)
    {
      foreach(var item in source) {
         if (predicate(item)) {          
            yield item;
            foreach(var child in Flatten(item.Children)
               yield child;
      }
    }

那么你可以执行如下操作：family.Flatten(n => n.Children.Count > 2).Where(...)

0

对于It'sNotALie.，MarcinJuraszek和DamienG的答案，还有一些变体。

首先，前两个给出了一个反直觉的排序。为了得到漂亮的树遍历顺序，只需反转连接（将“源”放在第一位）。

其次，如果你正在使用像EF这样昂贵的源，并且想要限制整个分支，那么Damien的建议是插入谓词，这是一个好方法，仍然可以用Linq实现。

最后，对于一个昂贵的源，也许预先选择每个节点感兴趣的字段会更好。

将所有这些组合起来：

public static IEnumerable<R> Flatten<T,R>(this T source, Func<T, IEnumerable<T>> children
    , Func<T, R> selector
    , Func<T, bool> branchpredicate = null
) {
    if (children == null) throw new ArgumentNullException("children");
    if (selector == null) throw new ArgumentNullException("selector");
    var pred = branchpredicate ?? (src => true);
    if (children(source) == null) return new[] { selector(source) };

    return new[] { selector(source) }
        .Concat(children(source)
        .Where(pred)
        .SelectMany(c => Flatten(c, children, selector, pred)));
}
0

嗯，我想最好的方法是采用使用分层结构的技术：

  1. 你需要一个锚点来实现

  2. 你需要递归部分

    // 锚点

rootFamily.Children.ForEach(childFamily => 
{
    if (childFamily.Name.Contains(search))
    {
       // 在此处添加你的逻辑
       return;
    }
    SearchForChildren(childFamily);
});

// 递归

public void SearchForChildren(Family childFamily)
{
    childFamily.Children.ForEach(_childFamily => 
    {
        if (_childFamily.Name.Contains(search))
        {
           // 在此处添加你的逻辑
           return;
        }
        SearchForChildren(_childFamily);
    });
}
0

我已经尝试了两个建议的代码，并使代码更加清晰：

    public static IEnumerable<T> Flatten1<T>(this T source, Func<T, IEnumerable<T>> selector)
    {
        return selector(source).SelectMany(c => Flatten1(c, selector)).Concat(new[] { source });
    }

    public static IEnumerable<T> Flatten2<T>(this T source, Func<T, IEnumerable<T>> selector)
    {            
        var stack = new Stack<T>();
        stack.Push(source);
        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current;
            foreach (var child in selector(current))
                stack.Push(child);
        }
    }

Flatten2() 看起来稍微快一点，但差距不大。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接