Geek asks and answers

Postobrazovanie using tail recursion

I find this link, http://www.experts-exchange.com/Programming/Algorithms/Q_25205171.html , which offers a way to do tail recursion after ordering. however, it uses 2 stacks, is there any way to do this with only one stack. thank!

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());
    }
  }
0
source share
1 answer

Yes, but the code needs to be structured differently. Correct stack-based recursive algorithm modeling should keep the node on the stack until the node and its children are fully traversed. The stack should contain instances of a class that contains information about how many children were passed, for example:

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

( ). , node , StackElement, node numTraversedChildren 0. ( ) , . numTraversedChildren == 2, , node . ( , ), node, . node , numTraversedChildren ( numTraversedChildren 0), ( numTraversedChildren 1).

, while push/pop : push - , pop - , . .

+1

More articles:


All Articles