中序遍历|博客系列

# 中序遍历

遍历顺序为：

遍历之后：["LL","L","LR","Root","RL","R","RR"]

递归遍历

function inOrderRec (tree) {
    let list = []
    let inOrderRecFn = function (node) {
        if (node) {
            if (node.left) inOrderRecFn(node.left)
            list.push(node.value)
            if (node.right) inOrderRecFn(node.right)
        }
    }
    inOrderRecFn(tree)
    return list
}

@前端进阶之旅: 代码已经复制到剪贴板

非递归遍历

非遍历我是这样考虑的：

会先把中间"Root"压入栈中
然后开始压入"Root"的左边节点
当左边节点全部都压进栈了之后，["Root", "L", "LL"]
要开始从栈的末位取出value了，同时要开始把右边的也压入栈了
当取出"LL"的时候，"LL"已经没有左右子节点了，所以会继续从栈的末位取出value
也就是取出了"L"，"L"还是有右节点的，所以要把"LR"压入栈
"LR"压入栈之后，"LR"也是没有左子节点的，所以会从栈的末位取出，且它又没有右子节点，就会继续取出
继续取出"Root"，这时候再开始把node = "Root".right了，也就是要开始遍历"R"了
以此类推把"R"也按上面的步骤遍历完

function inOrderUnRec (tree) {
    let list = []
    let inOrderUnRecFn = function (node) {
        if (node) { // 当前节点存在
            let stack = [] // 定义一个空的栈
            while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在
                if (node) { // 若是节点存在
                    stack.push(node) // 将当前节点推入栈
                    node = node.left // 将左子树作为当前节点
                } else { // 当前节点不存在(左子树为空)
                    node = stack.pop() // 从栈中取出节点
                    list.push(node.value)
                    node = node.right // 将右子树作为当前节点
                }
            }
        }
    }
    inOrderUnRecFn(tree)
    return list
}

@前端进阶之旅: 代码已经复制到剪贴板

非递归第一次遍历

let stack = [] // 定义一个空的栈
while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在
    // 此时：
    // node: {value: 'Root', left: {}, right: {}}
    if (node) { // 若是节点存在
        // 将当前节点推入栈
        // stack: [ {value: 'Root', left: {}, right: {}} ]
        stack.push(node)
        // 将左子树作为当前节点
        // node: {value: 'L', left: {}, right: {}}
        node = node.left
    } else { // 当前节点不存在(左子树为空)
        node = stack.pop() // 从栈中取出节点
        list.push(node.value)
        node = node.right // 将右子树作为当前节点
    }
}

@前端进阶之旅: 代码已经复制到剪贴板

非递归第二次遍历

let stack = [] // 定义一个空的栈
while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在
    // 此时：
    // node: {value: 'L', left: {}, right: {}}
    if (node) { // 若是节点存在
        // 将当前节点推入栈
        // stack: [ {value: 'Root', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]
        stack.push(node)
        // 将左子树作为当前节点
        // node: {value: 'LL'}
        node = node.left
    } else { // 当前节点不存在(左子树为空)
        node = stack.pop() // 从栈中取出节点
        list.push(node.value)
        node = node.right // 将右子树作为当前节点
    }
}

@前端进阶之旅: 代码已经复制到剪贴板

经过第二次循环之后，stack变成了[ {value: 'Root', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ], 当前节点node变成了{value: 'LL'}。

这样在第四次循环的时候, node就为undefinded了，此时进入了else中，然后就达到了先遍历所有左子树，再获取根节点，最后遍历右子树的效果。

# 中序遍历

遍历顺序为：

遍历之后：["LL","L","LR","Root","RL","R","RR"]

递归遍历

function inOrderRec (tree) {
    let list = []
    let inOrderRecFn = function (node) {
        if (node) {
            if (node.left) inOrderRecFn(node.left)
            list.push(node.value)
            if (node.right) inOrderRecFn(node.right)
        }
    }
    inOrderRecFn(tree)
    return list
}

@前端进阶之旅: 代码已经复制到剪贴板

非递归遍历

非遍历我是这样考虑的：

会先把中间"Root"压入栈中
然后开始压入"Root"的左边节点
当左边节点全部都压进栈了之后，["Root", "L", "LL"]
要开始从栈的末位取出value了，同时要开始把右边的也压入栈了
当取出"LL"的时候，"LL"已经没有左右子节点了，所以会继续从栈的末位取出value
也就是取出了"L"，"L"还是有右节点的，所以要把"LR"压入栈
"LR"压入栈之后，"LR"也是没有左子节点的，所以会从栈的末位取出，且它又没有右子节点，就会继续取出
继续取出"Root"，这时候再开始把node = "Root".right了，也就是要开始遍历"R"了
以此类推把"R"也按上面的步骤遍历完

function inOrderUnRec (tree) {
    let list = []
    let inOrderUnRecFn = function (node) {
        if (node) { // 当前节点存在
            let stack = [] // 定义一个空的栈
            while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在
                if (node) { // 若是节点存在
                    stack.push(node) // 将当前节点推入栈
                    node = node.left // 将左子树作为当前节点
                } else { // 当前节点不存在(左子树为空)
                    node = stack.pop() // 从栈中取出节点
                    list.push(node.value)
                    node = node.right // 将右子树作为当前节点
                }
            }
        }
    }
    inOrderUnRecFn(tree)
    return list
}

@前端进阶之旅: 代码已经复制到剪贴板

非递归第一次遍历

let stack = [] // 定义一个空的栈
while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在
    // 此时：
    // node: {value: 'Root', left: {}, right: {}}
    if (node) { // 若是节点存在
        // 将当前节点推入栈
        // stack: [ {value: 'Root', left: {}, right: {}} ]
        stack.push(node)
        // 将左子树作为当前节点
        // node: {value: 'L', left: {}, right: {}}
        node = node.left
    } else { // 当前节点不存在(左子树为空)
        node = stack.pop() // 从栈中取出节点
        list.push(node.value)
        node = node.right // 将右子树作为当前节点
    }
}

@前端进阶之旅: 代码已经复制到剪贴板

非递归第二次遍历

let stack = [] // 定义一个空的栈
while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在
    // 此时：
    // node: {value: 'L', left: {}, right: {}}
    if (node) { // 若是节点存在
        // 将当前节点推入栈
        // stack: [ {value: 'Root', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]
        stack.push(node)
        // 将左子树作为当前节点
        // node: {value: 'LL'}
        node = node.left
    } else { // 当前节点不存在(左子树为空)
        node = stack.pop() // 从栈中取出节点
        list.push(node.value)
        node = node.right // 将右子树作为当前节点
    }
}

@前端进阶之旅: 代码已经复制到剪贴板

经过第二次循环之后，stack变成了[ {value: 'Root', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ], 当前节点node变成了{value: 'LL'}。

这样在第四次循环的时候, node就为undefinded了，此时进入了else中，然后就达到了先遍历所有左子树，再获取根节点，最后遍历右子树的效果。