前序遍历|博客系列

# 前序遍历

遍历顺序为：

首先我们来实现一下前序遍历, 你可能很容易的就想到了必须用递归的方式来实现:

递归遍历

function preOrderRec(tree) { // 前序遍历函数
    let list = [] // 定义一个数组来放最终遍历结果
    let preOrderRecFn = function(node) { // 定义一个函数来实现递归
        if (node) { // 若是该节点存在
            list.push(node.value) // 当前节点的值推进数组
            preOrderRecFn(node.left) // 先遍历左子树
            preOrderRecFn(node.right) // 然后遍历右子树
        }
    }
    preOrderRecFn(tree)
    return list
}

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

可以看到,上面preOrderRec函数接受一个tree对象, 然后判断每个节点是否存在, 若是存在则先将当前节点的值推进数组, 然后再遍历左子树, 之后再遍历右子树.

非递归遍历

function preOrderUnRec(tree) {
    let list = [] // 定义一个数组来放最终遍历结果
    let preOrderUnRecFn = function(node) { // 定义一个函数来遍历节点
        if (node) { // 若是该节点存在
            let stack = [node] // 将当前节点推入栈
            while (stack.length !== 0) { // 终止条件: stack数组为空
                node = stack.pop() // 取出栈中的最后一个节点
                list.push(node.value) // 当前节点的值推进数组
                if (node.right) stack.push(node.right) // 先将右子树节点推入栈
                if (node.left) stack.push(node.left) // 再将左子树节点推入栈
            }
        }
    }
    preOrderUnRecFn(tree)
    return list
}

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

如果你看上面的代码觉得有点生涩的话, 可以先看第一遍循环:

非递归遍历第一次循环

function preOrderUnRec(tree) {
    let list = [] // 定义一个数组来放最终遍历结果
    let preOrderUnRecFn = function(node) { // 定义一个函数来遍历节点
        // 第一次输入的 node 为 {value: 'Root', left: {}, right: {}}
        if (node) {
            // 将当前节点推入栈
            // 此时 stack: [ {value: 'Root', left: {}, right: {}} ]
            let stack = [node]
            while (stack.length !== 0) { // 终止条件: stack数组为空
                // 取出栈中的最后一个节点, 此时:
                // node: {value: 'Root', left: {}, right: {}}
                // stack: []
                node = stack.pop()
                // 当前节点的值推进数组
                // list: ['Root']
                list.push(node.value)
                // 先将右子树节点推入栈
                // stack: [ {value: 'R', left: {}, right: {}} ]
                if (node.right) stack.push(node.right)
                // 再将左子树节点推入栈
                // stack: [ {value: 'R', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]
                if (node.left) stack.push(node.left)
            }
        }
    }
    preOrderUnRecFn(tree)
    return list
}

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

经过第一次循环之后, 我们发现list中已经存放了我们想要的Root字符串.

stack数组也变成了两项:

stack: [ {value: 'R', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]

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

此时进入while循环的判断stack.length !== 0, 显然这个判断是为true, 所以程序又会继续往下走:

非递归遍历第二次循环

while (stack.length !== 0) { // 终止条件: stack数组为空
    // 第二次循环
    // 此时 stack: [ {value: 'R', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]
    // node: {value: 'L', left: {}, right: {}}
    // stack: [ {value: 'R', left: {}, right: {}} ]
    node = stack.pop()
    // 当前节点的值推进数组
    // list: ['Root', 'L']
    list.push(node.value)
    // 先将右子树节点推入栈
    // stack: [ {value: 'R', left: {}, right: {}}, {value: 'LR'} ]
    if (node.right) stack.push(node.right)
    // 再将左子树节点推入栈
    // stack: [ {value: 'R', left: {}, right: {}}, {value: 'LR'}, {value: 'LL'} ]
    if (node.left) stack.push(node.left)
}

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

看到这里你应该就看懂了.

# 前序遍历

遍历顺序为：

首先我们来实现一下前序遍历, 你可能很容易的就想到了必须用递归的方式来实现:

递归遍历

function preOrderRec(tree) { // 前序遍历函数
    let list = [] // 定义一个数组来放最终遍历结果
    let preOrderRecFn = function(node) { // 定义一个函数来实现递归
        if (node) { // 若是该节点存在
            list.push(node.value) // 当前节点的值推进数组
            preOrderRecFn(node.left) // 先遍历左子树
            preOrderRecFn(node.right) // 然后遍历右子树
        }
    }
    preOrderRecFn(tree)
    return list
}

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

非递归遍历

function preOrderUnRec(tree) {
    let list = [] // 定义一个数组来放最终遍历结果
    let preOrderUnRecFn = function(node) { // 定义一个函数来遍历节点
        if (node) { // 若是该节点存在
            let stack = [node] // 将当前节点推入栈
            while (stack.length !== 0) { // 终止条件: stack数组为空
                node = stack.pop() // 取出栈中的最后一个节点
                list.push(node.value) // 当前节点的值推进数组
                if (node.right) stack.push(node.right) // 先将右子树节点推入栈
                if (node.left) stack.push(node.left) // 再将左子树节点推入栈
            }
        }
    }
    preOrderUnRecFn(tree)
    return list
}

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

如果你看上面的代码觉得有点生涩的话, 可以先看第一遍循环:

非递归遍历第一次循环

function preOrderUnRec(tree) {
    let list = [] // 定义一个数组来放最终遍历结果
    let preOrderUnRecFn = function(node) { // 定义一个函数来遍历节点
        // 第一次输入的 node 为 {value: 'Root', left: {}, right: {}}
        if (node) {
            // 将当前节点推入栈
            // 此时 stack: [ {value: 'Root', left: {}, right: {}} ]
            let stack = [node]
            while (stack.length !== 0) { // 终止条件: stack数组为空
                // 取出栈中的最后一个节点, 此时:
                // node: {value: 'Root', left: {}, right: {}}
                // stack: []
                node = stack.pop()
                // 当前节点的值推进数组
                // list: ['Root']
                list.push(node.value)
                // 先将右子树节点推入栈
                // stack: [ {value: 'R', left: {}, right: {}} ]
                if (node.right) stack.push(node.right)
                // 再将左子树节点推入栈
                // stack: [ {value: 'R', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]
                if (node.left) stack.push(node.left)
            }
        }
    }
    preOrderUnRecFn(tree)
    return list
}

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

经过第一次循环之后, 我们发现list中已经存放了我们想要的Root字符串.

stack数组也变成了两项:

stack: [ {value: 'R', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]

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

此时进入while循环的判断stack.length !== 0, 显然这个判断是为true, 所以程序又会继续往下走:

非递归遍历第二次循环

while (stack.length !== 0) { // 终止条件: stack数组为空
    // 第二次循环
    // 此时 stack: [ {value: 'R', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]
    // node: {value: 'L', left: {}, right: {}}
    // stack: [ {value: 'R', left: {}, right: {}} ]
    node = stack.pop()
    // 当前节点的值推进数组
    // list: ['Root', 'L']
    list.push(node.value)
    // 先将右子树节点推入栈
    // stack: [ {value: 'R', left: {}, right: {}}, {value: 'LR'} ]
    if (node.right) stack.push(node.right)
    // 再将左子树节点推入栈
    // stack: [ {value: 'R', left: {}, right: {}}, {value: 'LR'}, {value: 'LL'} ]
    if (node.left) stack.push(node.left)
}

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

看到这里你应该就看懂了.