遍历任意大的二叉树中序 [英] Traversing arbitrarily large binary tree inorder

问题描述

我停留在寻找解决办法。 C＃，.NET 4.0，VS2010

I'm stuck at finding a solution. C#, .NET 4.0, VS2010

我可以随便写一个递归的，但不能为我的生活搞的东西，不会溢出的堆栈如果树是任意大的。

I can easily write a recursive one, but can't for the life of me figure out something that won't overflow the stack if the tree is arbitrarily large.

这是一个二叉树的问题，我试图写一个

This is a binary tree question, and i am trying to write a

public IEnumerable<T> Values()

方法。

下面是完整的code如果你有兴趣： http://pastebin.com/xr2f3y7g

Here is the full code in case you are interested: http://pastebin.com/xr2f3y7g

显然，目前在那里的版本无法正常工作。也许我应该提到，我在C＃中的新手，从C ++转变。

Obviously, the version currently in there doesn't work. I probably should mention that I am a newbie in C#, transitioning from C++.

推荐答案

下面是一个方法序遍历，使用明确的堆栈。堆栈是在堆上创建的，所以它可以大得多，比堆栈中的处理器使用。

Here is a method for inorder traversal, that uses explicit stack. The stack is created on the heap, so it can be much larger, than the stack the processor uses.

public IEnumerable<T> Values()
{
    Stack<Node> stack = new Stack<Node>();
    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;
    }

}

如果您不能使用堆栈和你的节点恰好有父指针，你可以尝试从<一个解决方案href="http://stackoverflow.com/questions/3435425/modified-depth-first-traversal-of-tree/3435648#3435648">this问题

If you can't use a stack and your nodes happen to have parent pointers, you can try solutions from this question

这篇关于遍历任意大的二叉树中序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！