# 前序遍历
遍历顺序为：
首先我们来实现一下前序遍历, 你可能很容易的就想到了必须用递归的方式来实现:
递归遍历
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 = 
