在自引用（親子）分層樹中查找所有後代

Question

這與問題（Finding parents in a tree hierarchy for a given child LINQ (lambda expression)）類似。然而，我不需要找到所有的祖先，我需要找到所有的後代。

我正在修改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)); 
} 

Answer 1

我修改雅各布的方法，但只走完所有的後代在一個分支

這是因爲該行：

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原理）從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(); 
     } 
    } 
} 

這樣的：

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