在自引用(父-子)层次树中查找所有后代。
在自引用(父-子)层次树中查找所有后代。
提问于 2016-05-25 15:20:09
这类似于问题(为给定的子LINQ (lambda表达式)在树层次结构中查找父级)。然而，我不需要找到所有的祖先，我需要找到所有的后代。
我正在修改雅库布的方法，但只设法使所有的后代都在一个分支中。
private IEnumerable<UserRole> FindAllChildrenRecursively(List<UserRole> allRoles, UserRole role)
{
var child = allRoles.FirstOrDefault(x => x.ParentId == role.Id);
if (child == null)
return Enumerable.Empty<UserRole>();
return new[] { child }.Concat(FindAllChildrenRecursively(allRoles, child));
}Stack Overflow用户
回答已采纳
发布于 2016-05-25 20:25:34
我正在修改雅库布的方法，但只设法在一个分支中得到所有的后代
这是因为这一行：
var child = allRoles.FirstOrDefault(x => x.ParentId == role.Id);虽然它可能适合于查找单亲父级，但不适合查找多个子级。
但是您不需要递归迭代器和allRoles列表上的多次迭代。您可以使用ToLookup扩展方法创建快速查找结构，然后执行如下迭代DFS：
private static IEnumerable<UserRole> FindAllChildren(List<UserRole> allRoles, UserRole role)
{
var childrenByParentId = allRoles.ToLookup(r => r.ParentId);
var stack = new Stack<IEnumerator<UserRole>>();
var e = childrenByParentId[role != null ? role.Id : (int?)null].GetEnumerator();
try
{
while (true)
{
while (e.MoveNext())
{
yield return e.Current;
stack.Push(e);
e = childrenByParentId[e.Current.Id].GetEnumerator();
}
if (stack.Count == 0) break;
e.Dispose();
e = stack.Pop();
}
}
finally
{
e.Dispose();
while (stack.Count > 0) stack.Pop().Dispose();
}
}一种更好的方法是(遵循干的原则)利用来自如何通过LINQ使树变平？的通用树助手方法
public static class TreeUtils
{
public static IEnumerable<T> Expand<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
{
var stack = new Stack<IEnumerator<T>>();
var e = source.GetEnumerator();
try
{
while (true)
{
while (e.MoveNext())
{
var item = e.Current;
yield return item;
var elements = elementSelector(item);
if (elements == null) continue;
stack.Push(e);
e = elements.GetEnumerator();
}
if (stack.Count == 0) break;
e.Dispose();
e = stack.Pop();
}
}
finally
{
e.Dispose();
while (stack.Count != 0) stack.Pop().Dispose();
}
}
}就像这样：
private static IEnumerable<UserRole> FindAllChildren(List<UserRole> allRoles, UserRole role)
{
var childrenByParentId = allRoles.ToLookup(r => r.ParentId);
return childrenByParentId[role != null ? role.Id : (int?)null].Expand(r => childrenByParentId[r.Id]);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/37441398
复制相关文章
相似问题
腾讯云开发者
