C# 如何通过LINQ压平树？

Question

提问by myWallJSON

So I have simple tree:

所以我有简单的树：

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

I have a IEnumerable<MyNode>. I want to get a list of all MyNode(including inner node objects (Elements)) as one flat list Wheregroup == 1. How to do such thing via LINQ?

我有一个IEnumerable<MyNode>. 我想将所有MyNode（包括内部节点对象 ( Elements)）的列表作为一个平面列表Wheregroup == 1。如何通过 LINQ 做这样的事情？

Answer 1

采纳答案by dasblinkenlight

You can flatten a tree like this:

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

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

You can then filter by groupusing Where(...).

然后，您可以group使用进行过滤Where(...)。

To earn some "points for style", convert Flattento an extension function in a static class.

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

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

To earn more points for "even better style", convert Flattento a generic extension method that takes a tree and a function that produces descendants from a node:

要为“更好的风格”获得更多积分，请转换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);

Call this function like this:

像这样调用这个函数：

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

If you would prefer flattening in pre-order rather than in post-order, switch around the sides of the Concat(...).

如果您更喜欢按预排序而不是按后排序进行展平，请在Concat(...).

Answer 2

回答by Tom Brothers

void Main()
{
    var allNodes = GetTreeNodes().Flatten(x => x.Elements);

    allNodes.Dump();
}

public static class ExtensionMethods
{
    public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector = null)
    {
        if (source == null)
        {
            return new List<T>();
        }

        var list = source;

        if (childrenSelector != null)
        {
            foreach (var item in source)
            {
                list = list.Concat(childrenSelector(item).Flatten(childrenSelector));
            }
        }

        return list;
    }
}

IEnumerable<MyNode> GetTreeNodes() {
    return new[] { 
        new MyNode { Elements = new[] { new MyNode() }},
        new MyNode { Elements = new[] { new MyNode(), new MyNode(), new MyNode() }}
    };
}

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

Answer 3

回答by Eric Lippert

The problem with the accepted answer is that it is inefficient if the tree is deep. If the tree is verydeep then it blows the stack. You can solve the problem by using an explicit stack:

已接受答案的问题在于，如果树很深，则效率低下。如果树是非常深的，然后它吹堆栈。您可以通过使用显式堆栈来解决问题：

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

Assuming n nodes in a tree of height h and a branching factor considerably less than n, this method is O(1) in stack space, O(h) in heap space and O(n) in time. The other algorithm given is O(h) in stack, O(1) in heap and O(nh) in time. If the branching factor is small compared to n then h is between O(lg n) and O(n), which illustrates that the na?ve algorithm can use a dangerous amount of stack and a large amount of time if h is close to n.

假设高度为 h 的树中的 n 个节点和远小于 n 的分支因子，此方法在堆栈空间中为 O(1)，在堆空间中为 O(h)，在时间上为 O(n)。给出的另一个算法是堆栈中的 O(h)，堆中的 O(1) 和时间中的 O(nh)。如果分支因子与 n 相比较小，则 h 介于 O(lg n) 和 O(n) 之间，这说明如果 h 接近n.

Now that we have a traversal, your query is straightforward:

现在我们有了遍历，您的查询很简单：

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

Answer 4

回答by Konamiman

Just for completeness, here is the combination of the answers from dasblinkenlight and Eric Lippert. Unit tested and everything. :-)

为了完整起见，这里是来自 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);
     }
 }

Answer 5

回答by Dave

In case anyone else finds this, but also needs to know the level after they've flattened the tree, this expands on Konamiman's combination of dasblinkenlight and Eric Lippert's solutions:

万一其他人发现了这一点，但也需要知道他们压平树后的级别，这扩展了 Konamiman 的 dasblinkenlight 和 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));
        }
    }

Answer 6

回答by Ivan Stoev

Update:

更新：

For people interested in level of nesting (depth). One of the good things about explicit enumerator stack implementation is that at any moment (and in particular when yielding the element) the stack.Countrepresents the currently processing depth. So taking this into account and utilizing the C#7.0 value tuples, we can simply change the method declaration as follows:

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

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

and yieldstatement:

和yield声明：

yield return (item, stack.Count);

Then we can implement the original method by applying simple Selecton the above:

然后我们可以通过Select在上面应用 simple 来实现原始方法：

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

Original:

原来的：

Surprisingly no one (even Eric) showed the "natural" iterative port of a recursive pre-order DFT, so here it is:

令人惊讶的是，没有人（甚至 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();
        }
    }

Answer 7

回答by Corcus

Combining Dave's and Ivan Stoev's answer in case you need the level of nesting and the list flattened "in order" and not reversed like in the answer given by Konamiman.

结合 Dave 和 Ivan Stoev 的答案，以防您需要嵌套级别，并且列表“按顺序”展平，而不是像 Konamiman 给出的答案那样颠倒。

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

Answer 8

回答by rothschild86

Building on Konamiman's answer, and the comment that the ordering is unexpected, here's a version with an explicit sort param:

基于 Konamiman 的回答，以及排序出乎意料的评论，这里有一个带有显式排序参数的版本：

public static IEnumerable<T> TraverseAndFlatten<T, V>(this IEnumerable<T> items, Func<T, IEnumerable<T>> nested, Func<T, V> orderBy)
{
    var stack = new Stack<T>();
    foreach (var item in items.OrderBy(orderBy))
        stack.Push(item);

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

        var children = nested(current).OrderBy(orderBy);
        if (children == null) continue;

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

And a sample usage:

以及示例用法：

var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();

Answer 9

回答by lisz

Below is Ivan Stoev's code with the additonal feature of telling the index of every object in the path. E.g. search for "Item_120":

下面是 Ivan Stoev 的代码，它具有告诉路径中每个对象的索引的附加功能。例如搜索“Item_120”：

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

would return the item and an int array [1,2,0]. Obviously, nesting level is also available, as length of the array.

将返回该项目和一个 int 数组 [1,2,0]。显然，嵌套级别也是可用的，作为数组的长度。

public static IEnumerable<(T, int[])> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> getChildren) {
    var stack = new Stack<IEnumerator<T>>();
    var e = source.GetEnumerator();
    List<int> indexes = new List<int>() { -1 };
    try {
        while (true) {
            while (e.MoveNext()) {
                var item = e.Current;
                indexes[stack.Count]++;
                yield return (item, indexes.Take(stack.Count + 1).ToArray());
                var elements = getChildren(item);
                if (elements == null) continue;
                stack.Push(e);
                e = elements.GetEnumerator();
                if (indexes.Count == stack.Count)
                    indexes.Add(-1);
                }
            if (stack.Count == 0) break;
            e.Dispose();
            indexes[stack.Count] = -1;
            e = stack.Pop();
        }
    } finally {
        e.Dispose();
        while (stack.Count != 0) stack.Pop().Dispose();
    }
}

Answer 10

回答by Doug Clutter

I found some small issues with the answers given here:

我发现这里给出的答案有一些小问题：

What if the initial list of items is null?
What if there is a null value in the list of children?

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

Built on the previous answers and came up with the following:

建立在以前的答案的基础上，并提出以下内容：

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

And the unit tests:

和单元测试：

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

C# 如何通过LINQ压平树？

提问by myWallJSON

采纳答案by dasblinkenlight

回答by Tom Brothers

回答by Eric Lippert

回答by Konamiman

回答by Dave

回答by Ivan Stoev

回答by Corcus

回答by rothschild86

回答by lisz

回答by Doug Clutter

相关推荐

最近更新

标签

C# 如何通过LINQ压平树？

提问by myWallJSON

采纳答案by dasblinkenlight

回答by Tom Brothers

回答by Eric Lippert

回答by Konamiman

回答by Dave

回答by Ivan Stoev

回答by Corcus

回答by rothschild86

回答by lisz

回答by Doug Clutter

相关推荐

如何在 C# 中调用 SQL 函数？

C# Request.Cookies 和 Response.Cookies 的区别

在 C# 中使用 ping

C# 在 webservice 的情况下如何从 WSDL 生成代理类

相关推荐

最近更新

标签