树是分层数据的抽象模型

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

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

树上的常用操作：

深度/广度优先遍历，中序遍历

深度优先遍历

尽可能深入地搜索树的分支

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

广度优先遍历

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

const  bfs = ( root) => { 
     // add the root node to the queue
     const q = [root] 
     while(q. length >  0) { 
         const n = q. shift(); 
         console. log(n. val) 
        n. children. forEach( child => { 
            q. push(child) 
        }) 
    } 
}
 copy code

前序遍历

• 访问根节点
• 根节点左子树的前序遍历
• 根节点右子树的前序遍历

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 
}
 copy code

中序遍历

• 根节点左子树的中序遍历
• 访问节点
• 根节点右子树的中序遍历

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

后序遍历

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

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

层次遍历（广度遍历）

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
 copy code

关注七爪网，获取更多APP/小程序/网站源码资源！