如何使树节点的值成为IEnumerable? [英] How to make an IEnumerable of values of tree nodes?

问题描述

请考虑以下课程:

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;中.

Each value is passed O(h) times, where h is the height of the tree. First, in yield return value; statement, then in yield return i; of each parent node.

因此，sub_values使用O(nh)时间复杂度返回n值.

So, sub_values returns n values using O(nh) time complexity.

我可以用一种方法代替它，该方法接受对整数列表的引用，而不是返回值，而是将它们添加到此列表中，但不再懒惰了.

I can replace it with a method, which accepts a reference to a list of integers and instead of returning values, adds them to this list, but it won't be lazy anymore.

我可以在O(n)中返回n值并保持惰性吗?

Can I return n values in O(n) and maintain laziness?

推荐答案

它与 DRY

It's very similar to Function which will return particular node from tree structure 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类中定义一些有用的帮助器

Now let define some useful helpers inside your 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方法进行过滤，投影等.例如，有问题的方法就是这样

Notice the Traverse method - it provides the laziness you are asking for. Now you can use the usual LINQ methods for filtering, projections etc. For instance, the method in question becomes like this

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

这篇关于如何使树节点的值成为IEnumerable?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！