二叉树前中后序遍历的非递归实现

递归改非递归一般都会用到栈这个结构,栈的特点就是先进后出,所以说栈其实是维护了一个特定顺序的结构。

我们先定义这么一种操作:

左遍历:指从给定节点开始无限遍历其左子节点直到叶子节点为止,并将其依次压入栈中。(这样在栈中的节点就都满足一个性质:入栈时一定是先根后左,出栈时一定是先左后根)

function traversal(node) {
    const stack = []
    while(node) {
        console.log(node) // ------> @1
        stack.push(node)
        node = node.left
    }
    while(stack.length) {
        node = stack.pop()
        console.log(node) // ------> @2
    }
}

如果我们在入栈的时候访问节点(@1),则可以保证根->左的顺序

如果我们在出栈的时候访问节点(@2),则可以保证左->根的顺序

这里大家肯定会问,这个只是从根节点开始的左子节点的顺序呀,如果有右子节点怎么办呢?

我们拿先序遍历举例说明:

先序遍历要求的顺序是 根->左->右 。由前面的讨论我们已经可以做到根->左的顺序访问了,即只要做到入栈时访问即可。

那么如果有右子节点该如何处理呢?右子节的入栈条件是什么呢?

要解决这个问题我们需要先定义好出栈的含义,首先我们可以明确的是,对于先序遍历来说,入栈时访问,因此按照我们之前的定义,根节点一定在左子节点前被访问, 而出栈的时机则是左遍历结束,因为此时对于栈顶节点来说:

  1. 该节点的根节点一定访问过了(入栈时)
  2. 该节点没有左子节点(根据左遍历的定义即可推出),或左子节点已经访问过了

而这不正是访问右子节点的前置条件吗?换句话说,直接对出栈节点的右子节点左遍历。

function traversal(node) {
    const stack = []
    while (stack.length > 0 || node) {
        while(node) {         // -----> @1
            console.log(node) // 访问节点
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack.pop() // 此时的栈顶节点的根和左都可以保证已经访问过
            node = node.right // -----> @2
        }
    }
}

@1处的 while 循环是我们定义的 左遍历,而对右节点左遍历就是把当前 node 赋值为右子节点(@2),并跳到@1处开始右节点的左遍历

按照上述讨论我们再来分析下中序遍历

中序遍历要求的顺序是 左->根->右 。由前面的讨论我们已经可以做到左->根的顺序访问了,即只要做到出栈时访问即可。

我们通过入栈维护了根->左的存储顺序,而又通过出栈获取左->根的访问顺序。

此时出栈的时机也是左遍历结束,因为此时对于栈顶节点来说:

  1. 该节点左子节点一定访问过了
  2. 现在正好需要访问该节点,并对右子树进行左遍历
function traversal(node) {
    const stack = []
    while (stack.length > 0 || node) {
        while(node) {
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack.pop() // 此时的栈顶节点的左子树都已访问过
            console.log(node) // 访问节点
            node = node.right // 准备左遍历右子树
        }
    }
}

大家可能已经注意到,前序遍历和中序遍历的代码几乎一样,只是访问的时机不同。

最后我们再来看下后序遍历

相比于前序和中序,后序稍微复杂点。目前我们已经可以做到根->左或者左->根的访问顺序了, 但是后序遍历要求左->右->根,显然我们能够参考的是之前实现的左->根的定义,即出栈时访问。 但是后序遍历的右节点是介于左和根之间的, 这点则和中序遍历不同,因此对于出栈的处理也不同。 我们知道中序遍历中出栈的条件是左遍历结束。 但是后序遍历时,判断栈顶节点能否出栈除了左遍历结束还有两种情况需要考虑:

  1. 右子树还没有访问,需要先遍历右子树(不可以出栈);
  2. 右子树已经访问过了,可以访问该节点了(可以出栈)。

问题的关键就在于右子树有没有被访问过,因此我们需要定义一个变量保存上一个被访问的节点,以此来区分上述的两种情况。

function traversal(node) {
    const stack = []
    let lastVisit = null
    while (stack.length > 0 || node) {
        while(node) {
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack[stack.length - 1] // 查看栈顶节点
            if (!node.right || node.right === lastVisit) { // 栈顶节点没有右子节点或右子节点已经访问过,则可以访问该节点
                node = stack.pop()
                console.log(node) // 访问节点
                lastVisit = node // 更新最新访问节点
                node = null // node 置空跳过while循环,再次处理栈
            } else {
                node = node.right // 栈顶节点的右子树没有遍历,则开始遍历右子树
            }
        }
    }
}

总结一下:

前序遍历:左遍历根节点,入栈时访问,出栈时左遍历右子节点

中序遍历:左遍历根节点,出栈时访问,出栈时左遍历右子节点

后序遍历:左遍历根节点,出栈时访问,记录上次访问的节点,出栈前判断上次访问节点是否为其右子节点,是则允许出栈,否则继续左遍历右子节点