让所有孩子到一个列表 - 递归C#

Question

C#| .NET 4.5 | 实体框架5

我在Entity Framework中有一个类如下所示:

public class Location
{
   public long ID {get;set;}
   public long ParentID {get;set;}
   public List<Location> Children {get;set;}
}

ID是位置的标识符,ParentID将其链接到父级,Children包含父级位置的所有子级位置.我正在寻找一些简单的方法,可能递归地将所有"Location"和他们的孩子放到一个包含Location.ID的List中.我在递归地概念化这个问题时遇到了麻烦.任何帮助表示赞赏.

这是我到目前为止,它是实体类的扩展,但我相信它可以做得更好/更简单:

public List<Location> GetAllDescendants()
{
    List<Location> returnList = new List<Location>();
    List<Location> result = new List<Location>();
    result.AddRange(GetAllDescendants(this, returnList));
    return result;
}

public List<Location> GetAllDescendants(Location oID, ICollection<Location> list)
{
    list.Add(oID);
    foreach (Location o in oID.Children)
    {
            if (o.ID != oID.ID)
                    GetAllDescendants(o, list);
    }
    return list.ToList();
}

更新

我最终在SQL中编写了递归,将其抛入SP,然后将其拉入实体.看起来更干净,比使用Linq更容易,并且根据评论判断Linq和Entity似乎不是最好的路线.感谢您的帮助!

Answer 1

你可以做SelectMany

List<Location> result = myLocationList.SelectMany(x => x.Children).ToList();

您可以在where条件中使用某些选择性结果

List<Location> result = myLocationList.Where(y => y.ParentID == someValue)
                                      .SelectMany(x => x.Children).ToList();

如果您只需要Id's of Children,那么您可以这样做

List<long> idResult = myLocationList.SelectMany(x => x.Children)
                                    .SelectMany(x => x.ID).ToList();

Answer 2

试试这个扩展方法:

public static IEnumerable<T> Flatten<T, R>(this IEnumerable<T> source, Func<T, R> recursion) where R : IEnumerable<T>
{
    return source.SelectMany(x => (recursion(x) != null && recursion(x).Any()) ? recursion(x).Flatten(recursion) : null)
                 .Where(x => x != null);
}

你可以像这样使用它:

locationList.Flatten(x => x.Children).Select(x => x.ID);

Answer 3

这样就可以了:

class Extensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        var result = source.SelectMany(selector);
        if (!result.Any())
        {
            return result;
        }
        return result.Concat(result.SelectManyRecursive(selector));
    }
}

像这样使用它:

List<Location> locations = new List<Location>();
//
// your code here to get locations
//
List<string> IDs = locations.SelectManyRecursive(l => l.Children).Select(l => l.ID).ToList();

Answer 4

我的Children模型中没有道具，所以Nikhil Agrawal的答案对我不起作用，所以这是我的解决方案。

使用以下型号：

public class Foo
{
    public int Id { get; set; }
    public int? ParentId { get; set; }  
    // other props
}

您可以使用以下方法获取一项的子项：

List<Foo> GetChildren(List<Foo> foos, int id)
{
    return foos
        .Where(x => x.ParentId == id)
        .Union(foos.Where(x => x.ParentId == id)
            .SelectMany(y => GetChildren(foos, y.Id))
        ).ToList();
}

例如。

List<Foo> foos = new List<Foo>();

foos.Add(new Foo { Id = 1 });
foos.Add(new Foo { Id = 2, ParentId = 1 });
foos.Add(new Foo { Id = 3, ParentId = 2 });
foos.Add(new Foo { Id = 4 });

GetChild(foos, 1).Dump(); // will give you 2 and 3 (ids)

Answer 5

正如 @electricalbah 指出的那样，@NikhilAgrawal 接受的答案不会递归地获得所有子代和孙子。

我确实怀念@EricLippert 在代码审查中给出的答案。

https://codereview.stackexchange.com/a/5661/96658

static IEnumerable<T> DepthFirstTreeTraversal<T>(T root, Func<T, IEnumerable<T>> children)      
{
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        // If you don't care about maintaining child order then remove the Reverse.
        foreach(var child in children(current).Reverse())
            stack.Push(child);
        yield return current;
    }
}

像这样调用：

static List<Location> AllChildren(Location start)
{
    return DepthFirstTreeTraversal(start, c=>c.Children).ToList();
}

我用下面的例子做了一个例子SelectMany。正如您所看到的，Immediate Window如果您使用该解决方案，您甚至不会获得 Parent Id。

Answer 6

实体框架当前不支持递归，因此您可以

• 像您所做的那样依赖延迟加载子集合（注意 N+1 问题）
• 查询任意深度的对象（这将是一个丑陋的查询，尽管您可以使用 System.Linq.Expressions 生成它）

唯一真正的选择是避免使用 LINQ 来表达查询，而是诉诸标准 SQL。

无论您是否首先使用代码，实体框架都很好地支持这种情况。

对于代码优先，请考虑以下内容

var results = this.db.Database.SqlQuery<ResultType>(rawSqlQuery)

对于模型优先，请考虑使用定义查询，我认为这是一个不错的选择，因为它允许进一步组合或存储过程。

要递归取回数据，您需要了解递归 CTE，假设您使用的是 SQL Server，并且它是 2005+ 版本

编辑：

这是任意深度的递归查询的代码。我把这些放在一起只是为了好玩，我怀疑它会非常有效！

var maxDepth = 5;

var query = context.Locations.Where(o => o.ID == 1);
var nextLevelQuery = query;

for (var i = 0; i < maxDepth; i++)
{
    nextLevelQuery = nextLevelQuery.SelectMany(o => o.Children);
    query = query.Concat(nextLevelQuery);
}

扁平列表位于变量查询中

Answer 7

我想贡献自己的解决方案，该解决方案已从以下参考资料中进行了修改：

public static IEnumerable<T> Flatten<T, R>(this IEnumerable<T> source, Func<T, R> recursion) where R : IEnumerable<T>
{
    var flattened = source.ToList();

    var children = source.Select(recursion);

    if (children != null)
    {
        foreach (var child in children)
        {
            flattened.AddRange(child.Flatten(recursion));
        }
    }

    return flattened;
}

例：

var n = new List<FamilyMember>()
{
    new FamilyMember { Name = "Dominic", Children = new List<FamilyMember>() 
        {
            new FamilyMember { Name = "Brittany", Children = new List<FamilyMember>() }
        }
    }
}.Flatten(x => x.Children).Select(x => x.Name);

输出：

• 多米尼克
• 布列塔尼

类：

public class FamilyMember {
    public string Name {get; set;}
    public List<FamilyMember> Children { get; set;}
}

参考 /sf/answers/1473786751/

注意：找不到其他参考，但是SO上的其他人发布了一个答案，我从中复制了一些代码。