1

フラットリストから動的な階層構造を返す方法は2つあります。最初の方法は、ここで再帰メソッドを使用するとうまく機能します：（ID / ParentID）リストから階層リストへ。

今回はレポート出力が保存されているカテゴリとレポートのみを表示することを除いて、同じことをしようとしています。私が見つけたものはすべてルートから下に構築されており、下から上に行く必要があるため、どこから始めればよいかわかりません。

私は今、私の最初の方法でこのようなものを手に入れました：

Category 1
  |_Sub Category 1
    |_Report 1
    |_Report 2
      |_Saved Output
Category 2
  |_Sub Category 2
  | |_Report 3
  | |_Report 4
  |_Sub Category 3
    |_Report 5
    |_Report 6
      |_Saved Output
Category 3
  |_Sub Category 4
    |_Report 7

私の2番目の方法で欲しいのはこれです：

Category 1
  |_Sub Category 1
    |_Report 2
      |_Saved Output
Category 2
  |_Sub Category 3
    |_Report 6
      |_Saved Output

これが私の基本的なテスト構造です：

class Flat
{
    public int id { get; set; }
    public int parentId { get; set; }
    public string name { get; set; }
    public bool isOutput { get; set; }

    public Flat(int i, int pid, string n, bool o)
    {
        this.id = i;
        this.parentId = pid;
        this.name = n;
        this.isOutput = o;
    }
}

class MyClass
{
    public int id { get; set; }
    public int parentId { get; set; }
    public string name { get; set; }
    public bool isOutput { get; set; }

    public List<MyClass> children { get; set; }

    public MyClass()
    {
        this.children = new List<MyClass>();
    }
}

List<Flat> items = new List<Flat>()
        {
                new Flat(1,0,"Category 1",false),
                new Flat(4,1,"Sub Category 1",false),
                new Flat(8,4,"Report 1",false),
                new Flat(9,4,"Report 2",false),
                new Flat(15,9,"Saved Output",true),
                new Flat(2,0,"Category 2",false),
                new Flat(5,2,"Sub Category 2",false),
                new Flat(10,5,"Report 3",false),
                new Flat(11,5,"Report 4",false),
                new Flat(6,2,"Sub Category 3",false),
                new Flat(12,6,"Report 5",false),
                new Flat(13,6,"Report 6",false),
                new Flat(16,13,"Saved Output",true),
                new Flat(3,0,"Category 3",false),
                new Flat(7,3,"Sub Category 4",false),
                new Flat(14,7,"Report 7",false)
        };
4

3 に答える 3

2

ボトムアップでビルドするには、有効なすべてのリーフノード（output == true）から始めて、ルートに到達するまですべての親ノードを上向きに処理する必要があります。動作するはずの1つの方法は次のとおりです。

List<Flat> GetSavedOutput(List<Flat> items)
{
    // get all output leaf nodes
    var toAdd = items.Where (i => i.isOutput == true).ToList();
    var result = new List<Flat>();

    // grab all parent nodes that are not already included until
    // there's nothing new to add
    while (toAdd.Count > 0)
    {
        result.AddRange(toAdd);
        toAdd = items.Where (i => !result.Contains(i)
                               && result.Any (r => r.parentId == i.id)).ToList();
    }

    return result;
}

これは短くて迅速で、小さくて単純なツリーにはうまく機能するはずですが、同じノードを何度も処理するため、最も効率的な方法ではありません。もう少し複雑ですが、より良い方法は、各アイテムの親ツリーを上に移動することです。

List<Flat> GetSavedOutput(List<Flat> items)
{
    var savedOutput = items.Where (i => i.isOutput == true).ToList();
    var result = new List<Flat>();

    foreach (var item in savedOutput) {
        result.Add(item);
        var temp = item;
        do {
            temp = items.Single (i => i.id == temp.parentId);
            result.Add(temp);
        } while (temp.parentId != 0);
    }

    return result;
}

それでも十分に効率的でない場合は、各インスタンスに親ノードへの参照を格納することでパフォーマンスを少し向上させることができます。これにより、への呼び出しを使用して親を検索Flatしなくても、親を直接参照できます。これにより、効率が向上します。O(1)SingleO(n)

于 2013-01-23T05:25:55.610 に答える
1

まず、指定されたリストに基づいて、アイテムに出力アイテムへのパスがあるかどうかを判断するための再帰メソッドを定義することをお勧めします。

static bool HasPathToOutput(List<Flat> items, Flat item)
{
    if (item.isOutput)
    {
        return true;
    }

    // Recursively determine whether any of the item's children have
    // a path to an output
    return items.Where(i => i.parentId == item.id).Any(i => HasPathToOutput(items, i));
}

次に、そのメソッドを使用して、いくつかのLINQクエリでリストを実行します。最初に、保存された出力へのパスを持つアイテムを取得し、次に階層を構築し、最後に、階層の最上位にあるアイテムのみを取得します。

// Generate a predicate based on the list
List<MyClass> foundItems = 
       items.Where(item => HasPathToOutput(items, item))
            .Select(f => new MyClass { id = f.id, isOutput = f.isOutput, parentId = f.parentId, name = f.name })
            .ToList();

// Generate child relationships
foundItems.ForEach(item => item.children = foundItems.Where(child => child.parentId == item.id).ToList());

// Filter out top-level items
List<MyClass> topLevel = foundItems.Where(i => i.parentId == 0).ToList();
于 2013-01-23T05:49:20.197 に答える
0

データの深さ優先をトラバースしたい

これにより、最初にすべてのリーフノードが確認され、保存された要素がリストに追加され、ルートノードが保存されたことを親ノードに通知されます。

public bool StoreSavedElements(List<Tree> elements)
{
    bool nodeSaved = false;

    foreach (Tree child in childs)
    {
        if (child.StoreSavedElements(elements))
        {
            nodeSaved = true;
        }
    }

    if (this.text == "Saved")
    {
        nodeSaved = true;
        elements.Add(this);
    }

    return nodeSaved;
}
于 2013-01-23T10:12:05.720 に答える