c# - 树分支算法

Question

我正在尝试创建一个函数，其中输入是 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>();
    }
}

提前致谢。

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

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

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

然后，具有多个 id 的情况就变成了多次执行此操作，并加入所有结果。

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