查找自引用（父子）分层树所有后代 [英] 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 using ToLookup 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屋！