二叉树前中后序遍历的非递归实现
递归改非递归一般都会用到栈这个结构,栈的特点就是先进后出,所以说栈其实是维护了一个特定顺序的结构。
我们先定义这么一种操作:
左遍历:指从给定节点开始无限遍历其左子节点直到叶子节点为止,并将其依次压入栈中。(这样在栈中的节点就都满足一个性质:入栈时一定是先根后左,出栈时一定是先左后根)
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),则可以保证左->根
的顺序
这里大家肯定会问,这个只是从根节点开始的左子节点的顺序呀,如果有右子节点怎么办呢?
我们拿先序遍历举例说明:
先序遍历要求的顺序是 根->左->右
。由前面的讨论我们已经可以做到根->左
的顺序访问了,即只要做到入栈时访问即可。
那么如果有右子节点该如何处理呢?右子节的入栈条件是什么呢?
要解决这个问题我们需要先定义好出栈的含义,首先我们可以明确的是,对于先序遍历来说,入栈时访问,因此按照我们之前的定义,根节点一定在左子节点前被访问, 而出栈的时机则是左遍历结束,因为此时对于栈顶节点来说:
- 该节点的根节点一定访问过了(入栈时)
- 该节点没有左子节点(根据左遍历的定义即可推出),或左子节点已经访问过了
而这不正是访问右子节点的前置条件吗?换句话说,直接对出栈节点的右子节点左遍历。
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
处开始右节点的左遍历
按照上述讨论我们再来分析下中序遍历
中序遍历要求的顺序是 左->根->右
。由前面的讨论我们已经可以做到左->根
的顺序访问了,即只要做到出栈时访问即可。
我们通过入栈维护了根->左
的存储顺序,而又通过出栈获取左->根
的访问顺序。
此时出栈的时机也是左遍历结束,因为此时对于栈顶节点来说:
- 该节点左子节点一定访问过了
- 现在正好需要访问该节点,并对右子树进行左遍历
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 // 准备左遍历右子树
}
}
}
大家可能已经注意到,前序遍历和中序遍历的代码几乎一样,只是访问的时机不同。
最后我们再来看下后序遍历
相比于前序和中序,后序稍微复杂点。目前我们已经可以做到根->左
或者左->根
的访问顺序了,
但是后序遍历要求左->右->根
,显然我们能够参考的是之前实现的左->根
的定义,即出栈时访问。
但是后序遍历的右节点是介于左和根之间的, 这点则和中序遍历不同,因此对于出栈的处理也不同。
我们知道中序遍历中出栈的条件是左遍历结束。
但是后序遍历时,判断栈顶节点能否出栈除了左遍历结束还有两种情况需要考虑:
- 右子树还没有访问,需要先遍历右子树(不可以出栈);
- 右子树已经访问过了,可以访问该节点了(可以出栈)。
问题的关键就在于右子树有没有被访问过,因此我们需要定义一个变量保存上一个被访问的节点,以此来区分上述的两种情况。
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 // 栈顶节点的右子树没有遍历,则开始遍历右子树
}
}
}
}
总结一下:
前序遍历:左遍历根节点,入栈时访问,出栈时左遍历右子节点
中序遍历:左遍历根节点,出栈时访问,出栈时左遍历右子节点
后序遍历:左遍历根节点,出栈时访问,记录上次访问的节点,出栈前判断上次访问节点是否为其右子节点,是则允许出栈,否则继续左遍历右子节点