почему 2 стопки так эффективны для пост-заказных поперечин

Итак, я знаком с обходом постпорядка:

L -> R -> P (слева направо к родителю).

Я видел код, который мог довольно элегантно выполнять обход в обратном порядке, используя 2 стека:

public void postOrderTransverse(Node r){
    if(r == null){return;}
    Stack<Node> s = new Stack<Node>();
    Stack<Node> reverser = new Stack<Node>();
    s.push(r);
    while(!s.isEmpty()){
        Node temp = s.pop();
        reverser.push(temp);
        if (temp.left != null){
            s.push(temp.left);}
        if(temp.right != null){
            s.push(temp.right);}
    }
    while(!reverser.empty()){
        System.out.print(reverser.peek());
        reverser.pop();
    }
}

(через http://articles.leetcode.com/binary-tree-post-order-traversal/)

где, по сути, один стек просто переворачивает другой. Мне просто очень интересно, как это работает. У меня есть гипотеза, что Stack s принимает ввод, так что вывод будет примерно P -> R -> L, и он просто передает это на реверсор Stack, который выплевывает L -> R .-> P, так как это Last In First Out .

Однако, просто пытаясь продумать процессы этого алгоритма, я изо всех сил пытаюсь понять, как и почему Stack принимает входные данные именно так. Надеясь, что я мог бы получить некоторое представление о здесь! Спасибо :)


java algorithm binary-tree postorder
person javanewbie    schedule 19.08.2016    source источник
comment
Он выполняет обход в предварительном порядке, используя первый стек, и помещает результаты во второй стек, а затем извлекает этот стек, что дает вам обход в обратном порядке, просто обращая результаты.   -  person user207421    schedule 19.08.2016
comment
@EJP, он не выполняет предварительный обход, так как сначала проходит правый узел. На самом деле это петлевая версия рекурсивного обхода в обратном порядке.   -  person user3707125    schedule 19.08.2016

Ответы (1)


arrow_upward
1
arrow_downward

Предоставленный вами код представляет собой просто циклическую версию соответствующего рекурсивного решения:

public void postOrderTraverseRecursive(Node r){
    if(r == null){return;}

    if (r.left != null){
        postOrderTraverseRecursive(r.left);}
    if(r.right != null){
        postOrderTraverseRecursive(r.right);}

    System.out.print(r);
}

Чтобы преобразовать рекурсию в цикл, нам нужно обратить порядок выполнения операторов. Мы будем использовать один стек для поддержки вызовов рекурсии и один для поддержки вывода рекурсии (т. е. System.out.print аргументов инструкции).

Ваш код с более значимыми именами переменных и объяснением:

public void postOrderTraverse(Node root){
    if(root == null){return;}
    Stack<Node> recursionStack = new Stack<Node>();
    Stack<Node> printStack = new Stack<Node>();
    recursionStack.push(root);
    while(!recursionStack.isEmpty()){
        Node node = recursionStack.pop();
        /* Recursion iteration start */
        // According to the recursion we should process left->right->node.
        // Considering that in the loop version we have to reverse the order of invocations,
        // we are processing node->right->left
        printStack.push(node); // node is added to printStack immediately
        // left is added to recursionStack first, but because
        // of the FILO nature of the stack it will be processed last
        if (node.left != null){
            recursionStack.push(node.left);}
        // right is added to recursionStack last, but because
        // of the FILO nature of the stack it will be processed first
        if(node.right != null){
            recursionStack.push(node.right);}
        /* Recursion iteration end */
    }
    // We've processed all the input and now we have reversed
    // history of the prints, processing them in reverse order
    // to receive the actual one
    while(!printStack.empty()){
        System.out.print(printStack.peek());
        printStack.pop();
    }
}
person user3707125    schedule 19.08.2016