如何不使用递归遍历树？

Question

我有一个非常大的内存节点树，需要遍历树。将每个子节点的返回值传递给其父节点。必须这样做，直到所有节点的数据泡都到达根节点为止。

遍历就像这样工作。

private Data Execute(Node pNode)
{
    Data[] values = new Data[pNode.Children.Count];
    for(int i=0; i < pNode.Children.Count; i++)
    {
        values[i] = Execute(pNode.Children[i]);  // recursive
    }
    return pNode.Process(values);
}

public void Start(Node pRoot)
{
    Data result = Execute(pRoot);
}

这很好，但我担心调用堆栈限制了节点树的大小。

如何重写代码以避免对Execute进行递归调用？

Answer 1

下面是一个不使用递归的通用树遍历实现：

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

在您的情况下，您可以这样称呼它：

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

首先使用Queue而不是Stack进行呼吸搜索，而不是深度优先搜索。使用PriorityQueue进行最好的第一次搜索。

Answer 2

如果您事先对树的深度有了估计，也许您的情况下调整堆栈大小就足够了？在自2.0版本以来的C#中，无论何时启动新线程，这都是可能的，请参见此处：

http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx

这样，您就可以保留递归代码，而不必实现更复杂的东西。当然，用您自己的堆栈创建一个非递归解决方案可能会增加时间和内存效率，但我确信代码不会像现在这样简单。

Answer 3

如果不使用递归，就不能以树的形式遍历数据结构--如果不使用语言提供的堆栈框架和函数调用，则基本上必须编写自己的堆栈和函数调用，而且不太可能以比程序运行的机器上的编译器编写人员更高效的方式在语言中编程。

因此，避免因担心陷入资源限制而进行递归通常是错误的。当然，过早的资源优化总是被误导的，但在这种情况下，即使您测量和确认内存使用情况是瓶颈，您也可能无法在不降到编译器编写器级别的情况下改进它。