使用尾递归的后序

Question

我找到这个链接，http://www.experts-exchange.com/Programming/ Algorithms/Q_25205171.html，它提出了一种进行后序尾递归的方法。但是，它使用 2 个堆栈，有没有办法只用一个堆栈来做到这一点。谢谢！

下面是从上面的链接粘贴的java代码：

public static final <T> void postorder(Tree<T> root) {
    Stack<Tree<T>> stack = new Stack<Tree<T>>();
    Stack<Tree<T>> traversal = new Stack<Tree<T>>();
    stack.push(root);
    while (!stack.isEmpty()) {
      Tree<T> node = stack.pop();
      if (node.right != null) 
        stack.push(node.right);
      }
      if (node.left != null) {
        stack.push(node.left);
      }
      traversal.push(node);
    }
    while (!traversal.isEmpty()) {
      System.out.println(traversal.pop().value.toString());
    }
  }

Answer 1

是的，但是代码的结构需要不同。递归算法的正确的基于堆栈的模拟应该将节点保留在堆栈上，直到完全遍历该节点及其子节点。堆栈应该包含一个类的实例，该类包含有关已遍历了多少个子级的信息，例如：（

public class StackElement<T> {
    public Tree<T> node;
    public int numTraversedChildren;
}

为了简单起见，使用公共字段）。每当您将一个节点压入堆栈时，都会压入一个引用该节点且 numTraversedChildren 为 0 的 StackElement。在循环的顶部，查看（不要弹出） ) 堆栈以查找顶部元素。当且仅当 numTraversedChildren == 2 时，您才知道该节点的所有子节点都已被遍历。在这种情况下，您可以处理（在您的情况下，打印）该节点，然后弹出它。否则，将节点保留在堆栈上，递增 numTraversedChildren，并推送其左子节点（如果 numTraversedChildren 的旧值为 0）或其右子节点（如果旧值） numTraversedChildren 的值为 1)。

请注意，采用这种方法时，while 循环和堆栈上的入栈/出栈操作实际上是在模拟函数调用：入栈是调用，出栈是返回，并且堆栈维护所有的操作。每个函数调用的参数和局部变量。堆栈顶部的元素始终代表当前正在执行的函数。