遍历任意大的二叉树

Question

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

我可以很容易地编写一个递归的,但是对于我的生活来说,如果树是任意大的,就不能找出不会溢出堆栈的东西.

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

public IEnumerable<T> Values()

方法.

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

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

Answer 1

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

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

}

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