如何使用 LINQ Flatten() 展平一棵深树

Question

我有一个通用类型树类，如下所示：

public class TreeNode<T>
{
    private readonly T _data;
    private readonly TreeNode<T> _parent;
    private readonly List<TreeNode<T>> _children;
    private readonly int _level;

    public int Level
    { get { return _level; } }
    public int Count
    { get { return _children.Count; } }
    public bool IsRoot
    { get { return _parent == null; } }
    public bool IsLeaf
    { get { return _children.Count == 0; } }
    public T Data
    { get { return _data; } }
    public TreeNode<T> Parent
    { get { return _parent; } }

    public TreeNode(T data)
    {
        _data = data;
        _children = new List<TreeNode<T>>();
        _level = 0;
    }

    public TreeNode(T data, TreeNode<T> parent) : this(data)
    {
        _parent = parent;
        _level = _parent != null ? _parent.Level + 1 : 0;
    }

    public TreeNode<T> this[int key]
    {
        get { return _children[key]; }
    }

    public void AddChild(TreeNode<T> value)
    {
        _children.Add(value);
    }

    public TreeNode<T> GetChild(int key)
    {
        return _children[key];
    }

    public void Clear()
    {
        _children.Clear();
    }
}

我想在此类中创建一个函数来展平所有嵌套的子列表，无论树有多深。返回值将是 TreeNode 的列表。该函数可以在任何节点上使用，无论它是否是根节点。

我尝试使用 LINQ Flatten() 解决方案，但它似乎只返回第一级。如何使用（或不使用）LINQ 设计 TreeNode 类中的函数，以便无论节点是什么类型我总是可以返回这样的列表？

Answer 1

您可以创建枚举器函数来枚举节点的所有子节点。以下是如何操作的示例：

public IEnumerable<TreeNode<T>> EnumerateChildrenRecursive()
{
    foreach (var child in _children)
    {
        yield return child;

        foreach (var subItem in child.EnumerateChildrenRecursive())
        {
            yield return subItem;
        }
    }
}

转换为列表会很简单：

var list = root.EnumerateChildrenRecursive().ToList();

Answer 2

我不确定这个

Flatten()

方法是什么，它不是内置方法。

但是你需要遍历这棵树。我的典型方法是采用与 LINQ 相同的扩展方法：

public static IEnumerable<T> DepthFirst<T>(T self, Func<T, IEnumerable<T>> selector)
{
    var stack = new Stack<T>();
    stack.Push(self);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var child in selector(current))
        {
            stack.Push(child);
        }
    }
}

您需要在节点类上公开您的子级的 IEnumerable：

public class TreeNode<T>
{
   ...
   public IEnumerable<TreeNode<T>> Children => _children
}
...
var allNodes = myRootNode.DepthFirst(n => n.Children);

您可以通过将堆栈更改为队列来将迭代顺序更改为广度优先。

这要求树实际上是树而不是图。如果 TreeNode 将自身作为子节点，则返回的 IEnumerable 将无限长，并且您可能会遇到堆栈溢出。为了防止这种情况，您可以添加已访问节点的列表，以防止多次访问同一节点。