树干算法

Question

我正在尝试创建一个函数，其中输入是is的列表，和输出是一棵树，节点是基于节点的ID和所有父节点的。

每个节点都有一个ParentID。Home (ID: 1)是根。

函数头应该类似于：

public ModuleDTO GetModuleTree(List<int> ids);

示例树如下所示：

• 1个家庭
  • 2个应用程序
  • 3教学
    • 4门课程
    • 5个房间
    • 6名教师

​

- 7 Research 
    - 8 Publications

​

- 9 Graduation

​

如果4被传递给函数，它将返回如下树：

• 1个家庭
  • 3教学
    • 4门课程

​

​

如果5和8被传递给函数，它将返回如下树：

• 1个家庭
  • 3教学
    • 5个房间

​

- 7 Research 
    - 8 Publications

​

​

如果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>();
    }
}

提前谢谢。

Answer 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);
            }
        }
    }
}

Answer 2

(我假设查找速度在这里不是很重要，或者树比较小)

首先，让我们考虑为单个输入找到答案。这里一种有用的方法是尝试一个深度优先型算法，一种递归算法。查看树中的每个节点，一旦找到它，就返回它。当您开始从递归返回时，您将继续“向上”树，并将所有节点返回到主节点。

然后，有几个ids的情况就变成了这样几次，并加入了所有的结果。

当然，可以对该算法进行一些改进，以及可以采取的其他方法，这取决于性能需求和更改数据结构的自由。但是，它们可能不像上述解决方案的实现那样简单和清晰。