Postorder с использованием хвостовой рекурсии - PullRequest
Новая
       0

Postorder с использованием хвостовой рекурсии

0 голосов
/ 27 марта 2011

Я нахожу эту ссылку, 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());
    }
  }

1 Ответ

1 голос
/ 27 марта 2011

Да, но код должен быть структурирован по-другому. Надлежащее основанное на стеке моделирование рекурсивного алгоритма должно сохранять узел в стеке до тех пор, пока узел и его дочерние элементы не будут полностью пройдены. Стек должен содержать экземпляры класса, который содержит информацию о том, сколько дочерних объектов было пройдено, скажем: 

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

(использование открытых полей для простоты). Всякий раз, когда вы помещаете узел в стек, нажимайте StackElement, который ссылается на этот узел, а numTraversedChildren равен 0. В верхней части цикла посмотрите (не выдвигайте) стек, чтобы найти верхний элемент. Если и только если numTraversedChildren == 2, вы знаете, что все дочерние узлы этого узла были пройдены. В этом случае вы можете обработать (в вашем случае распечатать) этот узел, а затем извлечь его. В противном случае оставьте узел в стеке, увеличьте значение numTraversedChildren и вставьте его левый дочерний элемент (если старое значение numTraversedChildren было равно 0) или его правый дочерний элемент (если старое значение numTraversedChildren было равно 1).

Обратите внимание, что при использовании этого подхода цикл while и операции push / pop в стеке эффективно имитируют вызовы функций: push - это вызов, pop - это возврат, а стек поддерживает все параметры и локальные переменные для каждого вызова функции. Элемент в верхней части стека всегда представляет функцию, которая выполняется в данный момент.

...