1

これをできる限り説明しようと思います。このロジックを理解するのにかなり苦労しています。

基本的に、親と子のプロパティでそれぞれ構成される何千ものオブジェクトを含むコレクションがあります。

したがって、大まかに、これは次のとおりです。


public class MyObject{
     public string Parent { get; set; }
     public string Child { get; set; }
}

私が理解しようとしているのは、これをプレーンな TreeView コントロールに組み込む方法です。関係を構築する必要がありますが、それらが混在する可能性があるため、その方法がわかりません。ツリーがどのように見えるべきかで、おそらくこれをよりよく説明できます。

したがって、コレクション内に次のアイテムがあるとします。


0. Parent: "A", Child: "B"
1. Parent: "B", Child: "C"
2. Parent: "B", Child: "D"

私は自分のツリーを次のように見せたいと思います:


-A
--B
---C
-A
--B
---D
-B
--C
-B
--D

C#でこれを行うにはどうすればよいですか? 約 50 ノードの深さに達すると予想されるブランチがいくつかあるため、最大 N 個のリレーションシップをサポートする必要があります。

4

3 に答える 3

5

アップデート

パスごとにツリー全体を繰り返す必要があるため、この問題は実際には私が最初に認識したよりもかなり複雑であることが判明しました。これ以上混乱させたくないので、古いコードを単に削除しました。

再帰データ構造を使用するとこれが簡単になることを記録しておきたいと思います。

public class MyRecursiveObject
{
    public MyRecursiveObject Parent { get; set; }
    public string Name { get; set; }
    public List<MyRecursiveObject> Children { get; set; }
}

以下の実装コードを読むと、なぜこれが簡単なのかがはっきりとわかります。

private void PopulateTree(IEnumerable<MyObject> items)
{
    var groupedItems =
        from i in items
        group i by i.Parent into g
        select new { Name = g.Key, Children = g.Select(c => c.Child) };
    var lookup = groupedItems.ToDictionary(i => i.Name, i => i.Children);
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, Enumerable.Empty<string>(), parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        IEnumerable<string> newPath = path.Concat(new string[] { name });
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
    }
    else
    {
        TreeNode parentNode = null;
        foreach (string item in path)
            parentNode = AddTreeNode(parentNode, item);
        AddTreeNode(parentNode, name);
    }
}

private TreeNode AddTreeNode(TreeNode parent, string name)
{
    TreeNode node = new TreeNode(name);
    if (parent != null)
        parent.Nodes.Add(node);
    else
        treeView1.Nodes.Add(node);
    return node;
}

まず、ディクショナリにはルート ノードだけでなく中間ノードのキーも含まれることに気付きました。そのAddToTreeため、「B」ノードをルートとして取得するために、再帰メソッドで 2 回の再帰呼び出しを行う必要はありません。メソッドの最初のウォークでPopulateTree既に実行されています。

防御する必要があるのは、最初のウォークでリーフ ノードを追加することです。問題のデータ構造を使用して、これらは親辞書にキーがあるかどうかを確認することで検出できます。再帰的なデータ構造を使用すると、これはずっと簡単になります: をチェックするだけですParent == null。しかし、再帰構造は私たちが持っているものではないため、上記のコードを使用する必要があります。

ほとんどがユーティリティ メソッドであるため、後でこのAddTreeNodenull チェック ロジックを繰り返し続ける必要はありません。

本当の醜さは、2 番目の再帰的なAddToTree方法にあります。すべてのサブツリーの一意のコピーを作成しようとしているため、単純にツリー ノードを追加して、そのノードを親として再帰することはできません。ここでは、"A" には "B" という 1 つの子しかありませんが、"B" には "C" と "D" という 2 つの子があります。"A" の 2 つのコピーが必要ですが、"A" が最初にAddToTreeメソッドに渡されたときにそれを知る方法はありません。

したがって、実際に行う必要があるのは、最終段階までノードを作成せず、一時的なパスを保存することです。パスは不変IEnumerable<string>であり、混乱することはありません。追加する子がさらにある場合、このメソッドは単純にパスに追加して再帰します。子がなくなると、保存されたパス全体をたどり、それぞれにノードを追加します。

の呼び出しごとに新しい列挙型を作成しているため、これは非常にAddToTree非効率的です。多数のノードの場合、大量のメモリを消費する可能性があります。これは機能しますが、再帰的なデータ構造を使用するとより効率的になります。上部の構造例を使用すると、パスを保存したり、辞書を作成したりする必要はまったくありません。while子が残っていない場合は、参照を使用してループでパスをたどってParentください。

とにかく、これは再帰オブジェクトではないのでアカデミックだと思いますが、将来の設計のために覚えておくべきこととして、とにかく指摘する価値があると思いました。上記のコードはまさにあなたが望む結果を生成します。実際の TreeView でテストしてみました。

更新 2 - したがって、上記のバージョンはメモリ/スタックに関してかなり残忍であることが判明しました。おそらく、これらすべてのIEnumerable<string>インスタンスを作成した結果です。素晴らしい設計ではありませんが、可変に変更することでその特定の問題を取り除くことができList<string>ます。次のスニペットは、違いを示しています。

private void PopulateTree(IEnumerable<MyObject> items)
{
    // Snip lookup-generation code - same as before ...

    List<string> path = new List<string>();
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, path, parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        path.Add(name);
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
        path.Remove(name);
    }
    // Snip "else" block - again, this part is the same as before ...
}
于 2010-01-30T04:37:12.450 に答える
0

ルーベンスのように、私は両方を試しましたが、もう少し良いと思いますA Generic Tree Collection

このツリー コレクションには、ツリー内を移動するための優れた機能が組み込まれています。記事全体を読んでください。

上記リンクのサンプル

Static Class Module1
{

    public static void Main()
    {
        Common.ITree<myObj> myTree = default(Common.ITree<myObj>);
        myObj a = new myObj("a");
        myObj b = new myObj("b");
        myObj c = new myObj("c");
        myObj d = new myObj("d");

        myTree = Common.NodeTree<myObj>.NewTree;
        myTree.InsertChild(a).InsertChild(b).InsertChild(c).Parent.Parent.InsertNext(a).InsertChild(b).InsertChild(d).Parent.Parent.InsertNext(b).InsertChild(c).Parent.InsertNext(b).InsertChild(d);

        Console.WriteLine(myTree.ToStringRecursive);

        Console.ReadKey();
    }
}

Class myObj
{
    public string text;

    public myObj(string value)
    {
        text = value;
    }

    public override string ToString()
    {
        return text;
    }
}

ちょうどあなたが示したものです

-A
--B
---C
-A --B ---D
-B --C -B --D




于 2010-01-30T04:35:15.427 に答える