我正在尝试创建一个函数,其中输入是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 GraduationIf 4 is passed to the function, it would return a tree like this:
1 Home 3 Teaching 4 CoursesIf 5 and 8 are passed to the function, it would return a tree like this:
1 Home 3 Teaching 5 Rooms 7 Research 8 PublicationsIf 3 is passed to the function, it would return a tree like this:
1 Home 3 TeachingMy 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); } } } }更多推荐
发布评论