这是一个完成这项工作的扩展方法:
// Depth-first traversal, recursive
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> source,
Func<T, IEnumerable<T>> childrenSelector)
{
foreach (var item in source)
{
yield return item;
foreach (var child in childrenSelector(item).Flatten(childrenSelector))
{
yield return child;
}
}
}
你可以像这样使用它:
foreach(var category in categories.Flatten(c => c.Children))
{
...
}
上面的解决方案是深度优先遍历,如果你想要广度优先遍历,你可以这样做:
// Breadth-first traversal, non-recursive
public static IEnumerable<T> Flatten2<T>(
this IEnumerable<T> source,
Func<T, IEnumerable<T>> childrenSelector)
{
var queue = new Queue<T>(source);
while (queue.Count > 0)
{
var item = queue.Dequeue();
yield return item;
foreach (var child in childrenSelector(item))
{
queue.Enqueue(child);
}
}
}
它还具有非递归的好处...
更新:实际上,我只是想到了一种使深度优先遍历非递归的方法......这里是:
// Depth-first traversal, non-recursive
public static IEnumerable<T> Flatten3<T>(
this IEnumerable<T> source,
Func<T, IEnumerable<T>> childrenSelector)
{
LinkedList<T> list = new LinkedList<T>(source);
while (list.Count > 0)
{
var item = list.First.Value;
yield return item;
list.RemoveFirst();
var node = list.First;
foreach (var child in childrenSelector(item))
{
if (node != null)
list.AddBefore(node, child);
else
list.AddLast(child);
}
}
}
我使用 a 是LinkedList<T>
因为插入是 O(1) 操作,而对 a 的插入List<T>
是 O(n)。