在自引用（父子）层次树中查找所有后代

corix010 发表于 Dev

corix010

这类似于问题（在树层次结构中为给定的子级LINQ（lambda表达式）查找父级）。但是，除了找到所有祖先之外，我还需要找到所有后代。

我正在修改Yacoub的方法，但只设法将所有后代都放在一个分支中。

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

伊万·斯托夫（Ivan Stoev）

我正在修改Yacoub的方法，但只设法将所有后代都放在一个分支中

这是因为此行：

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

更好的方法是（遵循DRY原理）利用“如何通过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]);
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。