遍历任意大的二叉树

我一直在寻找解决方案。 C#,.NET 4.0,VS2010

我可以很容易地写一个递归的,但是如果树是任意大的话,我不能为我的生活弄清楚不会溢出堆栈的东西。

这是一个二叉树问题,我正在尝试写一个

public IEnumerable Values() 

方法。

以下是您感兴趣的完整代码: http : //pastebin.com/xr2f3y7g

显然,目前在那里的版本不起作用。 我可能应该提一下,我是C#的新手,从C ++过渡。

这是一个使用显式堆栈的inorder遍历方法。 堆栈是在堆上创建的,因此它可以比处理器使用的堆栈大得多。

 public IEnumerable Values() { Stack stack = new Stack(); Node current = this.root; while(current != null) { while(current.leftChild != null) { stack.Push(current); current = current.leftChild; } yield return current.data; while(current.rightChild == null && stack.Count > 0) { current = stack.Pop(); yield return current.data; } current = current.rightChild; } } 

如果您不能使用堆栈并且您的节点碰巧有父指针,您可以尝试此问题的解决方案

假设树几乎是平衡的,它的最大深度是log2(n),所以你需要一个巨大的树来溢出堆栈。

您可以将任何递归算法转换为迭代算法,但在这种情况下,它可能需要后向指针或显式堆栈,这两者看起来都很昂贵。

话虽如此,在.NET中递归通常不是很大,因为在终止条件之后堆栈被解除之前,调用方法实例中的任何局部变量都不能被GC。 我不知道JIT是否会自动优化尾端递归以使其迭代,但这会有所帮助。