所以我有简单的树：
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
}
我有一个IEnumerable<MyNode>. 我想将所有MyNode（包括内部节点对象（Elements））的列表作为一个平面列表Where group == 1。如何通过 LINQ 做这样的事情？
问问题
53872 次
14 回答
160
你可以像这样展平一棵树：
IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) =>
e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });
然后，您可以group使用过滤Where(...)。
要获得一些“风格积分”，请转换Flatten为静态类中的扩展函数。
public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) =>
e.SelectMany(c => c.Elements.Flatten()).Concat(e);
要为“更好的风格”赢得更多积分，请转换Flatten为采用树和从节点产生后代的函数的通用扩展方法：
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> e
, Func<T,IEnumerable<T>> f
) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);
像这样调用这个函数：
IEnumerable<MyNode> tree = ....
var res = tree.Flatten(node => node.Elements);
如果您希望在预购中而不是在后购中进行展平，请在Concat(...).
于 2012-08-06T14:28:22.943 回答
134
公认答案的问题是，如果树很深，效率会很低。如果树很深，那么它会炸毁堆栈。您可以通过使用显式堆栈来解决问题：
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)。给出的另一种算法是堆栈中的 O(h)、堆中的 O(1) 和时间中的 O(nh)。如果分支因子与 n 相比较小，则 h 介于 O(lg n) 和 O(n) 之间，这说明如果 h 接近 n，朴素算法可以使用危险的堆栈数量和大量时间。
现在我们有了遍历，您的查询很简单：
root.Traverse().Where(item=>item.group == 1);
于 2013-12-02T18:36:40.200 回答
29
为了完整起见，这里是 dasblinkenlight 和 Eric Lippert 的答案的组合。单元测试和一切。:-)
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);
}
}
于 2015-01-07T09:14:16.950 回答
24
更新：
对于对嵌套级别（深度）感兴趣的人。显式枚举器堆栈实现的好处之一是，在任何时候（特别是在产生元素时），它都stack.Count表示当前的处理深度。因此，考虑到这一点并利用 C#7.0 值元组，我们可以简单地更改方法声明，如下所示：
public static IEnumerable<(T Item, int Level)> ExpandWithLevel<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
和yield声明：
yield return (item, stack.Count);
然后我们可以通过在上面应用simple来实现原始方法Select：
public static IEnumerable<T> Expand<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) =>
source.ExpandWithLevel(elementSelector).Select(e => e.Item);
原来的：
令人惊讶的是，没有人（甚至 Eric）展示了递归预阶 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();
}
}
于 2015-08-07T15:18:51.097 回答
8
我发现这里给出的答案有一些小问题：
- 如果项目的初始列表为空怎么办？
- 如果子列表中有空值怎么办？
基于先前的答案并提出以下内容：
public static class IEnumerableExtensions
{
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> items,
Func<T, IEnumerable<T>> getChildren)
{
if (items == null)
yield break;
var stack = new Stack<T>(items);
while (stack.Count > 0)
{
var current = stack.Pop();
yield return current;
if (current == null) continue;
var children = getChildren(current);
if (children == null) continue;
foreach (var child in children)
stack.Push(child);
}
}
}
和单元测试：
[TestClass]
public class IEnumerableExtensionsTests
{
[TestMethod]
public void NullList()
{
IEnumerable<Test> items = null;
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(0, flattened.Count());
}
[TestMethod]
public void EmptyList()
{
var items = new Test[0];
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(0, flattened.Count());
}
[TestMethod]
public void OneItem()
{
var items = new[] { new Test() };
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(1, flattened.Count());
}
[TestMethod]
public void OneItemWithChild()
{
var items = new[] { new Test { Id = 1, Children = new[] { new Test { Id = 2 } } } };
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(2, flattened.Count());
Assert.IsTrue(flattened.Any(i => i.Id == 1));
Assert.IsTrue(flattened.Any(i => i.Id == 2));
}
[TestMethod]
public void OneItemWithNullChild()
{
var items = new[] { new Test { Id = 1, Children = new Test[] { null } } };
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(2, flattened.Count());
Assert.IsTrue(flattened.Any(i => i.Id == 1));
Assert.IsTrue(flattened.Any(i => i == null));
}
class Test
{
public int Id { get; set; }
public IEnumerable<Test> Children { get; set; }
}
}
于 2018-06-29T17:19:25.897 回答
4
万一其他人发现了这一点，但也需要在他们将树展平后知道级别，这将扩展 Konamiman 的 dasblinkenlight 和 Eric Lippert 的解决方案的组合：
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));
}
}
于 2015-07-08T21:01:28.473 回答
4
这里提供的大多数答案都是产生深度优先或之字形序列。例如从下面的树开始：
1 2
/ \ / \
/ \ / \
/ \ / \
/ \ / \
11 12 21 22
/ \ / \ / \ / \
/ \ / \ / \ / \
111 112 121 122 211 212 221 222
dasblinkenlight 的回答产生了这个扁平的序列：
111, 112, 121, 122, 11, 12, 211, 212, 221, 222, 21, 22, 1, 2
Konamiman 的回答（概括 Eric Lippert 的回答）产生了这个扁平序列：
2, 22, 222, 221, 21, 212, 211, 1, 12, 122, 121, 11, 112, 111
Ivan Stoev 的回答产生了这个扁平的序列：
1, 11, 111, 112, 12, 121, 122, 2, 21, 211, 212, 22, 221, 222
如果您对这样的广度优先序列感兴趣：
1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222
...那么这就是您的解决方案：
public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source,
Func<T, IEnumerable<T>> childrenSelector)
{
var queue = new Queue<T>(source);
while (queue.Count > 0)
{
var current = queue.Dequeue();
yield return current;
var children = childrenSelector(current);
if (children == null) continue;
foreach (var child in children) queue.Enqueue(child);
}
}
实现上的区别基本上是使用 aQueue而不是 a Stack。没有进行实际的排序。
注意：这种实现在内存效率方面远非最佳，因为在枚举期间，元素总数的很大一部分最终将存储在内部队列中。Stack基于 - 的树遍历在内存使用方面比Queue基于 - 的实现更有效。
于 2020-09-19T09:13:01.230 回答
2
另一个真正的选择是进行适当的 OO 设计。
例如要求MyNode返回所有展平。
像这样：
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
public IEnumerable<MyNode> GetAllNodes()
{
if (Elements == null)
{
return Enumerable.Empty<MyNode>();
}
return Elements.SelectMany(e => e.GetAllNodes());
}
}
现在您可以要求顶级 MyNode 获取所有节点。
var flatten = topNode.GetAllNodes();
如果您无法编辑课程，那么这不是一个选项。但除此之外，我认为这可能是单独（递归）LINQ 方法的首选。
这是使用 LINQ，所以我认为这个答案在这里适用；）
于 2019-06-23T20:28:49.760 回答
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();
}
}
}
于 2016-11-11T17:07:19.050 回答
1
这里有一些使用 Queue 的现成实现，首先返回 Flatten 树，然后返回我的孩子。
public static IEnumerable<T> Flatten<T>(this IEnumerable<T> items,
Func<T,IEnumerable<T>> getChildren)
{
if (items == null)
yield break;
var queue = new Queue<T>();
foreach (var item in items) {
if (item == null)
continue;
queue.Enqueue(item);
while (queue.Count > 0) {
var current = queue.Dequeue();
yield return current;
if (current == null)
continue;
var children = getChildren(current);
if (children == null)
continue;
foreach (var child in children)
queue.Enqueue(child);
}
}
}
于 2020-02-12T09:14:40.637 回答
0
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;
}
于 2012-08-06T14:38:11.590 回答
0
基于 Konamiman 的回答，以及排序出乎意料的评论，这是一个带有明确排序参数的版本：
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();
于 2017-03-23T22:19:45.077 回答
0
下面是 Ivan Stoev 的代码，它具有告诉路径中每个对象的索引的附加功能。例如搜索“Item_120”：
Item_0--Item_00
Item_01
Item_1--Item_10
Item_11
Item_12--Item_120
将返回项目和一个 int 数组 [1,2,0]。显然，嵌套级别也是可用的，作为数组的长度。
public static IEnumerable<(T, int[])> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> getChildren) {
var stack = new Stack<IEnumerator<T>>();
var e = source.GetEnumerator();
List<int> indexes = new List<int>() { -1 };
try {
while (true) {
while (e.MoveNext()) {
var item = e.Current;
indexes[stack.Count]++;
yield return (item, indexes.Take(stack.Count + 1).ToArray());
var elements = getChildren(item);
if (elements == null) continue;
stack.Push(e);
e = elements.GetEnumerator();
if (indexes.Count == stack.Count)
indexes.Add(-1);
}
if (stack.Count == 0) break;
e.Dispose();
indexes[stack.Count] = -1;
e = stack.Pop();
}
} finally {
e.Dispose();
while (stack.Count != 0) stack.Pop().Dispose();
}
}
于 2018-01-15T00:29:02.573 回答
0
每隔一段时间，我就会尝试解决这个问题并设计自己的解决方案，该解决方案支持任意深度的结构（无递归），执行广度优先遍历，并且不会滥用太多 LINQ 查询或抢先对子级执行递归。在挖掘.NET 源代码并尝试了许多解决方案之后，我终于想出了这个解决方案。它最终非常接近 Ian Stoev 的答案（我刚才才看到他的答案），但是我的没有使用无限循环或有不寻常的代码流。
public static IEnumerable<T> Traverse<T>(
this IEnumerable<T> source,
Func<T, IEnumerable<T>> fnRecurse)
{
if (source != null)
{
Stack<IEnumerator<T>> enumerators = new Stack<IEnumerator<T>>();
try
{
enumerators.Push(source.GetEnumerator());
while (enumerators.Count > 0)
{
var top = enumerators.Peek();
while (top.MoveNext())
{
yield return top.Current;
var children = fnRecurse(top.Current);
if (children != null)
{
top = children.GetEnumerator();
enumerators.Push(top);
}
}
enumerators.Pop().Dispose();
}
}
finally
{
while (enumerators.Count > 0)
enumerators.Pop().Dispose();
}
}
}
可以在此处找到一个工作示例。
于 2020-07-25T20:59:39.117 回答