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と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 に答える
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 に答える
0

DBで使用する必要がある場合は、DBに列を追加してツリーの深さを保存することをお勧めします。深さが変わる状況がいくつかあります。

  1. 新しい要素を追加すると、その深さはFatherDepth+1です。
  2. 削除：これがカスケード関係である場合、削除に問題はありませんが、カスケードでない場合は、子の深さを更新する再帰クエリを作成する必要があります。

深さを見つけるには、クエリを実行して最大深さの値を見つけます。

于 2012-05-13T18:52:45.083 に答える