15

我需要在树中搜索可能位于树中任何位置的数据。如何用 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; }
    }
}
4

8 回答 8

10

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);
}
于 2013-08-10T20:02:40.483 回答
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);
    }
}
于 2013-08-10T19:50:06.457 回答
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});
}
于 2013-08-10T19:13:11.370 回答
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(...)

于 2013-08-10T19:42:32.090 回答
1

我喜欢 Kenneth Bo Christensen 使用堆栈的答案,它效果很好,易于阅读且速度快(并且不使用递归)。唯一不愉快的是它颠倒了子项的顺序(因为堆栈是先进先出的)。如果排序顺序对您不重要,那么没关系。如果是这样,则可以使用 selector(current) 轻松实现排序。foreach 循环中的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);
    }
}
于 2015-02-06T10:47:56.900 回答
0

好吧,我想方法是使用使用分层结构的技术:

  1. 你需要一个锚来制作
  2. 你需要递归部分

    // Anchor
    
    rootFamily.Children.ForEach(childFamily => 
    {
        if (childFamily.Name.Contains(search))
        {
           // Your logic here
           return;
        }
        SearchForChildren(childFamily);
    });
    
    // Recursion
    
    public void SearchForChildren(Family childFamily)
    {
        childFamily.Children.ForEach(_childFamily => 
        {
            if (_childFamily.Name.Contains(search))
            {
               // Your logic here
               return;
            }
            SearchForChildren(_childFamily);
        });
    }
    
于 2013-08-10T19:17:12.927 回答
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() 似乎快一点,但它的运行很接近。

于 2014-11-04T17:05:39.503 回答
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)));
}
于 2016-10-20T05:53:31.690 回答