如何使用linq查询获取分层数据的深度？

Question

我有一个像这样的分层数据列表：

var list = new List<Data>(){some data...}

class Data
{
    public int number;
    public List<Data> info;
}

注意：树叶中的数据为-->info = null 示例：

数字是Data类的number property

   --1
      --11
   --2
      --21
      --22
      --23
      --24
   --3
      --31
      --32
          --321
          --322
   --4
      --41
      --42

如何使用 linq 查询（非递归方法或 for 循环）获取树的最大深度？将其应用于数据列表中。

在此示例中，321、322 的最大级别为 3。

谢谢。

- Reza ArabQaeni

---

LINQ是针对线性数据序列设计的，不适用于递归数据结构。使用递归方法有什么问题？ - dtb

没有错，我很好奇如何用linq解决这个问题。 - Reza ArabQaeni

特别是在LINQ to Entities中，为了使用一个查询语句实现这个目标，我不能使用递归方法。 - Reza ArabQaeni

你有一个递归数据结构 - 你需要一些形式的递归来遍历数据。 - Enigmativity

我认为使用映射函数进行计算并在Linq to entities中调用它可以解决问题，而不需要遍历数据，对吗？ - Reza ArabQaeni

Answer 1

LINQ和SQL操作的是扁平数据结构，它们不适用于递归数据结构。

使用LINQ to Entities，我认为你没有办法。在每个节点中存储子树的深度，并在插入/删除节点时递归更新它。

使用LINQ to Objects，您可以定义一个递归扩展方法，返回树中所有路径并获取最长路径的长度：

var result = root.Paths().Max(path => path.Length);

where

public static IEnumerable<Data[]> Paths(this Data data)
{
    return Paths(data, new[] { data });
}

private static IEnumerable<Data[]> Paths(Data data, Data[] path)
{
    return new[] { path }.Concat((data.info ?? Enumerable.Empty<Data>())
    .SelectMany(child => Paths(child, path.Concat(new[] { child }).ToArray())));
}

- dtb

Answer 2

所有的Linq操作符都以某种方式使用循环，因此如果要求不使用循环，则无法使用Linq解决。

没有递归也是可能的。你只需要一个栈。类似这样的东西。

public static IEnumerable<Tuple<int, T>> FlattenWithDepth<T>(T root, Func<T, IEnumerable<T>> children) {
    var stack = new Stack<Tuple<int, T>>();

    stack.Push(Tuple.Create(1, root));

    while (stack.Count > 0) {
        var node = stack.Pop();

        foreach (var child in children(node.Item2)) {
            stack.Push(Tuple.Create(node.Item1+1, child));
        }
        yield return node;
    }
}

你的 Linq 查询将会是：

FlattenWithDepth(root, x => x.info ?? Enumerable.Empty<Data>()).Max(x => x.Item1);

（抱歉，没有编译器可用来验证）

**编辑。刚看到您有多个根目录**

list.SelectMany(y => FlattenWithDepth(y, x => x.info ?? Enumerable.Empty<Data>()))
    .Max(x => x.Item1)

- adrianm

Answer 3

以下内容可行：

internal static class ListDataExtension
{
    public static int MaxDepthOfTree(this List<Data> dataList)
    {
        return dataList.Max(data => data.MaxDepthOfTree);
    }
}
internal class Data
{
    public int number;
    public List<Data> info;

    public int MaxDepthOfTree
    {
        get 
        { 
            return GetDepth(1); 
        }
    }

    int GetDepth(int depth)
    {
        if (info == null)
            return depth;
        var maxChild = info.Max(x => x.GetDepth(depth));
        return maxChild + 1;
    }
}

然后只需调用：

var maxDepth = list.MaxDepthOfTree();

- Eric Dahlvang

Answer 4

如果您需要在数据库中使用它，我建议您添加一个额外的列来保存树的深度。有一些情况可能会导致树的深度发生变化：

1. 添加新元素，其深度为父元素深度+1。
2. 删除：如果这是级联关系，删除不会有问题；但如果不是级联关系，则应编写递归查询以更新子元素的深度。

要查找深度，只需运行一个查询即可找到最大深度值。

- Saeed Amiri