如何通过LINQ压扁树?

所以我有简单的树:

class MyNode { public MyNode Parent; public IEnumerable<MyNode> Elements; int group = 1; } 

我有一个IEnumerable<MyNode> 。 我想获得所有MyNode (包括内部节点对象( Elements ))的列表作为一个扁平列表Where group == 1 。 如何通过LINQ做这样的事情?

你可以像这样弄平一棵树:

 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(...)

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

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

为了完整起见,这里是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); } } 

令人惊讶的是没有人(甚至埃里克)展示了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(); } } 

如果有其他人发现这一点,但也需要知道他们已经把树夷为平地的水平,这扩大了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)); } } 

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

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

结合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(); } } } 

基于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();