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

я нашел эту ссылку, 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());
    }
  }

algorithm tail-recursion
person user612308    schedule 27.03.2011    source источник
comment
используйте кнопку {} в редакторе для форматирования кода в следующий раз.   -  person Mat    schedule 27.03.2011

Ответы (1)


arrow_upward
1
arrow_downward

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

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 — это возврат, а стек поддерживает все параметры и локальные переменные для каждой функции. призыв. Элемент наверху стека всегда представляет функцию, которая выполняется в данный момент.

person Aasmund Eldhuset    schedule 27.03.2011
comment
спасибо за подробный ответ. это в основном добавляет еще один элемент данных к узлу. если мы пойдем с этим подходом, мы можем добавить флаг посещения и родительский указатель на узел, и вообще не использовать стек. - person user612308; 27.03.2011
comment
@ user612308: Это правильно, но имейте в виду, что это приведет к смешению самой структуры данных (дерева) с данными, специфичными для алгоритма (флаг visited и, возможно, указатель parent). Это совершенно нормально (в конце концов, структуры данных и алгоритмы тесно связаны), если единственной целью дерева является однократное выполнение этого алгоритма, но если дерево используется в другом месте программы, я бы рекомендовал хранить данные алгоритма вне дерева. - person Aasmund Eldhuset; 27.03.2011
comment
это верное замечание, я тоже об этом думал. еще раз спасибо за помощь Осмунд! - person user612308; 27.03.2011
comment
@ user612308: Рад, что помогло. :-) - person Aasmund Eldhuset; 27.03.2011