JS实现二叉树的遍历（DFS、BFS、前中后序遍历）

对于二叉树，有深度遍历（DFS）和广度遍历（BFS），深度遍历有前序遍历、中序遍历和后序遍历三种方法，广度遍历也叫做层序遍历。深度遍历的思路是用递归或者循环的方式，广度遍历可以用队列这种数据结构。四种遍历的方式分别是：
（1）前序遍历：根节点，左节点，右节点。
（2）中序遍历：左节点，根节点，右节点。
（3）后序遍历：左节点，右节点，根节点。
（4）广度遍历：按每层遍历
JavaScript代码实现如下：
分别写一个遍历函数，并且以根节点作为形参，返回一个由节点值组成的数组。创建节点的构造函数如下：

function TreeNode(x){
    this.val = x
    this.left = null
    this.right = null
}

一、前序遍历
（1）递归的实现，这种方式思路简单，但消耗空间大

let res = []
function preorderTraverse(pRoot){
    if(!pRoot){//递归的出口
        return 
    }
    res.push(pRoot.val)
    preorderTraverse(pRoot.left)
    preorderTraverse(pRoot.right)
}

（2）循环的方式：这里用到栈这种数据结构，为了访问右子树而存在。对每个节点
a、访问其节点值，并把该节点入栈，在将当前节点设置为左子树。
b、判断节点是否为空，若为空，则将栈顶节点出栈，将当前节点设置为右节点；若不为空，则执行a步骤，直到当前节点为空或者栈为空。

function preorderTraverse(pRoot){
    if(!pRoot){ //判断根节点是否为空
        return []
    }
    let res = [], stack = []
    while(pRoot !== null || stack.length !== 0) {
        while(pRoot !== null){
            res.push(pRoot.val) //先访问当前节点值
            stack.push(pRoot) //将当前节点推入栈中，为了便于访问右节点
            pRoot = pRoot.left //将节点设置为左节点，并通过while循环判断是否为空
        }
        pRoot = stack.pop() 
        pRoot = pRoot.right//将节点设置为右节点
    }
    return res
}

二、中序遍历

//递归的方式
let res = []
function inorderTraverse(pRoot){
    if(!pRoot){//递归的出口
        return 
    }
    inorderTraverse(pRoot.left)
    res.push(pRoot.val)
    inorderTraverse(pRoot.right)
}

//循环的方式
function inorderTraverse(pRoot){
    if(!pRoot){
        return []
    }
    let res = [], stack = []
    while(pRoot !== null || stack.length !== 0) {
        while(pRoot !== null){
            stack.push(pRoot)
            pRoot = pRoot.left
        }
        pRoot = stack.pop()
        res.push(pRoot.val)
        pRoot = pRoot.right
    }
    return res
}

三、后序遍历

let res = []
function postorderTraverse(pRoot){
    if(!pRoot){//递归的出口
        return 
    }
    postorderTraverse(pRoot.left)
    postorderTraverse(pRoot.right)
    res.push(pRoot.val)
}

四、广度遍历

function bfs(pRoot){
    if(!node){
        return []
    }
    let queue = [pRoot]  //将根节点加入到队列中
    let result = []  //结果数组
    while(queue.length){
        let len = queue.length   //队列中长度循环一次就得变一次
        let tempArr = []  //存储每层节点值的临时数组，方便一层层打印
        for(let i = 0; i < len; i++){   //遍历每层节点
            let temp = queue.shift()
            tempArr.push(temp.val)
            if(temp.left){
                queue.push(pNode.left)
            }
            if(temp.right){
                queue.push(pNode.right)
            }
        }
       result.push([...tempArr])
    }
    return result
}

最后编辑于：2020.09.02 16:12:29