树的多种遍历算法

前言

树是一种分层数据的抽象模型

前端常见的树：DOM、树、级联选择（selection）、树形控件

JS中没有树这种结构，但是可以用Object和Array构建树

树的常用操作：

深度/广度优先遍历、先中后序遍历

深度优先遍历

尽可能深的搜索树的分支

const dfs = (root) => { 
    console.log(root.val) 
    root.children.forEach(dfs) 
}

广度优先遍历

先访问离根节点最近的节点

const bfs = (root) => { 
    //把根节点加入队列 
    const q = [root] 
    while(q.length > 0) { 
        const n = q.shift(); 
        console.log(n.val) 
        n.children.forEach(child => { 
            q.push(child) 
        }) 
    } 
}

先序遍历

• 访问根节点
• 对根节点的左子树进行先序遍历
• 对根节点的右子树进行先序遍历

var res = [] 
const preorder = (root) => { 
    if(!root) {return ;} 
    if(root !== null) { 
        res.push(root.val) 
        preorder(root.left, res) preorder(root.right, res) 
    } 
    return res 
}

中序遍历

• 对根节点的左子树进行中序遍历
• 访问跟节点
• 对根节点的右子树进行中序遍历

const inorder = (root) => { 
    if(!root) {return ;} 
    inorder(root.left) 
    console.log(root.val) 
    inorder(root.right) 
}

后序遍历

• 对根节点的左子树进行后序遍历
• 对根节点的右子树进行后序遍历
• 访问根节点

var res = [] 
const postorder = (root) => { 
    if(root !== null) { 
        postorder(root.left, res) 
        postorder(root.right, res) 
        res.push(root.val) 
    } 
    return res 
}

层次遍历（广度遍历）

const res = []     
function traversal (root, depth) {         
    if (root !== null) {             
        if (!res[depth]) {                 
            res[depth] = []             
        }             
        traversal(root.left, depth + 1)             
        res[depth].push(root.val)             
        traversal(root.right, depth + 1)         
    }     
}     
traversal(root, 0)     
return res

最后

本人8月更文挑战圆满结束啦，完结撒花！