将所有子元素添加到一个列表中 - 递归C#

Question

将所有子元素添加到一个列表中 - 递归C#

34

C# | .NET 4.5 | Entity Framework 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.ID的单个列表中。我在递归方面遇到了困难。希望有所帮助。

这是我到目前为止所做的，它是实体类的一个扩展，但我认为可以做得更好/更简单：

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 写了递归函数，将其放在存储过程中，然后将其导入到 Entity 中。相较于使用 Linq，这种方法看起来更加清晰和容易，而且根据评论来看，Linq 和 Entity 似乎不是最佳选择。感谢所有的帮助！

- Will

Entity Framework不包含任何涉及递归查询的内容。 - Aron

是的，我想要扩展这个功能，请看我的编辑。 - Will

我假设你想要一个基于Entity Framework的解决方案，而不是由Entity Framework延迟加载支持的Linq To Object解决方案...我查看了Entity Framework 6源代码，并想要添加该功能...但是微软将相关类设置为“internal”。BAS$%^DS - Aron

最终在SQL中采用递归，并引用存储过程。感谢帮助！ - Will

相关：如何通过LINQ展开树形结构？ - Theodor Zoulias

11个回答

16

这个可以解决问题：

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

- GreatAndPowerfulOz

4

如果你要给一个踩（downvote），请至少礼貌地说明原因。 - GreatAndPowerfulOz

3

这将只返回当前集合下面的子项。如果想在最终结果中包含这些子项，您需要合并源集合。 - Slicksim

@Slicksim 不是这样的，请再试一次。 - GreatAndPowerfulOz

1

因为这是一种低效的解决方案，所以被踩了。对于一个延迟枚举，调用Any，然后Concat，再调用SelectManyRecursive会导致多次枚举，进而多次调用selector lambda表达式。与其为树中的每个元素调用一次lambda表达式，不如为每个元素调用一次。 - Theodor Zoulias

10

我的模型中没有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)

- Mehdi Dehghani

太好了！我有与您的模型完全相同的设置（ID（PK），Parent ID和Child ID）。这种方法完美地运作，可以获取父ID的完整层次结构。我知道肯定有一种通过递归或其他方式来实现它的方法，但这是一个纯Linq示例，也可以与EF一起使用！ - NiallMitch14

这个答案中的模型与您原来的问题不同。 - Nikhil Agrawal

@NikhilAgrawal 是的，我已经在我的回答中提到了。 - Mehdi Dehghani

10

尝试使用这个扩展方法：

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

- Jonathas Costa

代码的编写方式，您不需要使用 R 泛型参数。 - GreatAndPowerfulOz

1

因为多次调用“递归”lambda表达式和多次评估生成的可枚举对象而被踩。 - Theodor Zoulias

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

参考文献：https://dev59.com/qGIk5IYBdhLWcg3we-H5#21054096

注意：找不到另一个参考文献了，但是在 Stack Overflow 上有人发布了一篇答案，我从中复制了一些代码。

- user1477388

代码的编写方式，您不需要使用 R 泛型参数。 - GreatAndPowerfulOz

我不理解你如何调用扩展方法child.Flatten()，因为child不是IEnumerable<T>而只是T。 - Carteră Veaceslav

在这个例子中，Children将始终是一个列表；它可能是空的。如果您的代码工作方式不同，则可以检查类型以查看它是否为IEnumerable，即return typeof(IEnumerable).IsAssignableFrom(type); 参考 https://dev59.com/Ul4b5IYBdhLWcg3wxEOm#28703732 - user1477388

6

@NikhilAgrawal 的答案没有像 @electricalbah 指出的那样递归地获取所有子孙节点。

我想念 @EricLippert 在 Code Review 上给出的答案。

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`可以看出，如果您使用该解决方案，甚至无法获取父 Id。

请参考下图：

- Ogglas

这里进行了空值检查：

    var childrenOfCurrent = children(current);
    if (childrenOfCurrent is not null)
    {
      // 如果您不关心维护子级顺序，则删除 Reverse。
      foreach (var child in childrenOfCurrent.Reverse())
        stack.Push(child);
    }
    yield return current;

- nvbnvb

5

Entity Framework目前不支持递归，因此您可以选择以下方式：

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

唯一真正的选择是避免使用LINQ表达式进行查询，而是采用标准SQL。

无论您使用代码优先还是其他方式，Entity Framework都可以很好地支持此情况。

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

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

扁平化后的列表存储在变量query中。

- Martin Booth

这就是我最终做的。感谢你的帮助。 - Will

2

创建列表以递归方式添加所有子项

公共静态列表：

public static List list = new List();

递归函数

 static  void GetChild(int id) // Pass parent Id
                {

                    using (var ctx =  new CodingPracticeDataSourceEntities())
                    {
                        if (ctx.Trees.Any(x => x.ParentId == id))
                        {
                            var childList = ctx.Trees.Where(x => x.ParentId == id).ToList();
                            list.AddRange(childList);
                            foreach (var item in childList)
                            {
                                GetChild(item.Id);
                            }

                        }

                    }
                }

示例模型

 public partial class Tree
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public Nullable<int> ParentId { get; set; }
    }

- Muhammed Afsal

1

对于需要通用解决方案的人：

/// <summary>
/// Recursively enumerate all children, grandchildren etc... in a 1-dimentional IEnumerable
/// </summary>
/// <typeparam name="TModel">The type of the model</typeparam>
/// <param name="root">The root from which to enumerate children</param>
/// <param name="childSelector">The selector on how to select the children of the root.</param>
/// <returns>A 1-dimentional IEnumerable of all it's children, grandchildren etc.. recursively.</returns>
public static IEnumerable<TModel> EnumerateChildren<TModel>(TModel root, Func<TModel, IEnumerable<TModel>> childSelector)
{
    var children = childSelector.Invoke(root);
    if (children == null)
    {
        yield break;
    }

    foreach (var child in children)
    {
        yield return child;

        foreach (var grandChild in EnumerateChildren(child, childSelector))
        {
            yield return grandChild;
        }
    }
}

用法：

var location = GetLocation(); // 获取根目录。

var children = EnumerateChildren(location, l => l.Children);

- Joost00719

0

假设您的DB上下文中有一个名为Locations的DbSet<Location>，那么这将解决您的问题：“我正在寻找一些简单的方法...以获取所有'Location'及其子项到一个包含Location.ID的单个列表中”。看起来我可能漏掉了什么，请在需要时进行澄清。

dbContext.Locations.ToList()
// IDs only would be dbContext.Locations.Select( l => l.ID ).ToList()

- Moho

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nikhil Agrawal · Accepted Answer

你可以使用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，可以这样做：

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