用一个语句压平一棵树（列表的列表）？

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 因为插入是O(1) 次操作，而插入 List 则为 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;
}

Answer 3

鉴于 @EZHart 提到的类，您还可以使用辅助方法来扩展它，我认为在这种情况下更简单。

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

Answer 4

如果广度优先遍历没问题，并且您只想使用一些短的非递归内联代码（实际上是 3 行），请创建一个使用根元素初始化的列表，然后仅通过一个简单的 for 循环来扩展它：

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