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

本文关键字：数据 深度 分层 获取 何使用 linq 查询 | 更新日期: 2023-09-27 18:33:56

我有一个分层数据列表，如下所示：

var list = new List<Data>(){some data...}
class Data
{
    public int number;
    public List<Data> info;
}

注：树叶数据 --> info = null

例：

数字是数据类的number property

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

如何使用linq查询（不是递归方法或for循环）知道树的最大深度到数据列表？

在此示例中，对于 321,322，最大级别为 3

谢谢。

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

LINQ和SQL对平面数据结构进行操作;它们不是为递归数据结构设计的。

使用 LINQ to Entities，我相信您就不走运了。将子树的深度存储在每个节点中，并在插入/删除节点时递归更新它。

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

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

哪里

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

所有 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)

以下方法有效：

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

如果你应该在数据库中使用它，我建议在你的数据库中添加额外的列来保存树的深度，在某些情况下深度会发生变化：

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

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

相关文章：