后序使用尾递归 [英] postorder using tail recursion

问题描述

我觉得这个环节， http://www.experts-exchange.com /Programming/Algorithms/Q_25205171.html ，这表明一种方法做后序尾递归。但是，它使用2栈，是有办法，只有一个堆做到这一点。谢谢！

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

 公共静态最终＆LT; T＆GT;无效后序（树＆LT; T＆GT;根）{
    堆叠＆LT;树＆LT; T＆GT;＆GT;堆栈=新的堆栈＆LT;树＆LT; T＆GT;＆GT;（）;
    堆叠＆LT;树＆LT; T＆GT;＆GT;遍历=新的堆栈＆LT;树＆LT; T＆GT;＆GT;（）;
    stack.push（根）;
    而（！stack.isEmpty（））{
      树＆LT; T＆GT;节点= stack.pop（）;
      如果（node.right！= NULL）
        stack.push（node.right）;
      }
      如果（node.left！= NULL）{
        stack.push（node.left）;
      }
      traversal.push（节点）;
    }
    而（！traversal.isEmpty（））{
      的System.out.println（traversal.pop（）value.toString（））;
    }
  }
 

解决方案

是的，但code需要进行结构不同。递归算法的正确栈为基础的模拟应的继续的堆栈上的一个节点，直到节点及其子节点已经完全走过。栈应该包含包含有多少孩子已经走过信息的类的实例，说：

 公共类StackElement＆LT; T＆GT; {
    公共树＆LT; T＆GT;节点;
    公众诠释numTraversedChildren;
}
 

（使用公共字段为简单起见）。当你把一个节点压入堆栈，推 StackElement 是指节点，其中 numTraversedChildren 为0。循环的顶部，偷看（不弹出）堆栈找到顶部元件。当且仅当 numTraversedChildren == 2 ，你知道这个节点的所有子已经走过。在这种情况下，您可以处理（在你的情况下，打印）的节点，然后弹出它。否则，保持堆栈，增量 numTraversedChildren 上的节点，并推动无论是它的左子（如 numTraversedChildren 为0）或它的右子（如 numTraversedChildren 的原值为1）。

请注意，当这个方法之后，在，而循环，并在堆栈上推/弹出操作，有效地模拟函数调用：推是一个电话，一个弹出窗口是一个返回，并且堆栈维护所有参数和局部变量对每个函数调用。在堆栈的顶部的元件总是重新presents当前正在执行的功能。

i find this link, http://www.experts-exchange.com/Programming/Algorithms/Q_25205171.html, which suggests a way to do postorder tail recursion. however, it uses 2 stacks, is there a way to do this with only one stack. thanks!

below is the java code pasted from the link above:

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

解决方案

Yes, but the code needs to be structured differently. A proper stack-based simulation of a recursive algorithm should keep a node on the stack until the node and its children have been completely traversed. The stack should contain instances of a class that contains information about how many children have been traversed, say:

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

(using public fields for simplicity). Whenever you push a node onto the stack, push a StackElement that refers to that node and where numTraversedChildren is 0. In the top of the loop, peek (don't pop) the stack to find the top element. If and only if numTraversedChildren == 2, you know that all children of this node have been traversed. In that case, you can process (in your case, print) that node and then pop it. Otherwise, keep the node on the stack, increment numTraversedChildren, and push either its left child (if the old value of numTraversedChildren was 0) or its right child (if the old value of numTraversedChildren was 1).

Note that when this approach is followed, the while loop and the push/pop operations on the stack are effectively simulating function calls: a push is a call, a pop is a return, and the stack maintains all parameters and local variables for each function invocation. The element at the top of the stack always represents the function that is currently executing.

这篇关于后序使用尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！