logo标签列表

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

c#.netlinq.net-4.0tree
118

我有一棵简单的树：

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

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

1
您希望展开的列表按什么顺序排列？ - Philip
1
节点何时停止拥有子节点？我猜想是当“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
15个回答
0
以下是Ivan Stoev的代码，增加了每个路径对象的索引功能。例如，搜索“Item_120”：
Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

将返回该项和一个整数数组[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();
    }
}
嗨，@lisz，你把这段代码粘贴在哪里？我遇到了一些错误，比如“修饰符'public'对于此项无效”，“修饰符'static'对于此项无效”。 - Kynao
0

基于之前的回答先序遍历展开

        public static IEnumerable<T> Flatten<T>(
           this IEnumerable<T> e
        , Func<T, IEnumerable<T>> f
         ) => e.Concat(e.SelectMany(c => f(c).Flatten(f)));
0
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;
}
1
在您的扩展中使用 foreach 意味着它不再是“延迟执行”（当然，除非您使用 yield return）。 - Tri Q Tran
0

偶尔我会尝试解决这个问题，并设计出支持任意深度结构（无递归），执行广度优先遍历，不滥用太多LINQ查询或预先在子节点上执行递归的解决方案。在研究了.NET源代码并尝试了许多解决方案后，我终于想出了这个解决方案。最终结果非常接近Ian Stoev的答案（我刚刚才看到他的答案），但我的解决方案没有使用无限循环或具有异常的代码流程。

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> fnRecurse)
{
    if (source != null)
    {
        Stack<IEnumerator<T>> enumerators = new Stack<IEnumerator<T>>();
        try
        {
            enumerators.Push(source.GetEnumerator());
            while (enumerators.Count > 0)
            {
                var top = enumerators.Peek();
                while (top.MoveNext())
                {
                    yield return top.Current;

                    var children = fnRecurse(top.Current);
                    if (children != null)
                    {
                        top = children.GetEnumerator();
                        enumerators.Push(top);
                    }
                }

                enumerators.Pop().Dispose();
            }
        }
        finally
        {
            while (enumerators.Count > 0)
                enumerators.Pop().Dispose();
        }
    }
}

可以在这里找到一个可工作的示例。

0

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

还有一个使用示例：

var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接