在具有多个嵌套子项的类/对象/列表中查找值/项-解网

问：

我有这个班级：

public class Division
{
    public int Id { get; set; }
    public string Naam { get; set; }
    public ICollection<Division> Children { get; set; }
}

填充对象/列表的示例：


Id  1
Name    "HQ"
Children    
   0    
   Id   200
   Name "HR"
   Children 
      0 
      Id    800
      Name  "Payrolls"
      Children  
         0  
         Id 1001
         Name   "Years"
         Children   
         1
         Id 1002
         Name   "Level"
         Children   
      1 
      Id    900
      Name  "Functions"
      Children  
         0  
         Id 2000
         Naam   "Grades"
         Children   
...

每个项目都可以有许多嵌套的“子项”。现在我想按 ID 查找项目，如何实现此目的？

我试图将结果放入列表中。lstDivision = Division.Children.ToList();

，然后通过以下方式查找项目：Division d = lstDivision.SelectMany(d => d.Children).Where(c => c.Id==2000).FirstOrDefault();

结果为 null。

C# LINQ 嵌套列表

如果你不想让两个数据结构始终保持最新，你也可以采用“缓存”方法，在字典中查找一个 ID，如果没有找到，则执行树搜索，然后写入字典并返回结果，这样下一个查询相同的 ID 会更快......如果它被删除，请记住从缓存中清除它。

答：

0赞 Fildor 11/29/2022 #1

朴素递归方法的一个例子是这样的：

// given: `Division` is a nullable reference type, probably a class
// I am refering to the `Division` class as given in question at the time of writing.

public Division FindDivisionByID( Division parent, int targetID )
{
    // Do we have the Node we were looking for already?
    // Yes: Return it.
    if( parent.Id == targetId ) return parent;

    // No: Process Children one by one
    foreach( var child in parent.Children )
    // Little assignment for OP: ^^ this does not take into account
    // that `parent.Children` could be null and will throw if it is.
    // You would want to fortify against that.
    {
        // If a descendant of this child or the child itself
        // was the one we are looking for, `childResult` will 
        // point to it. If not it will be null.
        var childResult = FindDivisionByID( child, targetID );
        // The requested Node was in this child's subtree?
        // Yes: Return it.
        if( childResult is not null ) return childResult;
        // No: Next child if there is one.
    }
    // Neither this Node nor any of its Children nor any of their 
    // descendants was the one we are looking for.
    return null;
}

我建议另外使用缓存来加快查找速度（因为它们经常发生）。

请注意，这只是实现目标的一种方法。有许多不同的方法可以遍历一棵树。有些更多，有些效率更低。深入研究这一点绝对是值得的，即使只是“听过一次”。

1赞 Jodrell 11/29/2022 #2

与 https://stackoverflow.com/a/73486312/659190 相比，

跟

public static IEnumerable<T> DepthFirstTraversal<T>(
    this T root,
    Func<T, IEnumerable<T>> branchSelector)
{
    ArgumentNullException.ThrowIfNull(branchSelector);
    
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        
        if (current == null)
        {
            continue;
        }
        
        foreach(var child in branchSelector(current))
        {
            stack.Push(child);
        }
    }
}

你可以做，

division
   .DepthFirstTraversal(d => d.Children)
   .Where(c => c.Id==2000)
   .FirstOrDefault();

上一个：从嵌套列表中检索数据

下一个：我在从 JSON 文件存储数组时遇到问题

在具有多个嵌套子项的类/对象/列表中查找值/项

Find value/item in class/object/list with multiple nested children

评论