如何使树节点的值成为 IEnumerable？

Question

考虑以下 class：

class TreeNode
{
    int value;
    public TreeNode l, r;
    public TreeNode(int value)
    {
        this.value = value;
    }
    public IEnumerable<int> sub_values()
    {
        if (l != null)
            foreach (int i in l.sub_values())
                yield return i;
        if (r != null)
            foreach (int i in r.sub_values())
                yield return i;
        yield return value;
    }
}

每个值被传递 O(h) 次，其中 h 是树的高度。首先，在yield return value;语句中，然后在每个父节点的yield return i;中。

因此，sub_values returns n 个值使用 O(nh) 时间复杂度。

我可以用一个方法替换它，该方法接受对整数列表的引用，而不是 returning 值，将它们添加到这个列表中，但它不会再懒惰了。

我可以 return n 价值观 O(n) 并保持懒惰吗？

Answer 1

与 and other SO posts regarding recursive iterators. All they involve using an explicit stack or queue. Here is a generic solution for any type of tree. Let first define a reusable function in some common place, so the next time DRY

非常相似

public static class TreeHelper
{
    public static IEnumerable<T> Traverse<T>(T node, Func<T, IEnumerable<T>> childrenSelector, bool preOrder = true)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = Enumerable.Repeat(node, 1).GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    var children = childrenSelector(item);
                    if (children == null)
                        yield return item;
                    else
                    {
                        if (preOrder) yield return item;
                        stack.Push(e);
                        e = children.GetEnumerator();
                    }
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
                if (!preOrder) yield return e.Current;
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

现在让我们在 TreeNode class

中定义一些有用的助手

public bool AnyChildren() { return l != null || r != null; }
public IEnumerable<TreeNode> Children
{
    get
    {
        if (l != null) yield return l;
        if (r != null) yield return r;
    }
}
public IEnumerable<TreeNode> Traverse(bool preOrder = false)
{
    return TreeHelper.Traverse(this, node => node.AnyChildren() ? node.Children : null, preOrder);
}

注意 Traverse 方法 - 它提供了您所要求的惰性。现在您可以使用常用的 LINQ 方法进行过滤、投影等。例如，有问题的方法变成这样

public IEnumerable<int> sub_values()
{
    return Traverse().Select(node => node.value);
}

如何使树节点的值成为 IEnumerable？

How to make an IEnumerable of values of tree nodes?

c#

ienumerable

lazy-evaluation