Flatten a tree (list of lists) with one statement?
Thanks to nHibernate, some of the data structures I work with are lists within lists within lists. So for example I have a data object called "category" which has a .Children property that resolves to a list of categories ... each one of which can have children ... and so on and so on.
I need to find a way of starting at a top-level category in this structure and getting a list or array or something similar of all the children in the entire structure - so all the children of all the children etc etc, flattened into a single list.
I'm sure it can be done with recursion, but I find开发者_运维百科 recursive code a pain to work through, and I'm convinced there must be a more straightforward way in .Net 4 using Linq or somesuch - any suggestions?
Here's an extension method that does the job:
// 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;
}
}
}
You can use it like this:
foreach(var category in categories.Flatten(c => c.Children))
{
...
}
The solution above does a depth-first traversal, if you want a breadth-first traversal you can do something like this:
// 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);
}
}
}
It also has the benefit of being non-recursive...
UPDATE: Actually, I just thought of a way to make the depth-first traversal non-recursive... here it is:
// 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);
}
}
}
I'm using a LinkedList<T>
because insertions are O(1) operations, whereas insertions to a List<T>
are O(n).
Assuming your Category class looks something like:
public class Category
{
public string Name { get; set; }
public List<Category> Children { get; set; }
}
I don't think there's an "easy" non-recursive way to do it; if you're simply looking for a single method call to handle it, the "easy" way is to write the recursive version into a single method call. There's probably an iterative way to do this, but I'm guessing it's actually pretty complicated. It's like asking the "easy" way to find a tangent to a curve without using calculus.
Anyway, this would probably do it:
public static List<Category> Flatten(Category root) {
var flattened = new List<Category> {root};
var children = root.Children;
if(children != null)
{
foreach (var child in children)
{
flattened.AddRange(Flatten(child));
}
}
return flattened;
}
Given the class @E.Z.Hart mentions, you could also extend it with a helper method for this which I think is simpler in this case.
public class Category
{
public string Name { get; set; }
public List<Category> Children { get; set; }
public IEnumerable<Category> AllChildren()
{
yield return this;
foreach (var child in Children)
foreach (var granChild in child.AllChildren())
{
yield return granChild;
}
}
}
If breadth-first traversal is OK and you only want to use some short non-recursive inline code (3 lines actually), create a list initialized with your root element(s) and then extend it by just one simple for-loop:
// your data object class looks like:
public class DataObject
{
public List<DataObject> Children { get; set; }
...
}
...
// given are some root elements
IEnumerable<DataObject> rootElements = ...
// initialize the flattened list with the root elements
var result = new List<DataObject>(rootElements);
// extend the flattened list by one simple for-loop,
// please note that result.Count may increase after every iteration!
for (int index = 0; index < result.Count; index++)
result.AddRange(result[index].Children);
精彩评论