了解二叉树上迭代后置遍历实现中的逻辑 [英] Understanding the logic in iterative Postorder traversal implementation on a Binary tree

问题描述

我试图了解使用2个堆栈实现后遍历的直观性.有人是怎么想出来的，仅仅是一种观察或某种特殊的思维方式就可以帮助人们想出这样的方法.如果是的话，请解释如何正确地思考.

I was trying to understand how it is so intuitive to implement postorder traversal using 2 stacks. How did someone come up with it, is it just an observation or some particular way of thinking which helps one come up with such methods. If yes then please explain how to think in the right direction.

推荐答案

让我解释一下我如何迷失于解决方案:

Let me explain how I stumbled on the solution:

您从一个简单的观察开始:初步看，前序和后序遍历仅在其操作顺序上有所不同:

You start off with this simple observation: prima facie, the pre-order and post-order traversal differ only in their order of operations:

preOrder(node):
    if(node == null){
         return
    }
    visit(node)
    preOrder(node.leftChild)
    preOrder(node.rightChild)

postOrder(node):
    if(node == null){
         return
    }
    postOrder(node.leftChild)
    postOrder(node.rightChild)
    visit node

preOrder函数执行一些计算(访问该节点)，并对其自身进行两次递归调用-让此命令称为"VLR". postOrder函数进行两次递归调用，然后访问该节点('LRV').

The preOrder function does some computations (visiting the node) and two recursive calls to itself - lets call this order 'VLR'. The postOrder function makes two recursive calls and then does visits the node ('LRV').

preOrder使其适用于一个简单的迭代实现，在该迭代实现中，我们访问节点，并将与递归调用相对应的计算推送到堆栈上.

The preOrder lends itself to a simple iterative implementation, where we visit the node, and push the computation corresponding to the recursive calls onto a stack.

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();
        visit(currentNode);
        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }
    }

堆栈包含未访问节点的列表.我们弹出一个节点，对其进行访问，将其推入右侧，然后推入左侧.重复.这给了我们preOrder.

The stack contains the list of unvisited nodes. We pop a node, visit it, push its right child, push the left child. Repeat. This gives us preOrder.

(注意:对于VLR，由于堆栈是LIFO，我们将右子项推到左子项之前-我们在访问最后被推入的子项之前先访问最后被推入的子项-我们想在右子项之前访问左子项孩子.对于VRL，我们将不得不重新订购该订单)

(Note: For VLR, we push the right child before the left child because a stack is LIFO - we visit the child pushed last before we visit the child pushed before it - and we want to visit the left child before the right child. For VRL, we would have to revser the order)

说我们这样做，我们先推右孩子，再推左孩子，然后才访问节点(类似于postOrder中(1)递归调用和(2)节点访问的相对顺序的镜像.我们尝试使通过在末尾移动V将VLR转换为LRV.

Say we do this we push the right child, push the left child, and only then visit the node (kind of mirroring the relative order of (1) recursive calls and (2) node visit in postOrder. We try to make VLR to LRV by moving V at the end).

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();
        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }
        visit(currentNode);
    }   

这应该给我们postOrder，对吗?否.这仍然是预购商品.定义preOrder的不是在将子级推入堆栈之前我们访问了一个节点，而是在从堆栈中永久删除该节点(并因此在访问它之后)之后弹出(并因此访问了)堆栈上的子级.最终，堆栈中的子级最终会被弹出并访问，但是其父级已经被弹出并访问了-因此这是preOrder.这种方法似乎是死路一条.

This should give us postOrder, right? No. This is still preOrder. What defines preOrder is NOT that we visited a node before pushing children on the stack, but that we popped (and hence visited) the children on the stack AFTER permanently removing the node (and hence after visiting it) from the stack. The children in the stack are eventually, at some point, popped and visited, but their parent has already been popped and visited - and hence this is preOrder. This approach seems like a dead-end.

但是还有另一种方法！不必通过从前到后移动V来将VLR转换为LRV，我们可以通过反转VLR中的L和R的顺序(使其成为VRL)，然后将生成的"VRL"转换为设为"LRV".

But there is another way! Instead of turning VLR into LRV by moving V fro the front to end, we can make 'VLR' into 'LRV' by reversing the order of L and R in VLR (making it VRL), and then reversing the resulting 'VRL' to make it 'LRV'.

从左到右的PostOrder遍历(LRV)生成的序列与"VRL"的倒序相同-"VRL"-从右到左的preOrder遍历的序列.

通过将其设为VRL来调整迭代式预购商品

Let's tweak our iterative preOrder by making it VRL:

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }

        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        visit(currentNode);
    }   

这将为我们提供一个VRL preOrder(一个序列，其反向为LRV，即postOrder). 我们只需要反向遍历它！ 这是需要第二个堆栈的地方.如果我们将访问的每个节点推到另一个堆栈，然后将其从上到下遍历，我们将获得postOrder！

This will give us a VRL preOrder (a sequence whose reverse is LRV, the postOrder). We just need to traverse it in reverse! This is where the need for a second stack comes in. If we push every node we visit to another stack, and then just traverse it top to down, we will get our postOrder!

这是我的最终解决方案:

Here is my final solution:

    var reverseStack = new Stack();
        while(!nodeStack.isEmpty()){
            var currentNode = nodeStack.pop()
            reverseStack.push(currentNode)
            if (currentNode.leftChild){
                nodeStack.push(currentNode.leftChild)
            }

            if (currentNode.rightChild){
                nodeStack.push(currentNode.rightChild)
            }
        }

        while(!reverseStack.isEmpty()){
            console.log(reverseStack.pop().getElement())
        }

您可以进行一些小的优化-这将为您提供在线上看到的标准两层式解决方案.请注意，两个堆栈不是必须的-例如，如果我们跟踪最后一个访问的节点，则可以只使用一个堆栈来实现postOrder.

There are minor optimizations you can make - which will give you the standard two stack solution you see online. Please note that two stacks are not necessary - and it is possible to implement postOrder with just one stack - for example, if we keep track of the last node visited.

这篇关于了解二叉树上迭代后置遍历实现中的逻辑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！