3

入力が ID のリストで、出力がすべての親ノードに基づくノードを持つツリーである関数を作成しようとしています。ID

各ノードにはParentID. Home(ID: 1) がルートです。

関数ヘッダーは次のようになります。

public ModuleDTO GetModuleTree(List<int> ids);

サンプル ツリーは次のようになります。

  • 1 ホーム
    • 2 アプリケーション
    • 3 教えること
      • 4コース
      • 5部屋
      • 6 教師
    • 7 研究
      • 8 出版物
    • 9 卒業

が関数4に渡されると、次のようなツリーが返されます。

  • 1 ホーム
    • 3 教えること
      • 4コース

5と8が関数に渡されると、次のようなツリーが返されます。

  • 1 ホーム
    • 3 教えること
      • 5部屋
    • 7 研究
      • 8 出版物

が関数3に渡されると、次のようなツリーが返されます。

  • 1 ホーム
    • 3 教えること

私のクラスは次のとおりです。

public class ModuleDTO
{
    public int ID { get; set; }
    public string Name { get; set; }
    public string TitleIS { get; set; }
    public string TitleEN { get; set; }
    public string RootURL { get; set; }
    public int? ParentID { get; set; }
    public List<ModuleDTO> ChildModules { get; set; }

    public ModuleDTO()
    {
        ChildModules = new List<ModuleDTO>();
    }
}

前もって感謝します。

4

2 に答える 2

1

私はこれでそれを解決しました：

public ModuleDTO GetModulesForUser(string userName)
{
    // Returns the list of IDs
    var ids = ListOfUserModules(userName);

    var modules = GetModuleTree(null);
    var module = modules.First();

    PruneTree(module, ids);

    return module;
}

public List<ModuleDTO> GetModuleTree(ModuleDTO parentModule)
{
    int? parentID = null;

    if (parentModule != null)
    {
        parentID = parentModule.ID;
    }

    var childModules = _modules.All().Where(s => s.ParentID == parentID).Select(x => x.ToDTO());

    List<ModuleDTO> modules = new List<ModuleDTO>();

    foreach (var m in childModules)
    {
        m.ChildModules = GetModuleTree(m);
        modules.Add(m);
    }

    return modules;
}

private void PruneTree(ModuleDTO root, List<int> ids)
{
    for(int i = root.ChildModules.Count() - 1; i >= 0; i--)
    {
        PruneTree(root.ChildModules[i], ids);
        if (root.ChildModules[i].ChildModules.Count == 0)
        {
            if (!ids.Contains(root.ChildModules[i].ID))
            {
                root.ChildModules.RemoveAt(i);
            }
        }
    }
}
于 2013-10-30T17:00:07.277 に答える
1

(ここではルックアップ速度はそれほど重要ではない、またはツリーが適度に小さいと仮定します)

まず、単一の入力に対する答えを見つけることについて考えてみましょう。ここで使用可能なアプローチは、再帰アルゴリズムである深さ優先型アルゴリズムを試すことです。ツリーのすべてのノードを見て、見つけたらすぐに返します。再帰から戻り始めるとすぐに、ツリーを「上」に進み、途中のすべてのノードをホーム ノードに戻します。

複数の ID を持つケースは、これを数回実行し、すべての結果を結合するだけになります。

もちろん、パフォーマンスのニーズとデータ構造を変更する自由度に応じて、このアルゴリズムに加えられるいくつかの改善や、他のアプローチも可能です。ただし、上記のソリューションの実装ほど単純で明確ではないかもしれません。

于 2013-10-29T21:58:54.043 に答える