c# - Twig 算法

Question

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

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

函数头应该是这样的:

public ModuleDTO GetModuleTree(List<int> ids);

示例树如下:

• 1 家
  • 2 份申请
  • 3 教学
    • 4 门类(class)
    • 5 个房间
    • 6 名教师
  • 7 研究
    • 8 篇文章
  • 9 毕业

如果将 4 传递给函数，它将返回这样的树:

• 1 家
  • 3 教学
    • 4 门类(class)

如果将 5 和 8 传递给函数，它将返回这样的树:

• 1 家
  • 3 教学
    • 5 个房间
  • 7 研究
    • 8 篇文章

如果将 3 传递给函数，它将返回这样的树:

• 1 家
  • 3 教学

我的类(class)如下:

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

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

首先让我们考虑为单个输入寻找答案。这里可用的方法是尝试 depth-first type algorithm ，一种递归算法。查看树中的每个节点，找到后立即返回。一旦开始从递归返回，您将继续“向上”树，并将沿途的所有节点返回到主节点。

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

根据性能需求和更改数据结构的自由度，当然可以对该算法以及可以采用的其他方法进行多项改进。不过，它们可能不像上述解决方案的实现那样简单明了。