7

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

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

谢谢。

4

4 回答 4

1

所有 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)
于 2012-05-13T18:30:20.980 回答
1

以下将起作用：

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();
于 2012-05-13T19:10:51.913 回答
1

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())));
}
于 2012-05-13T09:41:14.687 回答
0

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

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

要查找深度，只需运行查询以查找最大深度值。

于 2012-05-13T18:52:45.083 回答