myW*_*SON 86 .net c# linq tree .net-4.0
所以我有简单的树:
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
}
我有一个IEnumerable<MyNode>.我想得到一个列表MyNode(包括内部节点对象(Elements))作为一个平面列表Where group == 1.如何通过LINQ做这样的事情？
das*_*ght 130
你可以像这样展平一棵树:
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(...).
Eri*_*ert 119
接受的答案的问题是,如果树很深,效率很低.如果树是非常深的,然后它吹堆栈.您可以使用显式堆栈来解决问题:
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);
Kon*_*man 25
为了完整起见,这里是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);
}
}
Iva*_*oev 20
更新:
对于对嵌套水平感兴趣的人(深度).显式枚举器堆栈实现的一个好处是,在任何时刻(特别是当产生元素时)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();
}
}
这里提出的大多数答案都会产生深度优先或之字形序列。例如从下面的树开始：
1 2
/ \ / \
/ \ / \
/ \ / \
/ \ / \
11 12 21 22
/ \ / \ / \ / \
/ \ / \ / \ / \
111 112 121 122 211 212 221 222
谢尔盖·卡里尼琴科（Sergey Kalinichenko）的回答产生了这个扁平序列：
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
伊万·斯托耶夫的回答产生了这个扁平的序列：
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。
我发现这里给出的答案有一些小问题：
基于先前的答案，并提出以下内容：
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; }
}
}
| 归档时间： |
|
| 查看次数： |
39954 次 |
| 最近记录： |