如何最好地遍历Children of Children；s孩子们到了未知的深度

本文关键字：Children 未知 深度 孩子们 何最好 遍历 of | 更新日期: 2023-09-27 18:27:56

想象一个具有以下属性的对象：

        class TestObject
        {
            public string Name { get; set; }
            public Collection<TestObject> Children { get; set; }
        }

现在以锯齿状的方式初始化一些：

var person1 = new TestObject(){ 
                          Name = "Joe", 
                          Children = new Collection<TestObject>(){ childCollection1 }; 
                              };
var person2 = new TestObject(){ 
                          Name = "Mary", 
                          Children = new Collection<TestObject>(){ childCollection2 }; 
                              };

乔的孩子收藏只有一个层次，但玛丽的孩子有孩子，他们也有孩子。

我曾尝试使用SelectMany，但没有成功。

// Works
var joe = person1.Children.SelectMany(c => c.Children).Concat(person1.Children);
// Does not work - only returns 1 level deep
var mary = person2.Children.SelectMany(c => c.Children).Concat(person2.Children);

检索包含每个孩子的结果到未知深度的最佳方法是什么？

如何最好地遍历Children of Children；s孩子们到了未知的深度

您可以编写这样的通用遍历方法：

public static IEnumerable<T> Traverse<T>(T root, 
    Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(root);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next))
            stack.Push(child);
    }
}

这是一个通用模型，对遍历树非常有用。请注意，这将进行深度优先搜索。如果你想进行呼吸优先搜索，你可以使用Queue<T>而不是Stack<T>。

Helper方法

public static IEnumerable<T> Traversal<T>(
    T root,
    Func<T, IEnumerable<T>> getChildren)
{
    if (root == null)
    {
        yield break;
    }
    yield return root;
    var children = getChildren(root);
    if (children == null)
    {
        yield break;
    }
    foreach (var child in children)
    {
        foreach (var node in Traversal(child, getChildren))
        {
            yield return node;
        }
    }
}
//Or if you don't need all those null checks, here's a more compact version.
public static IEnumerable<T> Traversal<T>(
    T root,
    Func<T, IEnumerable<T>> getChildren)
{
    yield return root;
    foreach (var child in getChildren(root))
        foreach (var node in Traversal(child, getChildren))
            yield return node;
}
//If you like a LINQ/functional style better, this is also equivalent.
public static IEnumerable<T> Traversal<T>(
    T root,
    Func<T, IEnumerable<T>> getChildren)
{
    return new T[] { root }
        .Concat(getChildren(root)
            .SelectMany(child => Traversal(child, getChildren)));
}

用法

var everybody = Traversal(person, x => x.Children);

评论

您可以很容易地修改Traversal方法，使其行为完全符合您的要求。例如，如果只需要叶节点，那么当children为null或为空时，应该只使用yield return root;。

性能问题

如果性能有任何问题，请考虑上面的LINQ/函数实现，或者看看Servy的答案，其中任何一个都应该比使用yield ...的版本更高效。

相关文章：