如何使树节点的值的一个IEnumerable？ [英] How to make a 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;
    }
}

每个值传递 0 （H）次，其中 ^ h 是树的高度。首先，在收益率的返回值; 语句，然后在收益回报我; 每个父节点的

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 使用返回 N 值 O（NH）时间复杂度。

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.

我可以退掉 N 值在 O（N）并保持懒惰？

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

推荐答案

这是非常相似来功能将从树形结构返回特定的节点以及有关递归迭代器等SO职位。所有它们涉及到使用显式堆栈或队列。这里为任何类型树的通用的解决方案。让先定义一些共同的地方可重复使用的功能，所以下一次干

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();
        }
    }
}

现在让我们定义一些有用的工具你的树节点类

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);
}

注意导线方法 - 它提供了你所要求的懒惰。现在你可以使用过滤通常的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屋！