所以我有简单的树：
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});
}
然后你可以使用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(...)的两侧。
基于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();
下面是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();
}
}
接受的答案的问题是，如果树很深，效率很低。如果树很深，那么它会吹掉堆栈。您可以使用显式堆栈来解决问题：
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);
为了完整起见，这里是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);
}
}
更新：
对于对嵌套水平感兴趣的人（深度）。显式枚举器堆栈实现的一个好处是，在任何时刻（特别是在产生元素时）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);
然后我们可以通过在上面应用简单的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();
}
}
如果其他人发现了这个，但是在他们弄平了树之后也需要知道它的水平，这扩展了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));
}
}
我在这里给出了答案，我发现了一些小问题：
基于之前的答案，并提出以下建议：
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; }
}
}
另一个选择是采用适当的OO设计。
例如要求MyNode返回所有flatten。
像这样：
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
public IEnumerable<MyNode> GetAllNodes()
{
if (Elements == null)
{
return new List<MyNode>();
}
return Elements.SelectMany(e => e.GetAllNodes());
}
}
现在您可以要求顶级MyNode获取所有节点。
var flatten = topNode.GetAllNodes();
如果您无法编辑该类，则此选项不可用。但除此之外，我认为这可能是一个单独的（递归）LINQ方法的首选。
这是使用LINQ，所以我认为这个答案在这里适用;）
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();
}
}
}