29、深度、广度优先遍历

概念

深度优先遍历（Depth First Search）： 尽可能深的搜索树的分支

广度优先遍历（Breath First Search）：先访问离根节点最近的节点

算法思路

深度优先遍历

• 访问根节点
• 对根节点的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)

运行结果为：
a
b
d
e
c
f
g
符合深度优先遍历

广度优先遍历

• 新建一个队列，把根节点入队
• 把队头出队并访问
• 把对头的children挨个入队
• 重复第二、第三步，直到队列为空

const bfs = (root) => {
    const queue = [root]
    while (queue.length) {
        const n = queue.shift()
        console.log(n.val)
        n.children.forEach(item => {
            queue.push(item)
        })
    }
}
bfs(tree)

运行结果为：
a
b
c
d
e
f
g
符合广度优先遍历