树分支算法(Tree branch algorithm)

树分支算法(Tree branch algorithm)

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

提前致谢。

I'm trying to make a function where the input is a list of IDs and output is a tree with the nodes based on their ID and all parent nodes.

Each node has a ParentID. Home (ID: 1) is the root.

The function header would be something like:

public ModuleDTO GetModuleTree(List<int> ids);

Sample tree would be the following:

1 Home 2 Applications 3 Teaching 4 Courses 5 Rooms 6 Teachers 7 Research 8 Publications 9 Graduation

If 4 is passed to the function, it would return a tree like this:

1 Home 3 Teaching 4 Courses

If 5 and 8 are passed to the function, it would return a tree like this:

1 Home 3 Teaching 5 Rooms 7 Research 8 Publications

If 3 is passed to the function, it would return a tree like this:

1 Home 3 Teaching

My class is the following:

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

Thanks in advance.

最满意答案

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

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

有几个id的情况就这样做了几次，并加入了所有的结果。

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

I solved it with this:

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