如何通过LINQ来展开树形结构？

Question

我有一棵简单的树：

class MyNode
{
 public MyNode Parent;
 public IEnumerable<MyNode> Elements;
 int group = 1;
}

我有一个 IEnumerable<MyNode>，我想要获取所有 MyNode 的列表（包括内部节点对象 (Elements)），作为一个平面列表Wheregroup == 1。如何使用 LINQ 实现这样的事情？

- myWallJSON

---

您希望展开的列表按什么顺序排列？ - Philip

节点何时停止拥有子节点？我猜想是当“Elements”为空或为null时？ - Adam Houldsworth

可能与http://stackoverflow.com/questions/11827569/recursive-filtering-linq-to-objects重复，请将递归过滤的LINQ到对象的内容翻译成中文。 - Tamir

最简单/最清晰的解决方法是使用递归LINQ查询。这个问题：https://dev59.com/MXRB5IYBdhLWcg3wEDyl 有很多关于这个问题的讨论，而这个特定的答案：https://dev59.com/MXRB5IYBdhLWcg3wEDyl#793531则详细说明了如何实现它。 - Alvaro Rodriguez

Answer 1

您可以像这样压平一棵树：

IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) =>
    e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });

您可以使用 Where(...) 进行按 group 过滤。

为了获得一些“风格分”，请将 Flatten 转换为静态类中的扩展函数。

public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) =>
    e.SelectMany(c => c.Elements.Flatten()).Concat(e);

为了获得更多“更好的风格”积分，将Flatten转换为一个通用的扩展方法，该方法接受一个树和一个从节点产生后代的函数。

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> e
,   Func<T,IEnumerable<T>> f
) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);

这个函数的调用方式如下:

IEnumerable<MyNode> tree = ....
var res = tree.Flatten(node => node.Elements);

如果你更喜欢在预序中展开而不是后序中展开，请交换 Concat(...) 的两侧。

- Sergey Kalinichenko

---

我不同意: 使用c编写的代码是经过编译、测试并且能够正常工作的。而使用e则无法通过编译。你还可以添加if (e == null) return Enumerable.Empty<T>();来处理空的子列表。 - Adam Houldsworth

更像是这样的代码：public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> f) { if (source == null) return Enumerable.Empty<T>(); return source.SelectMany(c => f(c).Flatten(f)).Concat(source); } - myWallJSON

请注意，此解决方案的时间复杂度为O(nh)，其中n是树中项目的数量，h是树的平均深度。由于h可以在O(1)和O(n)之间变化，因此该算法的时间复杂度在O(n)到O(n平方)之间。有更好的算法可供使用。 - Eric Lippert

我注意到，如果列表是 IEnumerable<baseType> 类型，该函数将不会将元素添加到平坦列表中。 您可以通过以下方式调用该函数来解决问题： var res = tree.Flatten(node => node.Elements.OfType<DerivedType>) - Frank Horemans

@EricLippert 这是正确的，但如果深度不是问题，这是最易读的解决方案之一。 - Victorio Berra

Answer 2

接受的答案存在效率低下的问题，如果树的深度很大，则会导致堆栈溢出。您可以通过使用显式堆栈来解决此问题：

public static IEnumerable<MyNode> Traverse(this MyNode root)
{
    var stack = new Stack<MyNode>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in current.Elements)
            stack.Push(child);
    }
}

假设树的高度为h，分支因子远小于n，且树中有n个节点，则该方法在堆栈空间上是O(1)，在堆空间上是O(h)，在时间上是O(n)。另一种给出的算法在堆栈上是O(h)，在堆上是O(1)，在时间上是O(nh)。如果分支因子与n相比较小，则h介于O(lg n)和O(n)之间，这说明如果h接近n，那么朴素算法会使用危险数量的堆栈，并需要大量时间。

现在我们有了一个遍历，你的查询就很简单：

root.Traverse().Where(item=>item.group == 1);

- Eric Lippert

---

如果您要进行论点的辩论，那么这段代码可能并不是显然正确的。有什么方法可以使它更加明确正确呢？ - Eric Lippert

@ebramtharwat：正确。您可以在所有元素上调用 Traverse。或者您可以修改 Traverse 以接受一个序列，并使其将序列的所有元素推入 stack。记住，stack 是“我尚未遍历的元素”。或者您可以创建一个“虚拟”根，其中您的序列是其子级，然后遍历该虚拟根。 - Eric Lippert

如果您使用 foreach (var child in current.Elements.Reverse())，则会获得更符合预期的平整结果。特别是，子元素将按其出现顺序而非最后一个子元素先出现的方式呈现。在大多数情况下，这应该没有太大问题，但在我的情况下，我需要以可预测且符合预期的顺序进行平整。 - Micah Zoltu

@MicahZoltu，你可以通过将Stack<T>ж›їжЌўдёєQueue<T>来避免使用.ReverseгЂ‚ - Rubens Farias

@MicahZoltu 您对顺序是正确的，但“Reverse”的问题在于它会创建额外的迭代器，而这种方法旨在避免这种情况。@RubensFarias 将“Stack”替换为“Queue”会导致广度优先遍历。 - Jack A.

Answer 3

为了完整起见，这里是来自dasblinkenlight和Eric Lippert的答案的组合。已进行单元测试等。:-)

 public static IEnumerable<T> Flatten<T>(
        this IEnumerable<T> items,
        Func<T, IEnumerable<T>> getChildren)
 {
     var stack = new Stack<T>();
     foreach(var item in items)
         stack.Push(item);

     while(stack.Count > 0)
     {
         var current = stack.Pop();
         yield return current;

         var children = getChildren(current);
         if (children == null) continue;

         foreach (var child in children) 
            stack.Push(child);
     }
 }

- Konamiman

---

为了避免出现空引用异常： 获取当前节点的子节点：var children = getChildren(current);如果子节点不为空，将子节点逐个推入栈中： if (children != null) { foreach (var child in children) stack.Push(child); } - serg

请注意，尽管这将列表压平，但它会以相反的顺序返回。最后一个元素变成第一个等等。 - Corcus

如果 getChildren 为空，还应该检查并抛出异常。 - Jodrell

Answer 4

更新：

对于对嵌套层数感兴趣的人。显式枚举器堆栈实现的好处之一是，在任何时刻（特别是在生成元素时），stack.Count表示当前处理深度。因此，考虑到这一点并利用C#7.0的值元组，我们可以简单地更改方法声明如下：

public static IEnumerable<(T Item, int Level)> ExpandWithLevel<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)

yield语句：

yield return (item, stack.Count);

然后，我们可以通过在上述内容上应用简单的Select来实现原始方法：

public static IEnumerable<T> Expand<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) =>
    source.ExpandWithLevel(elementSelector).Select(e => e.Item);

翻译：

令人惊讶的是，甚至Eric也没有展示过递归先序DFT的“自然”迭代端口，因此在这里它来了：

    public static IEnumerable<T> Expand<T>(
        this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }

- Ivan Stoev

---

@NetMage 我想要特别的先序遍历。稍作修改它也可以处理后序遍历。但主要的点是，这是深度优先遍历。对于广度优先遍历我会使用Queue<T>。无论如何，这里的思路是保持一个带有枚举器的小栈，非常类似于递归实现中正在发生的事情。 - Ivan Stoev

@IvanStoev 我在想代码会变得更简单。我猜使用“堆栈”将导致一种锯齿形的广度优先遍历。 - NetMage

@TheodorZoulias（1）想象一下，每个级别都包含1000个“T”项。使用Stack<T>或Queue<T>需要推送/排队1000+1000+...+1000个项目，而Stack<IEnumerator<T>>将具有最大深度的活动枚举器对象。总的来说，枚举器比列表轻得多/使用的内存少 - 基本上是一些引用和位置。那么装箱呢？只有少数BCL集合类型枚举器是使用结构实现的，仅当您直接使用foreach时才会这样做。一旦您使用LINQ或IEnumerable<T>，所有这些优化都将消失，并且相同的装箱/GC压力适用。 - Ivan Stoev

@TheodorZoulias (2) 使用 Queue<T> 是进行广度优先遍历的必要条件。深度优先遍历需要使用栈。Stack<IEnumerator<T>> 只是反映了递归实现中的堆栈，例如 foreach (var e1 in source) foreach (var e2 in e1.Children) ... for each (var eN in eN-1.Children)（我猜您知道在 IEnumerable<T> 上使用 foreach 的含义 - using (var en = GetEnumerator()) while en.MoveNext() { ... } 等）。 - Ivan Stoev

Ivan，在仔细检查后，你两点都是正确的。装箱是不可避免的，存储一个子级枚举器肯定比存储所有子级更可取。已点赞。 :-) - Theodor Zoulias

Answer 5

我在这里找到了一些答案存在的小问题：

• 如果初始项列表为空怎么办？
• 如果子项列表中有空值怎么办？

基于之前的答案，我得出了以下结论：

public static class IEnumerableExtensions
{
    public static IEnumerable<T> Flatten<T>(
        this IEnumerable<T> items, 
        Func<T, IEnumerable<T>> getChildren)
    {
        if (items == null)
            yield break;

        var stack = new Stack<T>(items);
        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current;

            if (current == null) continue;

            var children = getChildren(current);
            if (children == null) continue;

            foreach (var child in children)
                stack.Push(child);
        }
    }
}

而单元测试：

[TestClass]
public class IEnumerableExtensionsTests
{
    [TestMethod]
    public void NullList()
    {
        IEnumerable<Test> items = null;
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(0, flattened.Count());
    }
    [TestMethod]
    public void EmptyList()
    {
        var items = new Test[0];
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(0, flattened.Count());
    }
    [TestMethod]
    public void OneItem()
    {
        var items = new[] { new Test() };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(1, flattened.Count());
    }
    [TestMethod]
    public void OneItemWithChild()
    {
        var items = new[] { new Test { Id = 1, Children = new[] { new Test { Id = 2 } } } };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(2, flattened.Count());
        Assert.IsTrue(flattened.Any(i => i.Id == 1));
        Assert.IsTrue(flattened.Any(i => i.Id == 2));
    }
    [TestMethod]
    public void OneItemWithNullChild()
    {
        var items = new[] { new Test { Id = 1, Children = new Test[] { null } } };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(2, flattened.Count());
        Assert.IsTrue(flattened.Any(i => i.Id == 1));
        Assert.IsTrue(flattened.Any(i => i == null));
    }
    class Test
    {
        public int Id { get; set; }
        public IEnumerable<Test> Children { get; set; }
    }
}

- Doug Clutter

Answer 6

这里提供的大部分答案都会生成 深度优先 或者之字形序列。例如，从下面的树开始：

        1                   2 
       / \                 / \
      /   \               /   \
     /     \             /     \
    /       \           /       \
   11       12         21       22
  / \       / \       / \       / \
 /   \     /   \     /   \     /   \
111 112   121 122   211 212   221 222

Sergey Kalinichenko的答案生成了这个扁平化的序列：

111, 112, 121, 122, 11, 12, 211, 212, 221, 222, 21, 22, 1, 2

Konamiman的答案（泛化了Eric Lippert的答案）生成了这个扁平序列：

2, 22, 222, 221, 21, 212, 211, 1, 12, 122, 121, 11, 112, 111

Ivan Stoev的答案生成了这个扁平化序列：

1, 11, 111, 112, 12, 121, 122, 2, 21, 211, 212, 22, 221, 222

如果你对像这样的广度优先序列感兴趣：

1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222

...那么这就是适合您的解决方案：

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector)
{
    var queue = new Queue<T>(source);
    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        yield return current;
        var children = childrenSelector(current);
        if (children == null) continue;
        foreach (var child in children) queue.Enqueue(child);
    }
}

实现的区别基本上是使用队列Queue而不是栈Stack。没有进行实际的排序。

---

注意：这种实现在内存效率方面远非最佳，因为在枚举过程中总元素数量的大部分将被存储在内部队列中。基于Stack的树遍历比基于Queue的实现更加高效，可以更好地利用内存。

- Theodor Zoulias

Answer 7

如果有其他人发现这篇文章，但是需要知道在展开树之后的级别，那么这篇文章将会进一步解释Konamiman和Eric Lippert的方案：

    public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(
            this IEnumerable<T> items,
            Func<T, IEnumerable<T>> getChilds)
    {
        var stack = new Stack<Tuple<T, int>>();
        foreach (var item in items)
            stack.Push(new Tuple<T, int>(item, 1));

        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current;
            foreach (var child in getChilds(current.Item1))
                stack.Push(new Tuple<T, int>(child, current.Item2 + 1));
        }
    }

- Dave

Answer 8

一个更好的选择是采用合适的面向对象设计。

例如：请求MyNode返回所有展平的结果。

就像这样：

class MyNode
{
    public MyNode Parent;
    public IEnumerable<MyNode> Elements;
    int group = 1;

    public IEnumerable<MyNode> GetAllNodes()
    {
        if (Elements == null)
        {
            return Enumerable.Empty<MyNode>(); 
        }

        return Elements.SelectMany(e => e.GetAllNodes());
    }
}

现在您可以请求顶级 MyNode 获取所有节点。

var flatten = topNode.GetAllNodes();

如果您无法编辑该类，则这不是一个选项。但是，否则，我认为将另一个（递归）LINQ方法作为首选可能更好。

由于此处使用了LINQ，因此我认为这个答案是适用的 ;)

- Julian

---

也许 Enumerable.Empty 比 new List 更好？ - Frank

确实！已更新！ - Julian

Answer 9

如果您需要嵌套级别并且需要按顺序展平列表而不是像Konamiman提供的答案中那样反转，请结合Dave和Ivan Stoev的答案。

 public static class HierarchicalEnumerableUtils
    {
        private static IEnumerable<Tuple<T, int>> ToLeveled<T>(this IEnumerable<T> source, int level)
        {
            if (source == null)
            {
                return null;
            }
            else
            {
                return source.Select(item => new Tuple<T, int>(item, level));
            }
        }

        public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
        {
            var stack = new Stack<IEnumerator<Tuple<T, int>>>();
            var leveledSource = source.ToLeveled(0);
            var e = leveledSource.GetEnumerator();
            try
            {
                while (true)
                {
                    while (e.MoveNext())
                    {
                        var item = e.Current;
                        yield return item;
                        var elements = elementSelector(item.Item1).ToLeveled(item.Item2 + 1);
                        if (elements == null) continue;
                        stack.Push(e);
                        e = elements.GetEnumerator();
                    }
                    if (stack.Count == 0) break;
                    e.Dispose();
                    e = stack.Pop();
                }
            }
            finally
            {
                e.Dispose();
                while (stack.Count != 0) stack.Pop().Dispose();
            }
        }
    }

- Corcus

---

还可以指定深度优先或广度优先，这也是很好的。 - Hugh

Answer 10

以下是使用队列实现的代码示例，先返回树的自身节点，再返回它的子节点。

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> items, 
    Func<T,IEnumerable<T>> getChildren)
    {
        if (items == null)
            yield break;

        var queue = new Queue<T>();

        foreach (var item in items) {
            if (item == null)
                continue;

            queue.Enqueue(item);

            while (queue.Count > 0) {
                var current = queue.Dequeue();
                yield return current;

                if (current == null)
                    continue;

                var children = getChildren(current);
                if (children == null)
                    continue;

                foreach (var child in children)
                    queue.Enqueue(child);
            }
        }

    }

- Ruben Alfonso Reyes