如何通过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}); } 

然后，您可以使用Where(...)按group进行过滤。

要获得一些“风格点”，将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(...)的两侧Concat(...) 。

Answer 2

被接受的答案的问题是，如果树很深，那么效率是低的。 如果这棵树很深，那么它会吹到堆栈上。 您可以通过使用显式堆栈来解决问题：

 public static IEnumerable<MyNode> Traverse(this MyNode root) { var stack = new Stack<MyNode>(); stack.Push(root); while(stack.Count > 0) { var current = stack.Pop(); yield return current; foreach(var child in current.Elements) stack.Push(child); } } 

假设高度为h的树中有n个节点，并且分支因子大大小于n，则此方法在堆栈空间中为O（1），堆空间中为O（h），时间为O（n）。 另一种algorithm是堆栈中的O（h），堆中的O（1）和时间上的O（nh）。 如果分支因子与n相比较小，则h在O（lg n）和O（n）之间，这说明如果h接近于n，朴素algorithm可以使用危险量的堆栈和大量的时间。

现在我们有了遍历，你的查询很简单：

 root.Traverse().Where(item=>item.group == 1); 

Answer 3

为了完整起见，这里是dasblinkenlight和Eric Lippert的答案的组合。 unit testing和一切。 🙂

  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); } } 

Answer 4

令人惊讶的是没有人（甚至埃里克）展示了recursion预订DFT的“自然”迭代端口，所以这里是：

  public static IEnumerable<T> Expand<T>( this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) { var stack = new Stack<IEnumerator<T>>(); var e = source.GetEnumerator(); try { while (true) { while (e.MoveNext()) { var item = e.Current; yield return item; var elements = elementSelector(item); if (elements == null) continue; stack.Push(e); e = elements.GetEnumerator(); } if (stack.Count == 0) break; e.Dispose(); e = stack.Pop(); } } finally { e.Dispose(); while (stack.Count != 0) stack.Pop().Dispose(); } } 

Answer 5

如果有其他人发现这一点，但也需要知道他们已经把树夷为平地的水平，这扩大了Konamiman的dasblinkenlight和Eric Lippert的解决scheme的组合：

  public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>( this IEnumerable<T> items, Func<T, IEnumerable<T>> getChilds) { var stack = new Stack<Tuple<T, int>>(); foreach (var item in items) stack.Push(new Tuple<T, int>(item, 1)); while (stack.Count > 0) { var current = stack.Pop(); yield return current; foreach (var child in getChilds(current.Item1)) stack.Push(new Tuple<T, int>(child, current.Item2 + 1)); } } 

Answer 6

解决这个问题最简单/最清晰的方法是使用recursionLINQ查询。 这个问题： 在LINQ中expressionrecursion有很多关于这个的讨论，这个特定的回答https://stackoverflow.com/a/793531/1550详细说明了如何实现它。;

Answer 7

 void Main() { var allNodes = GetTreeNodes().Flatten(x => x.Elements); allNodes.Dump(); } public static class ExtensionMethods { public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector = null) { if (source == null) { return new List<T>(); } var list = source; if (childrenSelector != null) { foreach (var item in source) { list = list.Concat(childrenSelector(item).Flatten(childrenSelector)); } } return list; } } IEnumerable<MyNode> GetTreeNodes() { return new[] { new MyNode { Elements = new[] { new MyNode() }}, new MyNode { Elements = new[] { new MyNode(), new MyNode(), new MyNode() }} }; } class MyNode { public MyNode Parent; public IEnumerable<MyNode> Elements; int group = 1; } 

Answer 8

结合Dave和Ivan Stoev的回答，如果你需要嵌套的层次和清单“按顺序”扁平化，而不是像Konamiman给出的答案一样逆转。

  public static class HierarchicalEnumerableUtils { private static IEnumerable<Tuple<T, int>> ToLeveled<T>(this IEnumerable<T> source, int level) { if (source == null) { return null; } else { return source.Select(item => new Tuple<T, int>(item, level)); } } public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) { var stack = new Stack<IEnumerator<Tuple<T, int>>>(); var leveledSource = source.ToLeveled(0); var e = leveledSource.GetEnumerator(); try { while (true) { while (e.MoveNext()) { var item = e.Current; yield return item; var elements = elementSelector(item.Item1).ToLeveled(item.Item2 + 1); if (elements == null) continue; stack.Push(e); e = elements.GetEnumerator(); } if (stack.Count == 0) break; e.Dispose(); e = stack.Pop(); } } finally { e.Dispose(); while (stack.Count != 0) stack.Pop().Dispose(); } } } 

Answer 9

基于Konamiman的回答，以及sorting是意想不到的评论，下面是一个带有显式sorting参数的版本：

 public static IEnumerable<T> TraverseAndFlatten<T, V>(this IEnumerable<T> items, Func<T, IEnumerable<T>> nested, Func<T, V> orderBy) { var stack = new Stack<T>(); foreach (var item in items.OrderBy(orderBy)) stack.Push(item); while (stack.Count > 0) { var current = stack.Pop(); yield return current; var children = nested(current).OrderBy(orderBy); if (children == null) continue; foreach (var child in children) stack.Push(child); } } 

还有一个示例用法：

 var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();