如何通过LINQ将树夷为平地？

Question

如何通过LINQ将树夷为平地？所以我有一棵简单的树：class MyNode{  public MyNode Parent;  public IEnumerable<MyNode> Elements;  int group = 1;}我有一个IEnumerable<MyNode>..我想要一份清单MyNode(包括内部节点对象(Elements)作为一个单一清单Where group == 1..如何通过LINQ做这样的事情？

Answer 1

你可以像这样把一棵树夷为平地：

IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) {
    return e.SelectMany(c => Flatten(c.Elements)).Concat(new[] {e});}

然后你可以过滤group使用Where(...).

若要获得“风格积分”，请转换Flatten到静态类中的扩展函数。

public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) {
    return e.SelectMany(c => c.Elements.Flatten()).Concat(e);}

为了获得“更好的风格”的一些分数，转换Flatten获取树和生成后代的函数的泛型扩展方法：

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> e,
    Func<T,IEnumerable<T>> f) {
    return e.SelectMany(c => f(c).Flatten(f)).Concat(e);}

这样调用此函数：

IEnumerable<MyNode> tree = ....var res = tree.Flatten(node => node.Elements);

如果您希望按预先顺序而不是按顺序排列，请在Concat(...).

Answer 2

为了完整起见，下面是dasbrakenlight和EricLippert的答案的组合。单元测试和一切。*-)

 public static IEnumerable<T> Flatten<T>(
        this IEnumerable<T> items,
        Func<T, IEnumerable<T>> getChildren)
 {
     var stack = new Stack<T>();
     foreach(var item in items)
         stack.Push(item);

     while(stack.Count > 0)
     {
         var current = stack.Pop();
         yield return current;

         var children = getChildren(current);
         if (children == null) continue;

         foreach (var child in children) 
            stack.Push(child);
     }
 }