树

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

前端中常见的树包括：
DOM树/级联选择/树形控件 

JS中没有树，但是可以用Object和Array构建树
树的常用操作：
深度/广度优先遍历
前中后序遍历

深度/广度优先遍历

深度优先遍历

尽可能深的搜索树的分支

算法口诀：
访问根节点
对根节点的children挨个进行深度优先遍历

const tree ={
    val:'a',
    children:[
        {
        val:'b',
        children:[
            {
            val:'d',
            children:[],
            },
            {
            val:'e',
            children:[],
            }
        ],
        {
        val:'c',
        children:[
                        {
            val:'f',
            children:[],
            },
            {
            val:'g',
            children:[],
            }
        ]
        }
}
    ]
}

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

dfs(tree)

广度优先遍历

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

算法口诀：
新建队列把根节点入队
把队头出队并访问
把对头的children挨个入队
重复二三步，直到队列为空

const tree ={
    val:'a',
    children:[
        {
        val:'b',
        children:[
            {
            val:'d',
            children:[],
            },
            {
            val:'e',
            children:[],
            }
        ],
        {
        val:'c',
        children:[
                        {
            val:'f',
            children:[],
            },
            {
            val:'g',
            children:[],
            }
        ]
        }
}
    ]
}

const bfs = () =>{
    const q = [root]
    while(q.length >0){
        const n = q.shift()
        console.log(n.val)
        n.children.forEach(child =>{
            q.push(child)
        })
    }
}

二叉树

树中每个节点最多只能有两个子节点
在JS中通常用Objec来模拟二叉树

先序遍历算法口诀

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

//获取二叉树  
const bt

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

const bt

const preorder = (root) =>{
    if(!root) return
    const stack = [root]
    while(stack.length){
        const n = stack.pop()
        cosole.log(n.val)
        if(n.right) stack.push(n.right)
        if(n.left) stack.push(n.left)
    }
}

中序遍历算法口诀

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

//获取二叉树  
const bt

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

const bt

const inorder = (root) =>{
    if(!root) return
    const stack = []
    let p = root
    while(stack.length || p){
        while(p){
            stakc.push(p)
            p = p.left
    }
        const n = stack.pop()
        console.log(n.val)
        p = n.right
    }
}

后序遍历算法口诀

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

//获取二叉树  
const bt

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

const bt

const postder = (root) =>{
    if(!root) return
    const stack = [root]
    const outputStack =[]
    while(stack.length){
        const n = stack.pop()
        outputStack.push(n)
        if(n.left) stack.push(n.left)
        if(n.right) stack.push(n.right)
    }
    while(outputStack.length >0) {
        const n = outputStack.pop()
        console.log(n.val)
    }
}

Check out the documentation for the full list of runtime APIs.