查找自引用(父子)分层树所有后代 [英] Find all descendants in self-referencing (parent-child) hierarchical tree
问题描述
这是类似的问题(的查找父母在树层次对于一个给定的孩子LINQ(lambda表达式))。然而,而不是找出所有的祖先,我需要找到所有后代。
我修改雅各布的方法,但只走完所有的后代在一个分支。
私人的IEnumerable<&UserRole的GT; FindAllChildrenRecursively(列表<&UserRole的GT; allRoles,UserRole的角色)
{
VAR孩子= allRoles.FirstOrDefault(X => x.ParentId == role.Id);
如果(孩子== NULL)
返回Enumerable.Empty<&UserRole的GT;();
返回新的[] {}子.Concat(FindAllChildrenRecursively(allRoles,儿童));
}
我修改雅各布的方法,但只走完所有的后代在一个分支
块引用>
这是因为该行的:
VAR孩子= allRoles.FirstOrDefault(X => x.ParentId == role.Id);
虽然它可能是适当的查找单母公司,它不是适合寻找的多个孩子
但你并不需要递归迭代器和多次重复过
allRoles
列表。可以使用的ToLookup
扩展方法,然后执行迭代的 DFS 是这样的:私有静态的IEnumerable<&UserRole的GT; FindAllChildren(列表<&UserRole的GT; allRoles,UserRole的角色)
{
VAR childrenByParentId = allRoles.ToLookup(R = GT; r.ParentId);
变种堆栈=新的堆栈< IEnumerator的<&UserRole的GT;>();
变种E = childrenByParentId [作用!= NULL? role.Id:(?INT)空] .GetEnumerator();
试
{
,而(真)
{
,而(e.MoveNext())
{
收益率的回报e.Current;
stack.Push(E);
E = childrenByParentId [e.Current.Id] .GetEnumerator();
}
如果(stack.Count == 0)打破;
e.Dispose();
E = stack.Pop();
}
}
终于
{
e.Dispose();
而(stack.Count大于0)。stack.Pop()配置();
}
}
这是更好的方法是(继<一个HREF =https://en.wikipedia.org/wiki/Don%27t_repeat_yourself相对=nofollow> DRY原则),以利用来自的如何通过LINQ扁平化树:
公共静态类TreeUtils
{
公共静态的IEnumerable< T>展开< T>(
本的IEnumerable< T>源,Func键< T,IEnumerable的< T>> elementSelector)
{
变种堆栈=新的堆栈< IEnumerator的< T>>( );
变种E = source.GetEnumerator();
试
{
,而(真)
{
,而(e.MoveNext())
{
VAR项目= e.Current ;
收益回报的项目;
VAR元素= elementSelector(项目);
如果(元素== NULL)继续;
stack.Push(E);
E = elements.GetEnumerator();
}
如果(stack.Count == 0)打破;
e.Dispose();
E = stack.Pop();
}
}
终于
{
e.Dispose();
,而(stack.Count!= 0)stack.Pop()的Dispose()。
}
}
}
是这样的:
私有静态的IEnumerable<&UserRole的GT; FindAllChildren(列表<&UserRole的GT; allRoles,UserRole的角色)
{
VAR childrenByParentId = allRoles.ToLookup(R = GT; r.ParentId);
返回childrenByParentId [作用!= NULL? role.Id:(?INT)空] .Expand(R = GT; childrenByParentId [r.Id]);
}
This is similar to the question (Finding parents in a tree hierarchy for a given child LINQ (lambda expression)). However, instead of finding all ancestors, I need to find all descendants.
I am modifying Yacoub's method but only managed to get all descendants in one branch.
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)); }
解决方案I am modifying Yacoub's method but only managed to get all descendants in one branch
This is because of this line:
var child = allRoles.FirstOrDefault(x => x.ParentId == role.Id);
While it might have been appropriate for finding a single parent, it's not appropriate for finding multiple children.
But you don't need recursive iterators and multiple iterations over the
allRoles
list. You can create a fast lookup structure usingToLookup
extension method and then perform iterative DFS like this: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(); } }
An even better approach would be (following the DRY principle) to utilize the generic tree helper method from How to flatten tree via 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(); } } }
like this:
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]); }
这篇关于查找自引用(父子)分层树所有后代的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!