用一个语句展平树(列表列表)？

Question

感谢nHibernate,我使用的一些数据结构是列表中列表中的列表.例如,我有一个名为"category"的数据对象,它有一个.Children属性,可以解析为一个类别列表......每个类别都可以有子节点......依此类推.

我需要找到一种方法,从这个结构中的顶级类别开始,并获得一个列表或数组或类似于整个结构中所有孩子的东西 - 所有孩子的所有孩子等等,扁平化为一个名单.

我确信它可以通过递归来完成,但我发现递归代码很难实现,而且我确信在.Net 4中必须有一个更简单的方法使用Linq或者某些 - 任何建议？

Answer 1

这是一个完成工作的扩展方法:

// 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);
        }
    }
}

我使用的是LinkedList<T>因为插入是O(1)操作,而插入是a List<T>是O(n).

Answer 2

假设您的Category类看起来像:

 public class Category
 {
   public string Name { get; set; }
   public List<Category> Children { get; set; }
 }

我不认为这是一种"简单"的非递归方式; 如果您只是寻找单个方法调用来处理它,那么"简单"的方法是将递归版本写入单个方法调用.可能有一种迭代的方法来做到这一点,但我猜它实际上非常复杂.这就像要求"简单"的方法在不使用微积分的情况下找到曲线的切线.

无论如何,这可能会这样做:

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;
}