如何用一行代码将树（列表的列表）展平？

Question

由于nHibernate的支持，我处理的一些数据结构是嵌套列表。例如，我有一个名为“category”的数据对象，它具有.Children属性，该属性解析为一个类别列表...每个类别都可以具有子类别...以此类推。

我需要找到一种方法，从这个结构中的顶级类别开始，获取所有子代的列表、数组或类似的东西，并将其展开为单个列表，包括所有子代及其子代等等。

我相信可以通过递归来完成，但我发现递归代码很难理解和编写，我确信在.Net 4中使用Linq或类似的东西有更简单的方法 - 有什么建议吗？

- Bob Tway

---

树的展开似乎本质上是递归的。我不相信有一种单语句的方法可以展开一棵树，即使使用LINQ也不行。您是否接受递归答案？ - Mike Park

当然。这似乎是那种应该有一个“简单”答案的事情之一。Linq的“selectMany”可以展平树的两个级别，但问题在于当我开始时无法知道我的对象有多少级别。所以我想递归是唯一的方法。 - Bob Tway

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) 的，而插入到 List<T> 中则是 O(n)。

- Thomas Levesque

---

对于基于队列的解决方案，我会给你加上+1分的聪明才智。我不知道是否应该称其为“容易”，但这可能是一个观点问题。深度优先和广度优先的问题很重要；我倾向于假设深度优先，这是一个不好的习惯。无论如何，你的答案更好。 - E.Z. Hart

关于深度优先搜索：添加“if (source == null) yield break;”将适用于大多数情况。 - Bastiaan Linders

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

- E.Z. Hart

---

有一个简单的非递归解决方案，但它执行广度优先遍历（请参见我的答案）。这可能不是一个大问题，但这取决于OP确切想要什么... - Thomas Levesque

Answer 3

如果广度优先遍历是可以接受的，并且您只想使用一些短的非递归内联代码（实际上只有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);

- Paul

---

如果你的树超过了1层深度怎么办？这样是行不通的。 - rollsch

@rolls 当循环时，列表会自我扩展。这样它就可以遍历所有层级上的所有元素。 - Tim Pohlmann

那很聪明，我没想到。我相信如果你使用链表，AddRange 的性能也会更好。 - rollsch

@rolls 感谢您的提示。我添加了一条注释以显示这里有一个小技巧。不幸的是，LinkedList没有AddRange方法，所以我使用了List类来保持简单。 - Paul

Answer 4

鉴于 @E.Z.Hart 提到的类，您还可以通过添加一个辅助方法来扩展它，在这种情况下我认为这更简单。

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

- Ogglas