使用LINQ实现对象层次结构的深度优先扁平化集合。

Question

我有一个对象层次结构（MasterNode -> ChildNodes），其中主节点和子节点是相同类型的，只有两个级别（顶级和子级）像这样（'A' 是 D、E 和 F 的父级，'B' 是 G 的父级等）

A--+
|  D
|  E
|  F
|
B--+
|  G
|
C--+
   H
   I

假设我有一个大对象（A，B，C）的IEnumerable作为MasterNodes，并给定一个父对象X，我可以通过X.children获取其子级的IEnumerable。

我知道可以使用SelectMany方法或使用以下方法枚举所有叶节点（子节点）。

from parent in Masternodes
from child in parent.children
select child

这将给我这个序列：

[D,E,F,G,H,I]

但这不是我要求的。

如何使用LINQ查询获取MasterNodes集合中对象的深度优先序列？（首先返回父级，然后是其所有子级，接着返回下一个父级及其所有子级等等）

预期结果应该像这样的序列：

[A,D,E,F,B,G,C,H,I]

更新:

我需要纯粹的.NET LINQ。我知道可以定义自己的方法来实现，但我想要的是只基于框架提供的方法来实现。

- Thanasis Ioannidis

---

LINQ可以帮助编写易于理解的代码，但它不包含一个EnumerateDepthFirstTwoLevelDeep方法。您需要组合几个LINQ方法才能获得所需的结果。如果存在这样的方法，那么找到它需要的时间比一次性编写几行代码更长，因为LINQ设计人员需要提供许多数百甚至数千个额外的方法来匹配您的特定情况，而且还有许多不同的情况。 - Alois Kraus

这就是我所询问的内容。这两行针对这种特定情况:) Heinzi的答案正是我想要的。 - Thanasis Ioannidis

Answer 1

如果您有以下类：

public class Node
{
    public string Name;
    public List<Node> Children = new List<Node>();
}

你的LINQ会是这样的：

 Func<IEnumerable<Node>, IEnumerable<Node>> Flatten = null;
 Flatten = coll => coll.SelectMany(n=>n.Concat(Flatten(n.Children)));

测试代码：

Node[] roots = new Node[]{ new Node(){Name="A"},new Node(){Name="B"},new Node(){Name="C"} };
roots[0].Children.Add(new Node(){Name="D"});
roots[0].Children.Add(new Node(){Name="E"});
roots[0].Children.Add(new Node(){Name="F"});

roots[1].Children.Add(new Node(){Name="G"});

roots[2].Children.Add(new Node(){Name="H"});
roots[2].Children.Add(new Node(){Name="I"});

Func<IEnumerable<Node>, IEnumerable<Node>> Flatten = null;
Flatten = coll => coll.SelectMany(n=>n.Concat(Flatten(n.Children)));

var result = String.Join(",",Flatten(roots).Select(x=>x.Name));

Console.WriteLine(result);

- L.B

---

@DanielHilgarth 我知道递归 lambda 不太易读，但最终只有两行代码。 - L.B

你也可以使用第三方图形库，比如 http://nuget.org/packages/QuickGraph，其中包含深度优先递归算法。 - akton

@L.B：个人而言，我会将其制作成常规递归方法，因为这样更易读。 - Daniel Hilgarth

Answer 2

如果你需要超过两个层级，你可以使用以下的扩展方法，该方法会递归遍历你的对象图：

public static IEnumerable<T> Flat<T>(this IEnumerable<T> l, Func<T, IEnumerable<T>> f) =>
        l.SelectMany(i => new T[] { i }.Concat(f(i).Flat(f)));

它使用将T映射到描述数据父 -> 子关系的IEnumerable<T>的函数，对给定的IEnumerable<T>进行扁平化处理。

深度优先扁平化是通过将每个元素与其子树连接起来，然后使用SelectMany将它们连接在一起完成的。

您可以像这样使用它：

var flattened = Masternodes.Flat(c => c.children);

- Raziel

---

我喜欢这个答案，因为它更通用。 - Thanasis Ioannidis

如果您认为这个答案更好，请考虑将接受的答案更改为此答案。谢谢！ - Raziel

Answer 3

由于您只有两个级别，因此以下方法应该有效：

var result = (from parent in masternodes
              select new Node[] { parent }.Concat(parent.children)).SelectMany(i => i);

首先，它创建了包括父级及其子级的可枚举对象：

[A, D, E, F]
[B, G]
[C, H]

然后使用 SelectMany 将它们展平。

- Heinzi

---

谢谢，这实际上是我在发布问题后不久想到的。是否有一种LINQ方法可以将一个对象x转换为包含此对象的IEnumerable？还是我必须使用新的Node[] { ... }方式？ - Thanasis Ioannidis

虽然这不是唯一回答问题的答案，但我选择它是因为它简短、快速、干净并且直接切入要点。 - Thanasis Ioannidis

@Saysmaster: 没有什么真正优雅的方法来创建一个单项IEnumerable。另一个选择是Enumerable.Repat(item, 1)（参见此问题）或为此目的创建扩展方法（请参见此问题）。 - Heinzi

Answer 4

假设我们有以下的类：

public class MasterNode : ChildNode
{
    public List<ChildNode> ChildNodes;
}

public class ChildNode
{
    public string Value;
}

那么

        List<MasterNode> list = new List<MasterNode>
        {
            new MasterNode
            {
                Value="A", 
                ChildNodes = new List<ChildNode>
                {
                    new ChildNode{Value = "D"},
                    new ChildNode{Value = "E"},
                    new ChildNode{Value = "F"}
                }
            },
            new MasterNode
            {
                Value="B", 
                ChildNodes = new List<ChildNode>
                {                        
                    new ChildNode{Value = "G"}
                }
            },
            new MasterNode
            {
                Value="C", 
                ChildNodes = new List<ChildNode>
                {
                    new ChildNode{Value = "H"},
                    new ChildNode{Value = "I"}
                }
            }
        };

        foreach (ChildNode c in list.SelectMany(l =>
                                {
                                   List<ChildNode> result = l.ChildNodes.ToList();
                                   result.Insert(0, l);
                                   return result;
                                }))
        {
            Console.WriteLine(c.Value);
        }

- horgh