深度/广度优先遍历

深度优先遍历

深度优先遍历，尽可能深的搜索一棵树的分支

算法口诀

访问根节点，
对根节点的children挨个遍历
就是一个递归

const tree = {
    value: 'a',
    children: [
        {
            value: 'b',
            children: [
                {
                    value: 'd',
                    children: []
                },
                {
                    value: 'e',
                    children: [ ]
                }
            ]
        },
        {
            value: 'c',
            children: [
                {
                    value: 'f',
                    children: [
                    ]
                },
                {
                    value: 'g',
                    children: [
                    ]
                }
            ]
        }
    ]
}
const dfs = (root) => {
  console.log(root.value); // a,b,d,e,c,f,g
  root.children.forEach(dfs);
}

广度优先遍历

广度优先遍历，先访问离根节点最近的节点

把深度和广度理解成看书，深度是从目录到标题到内容，看完继续看第二章
广度是先看第一章目录，标题，再看第二章目录，标题；是先把整本书过一篇，再去看内容

算法口诀

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

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

                    ]
                },
                {
                    value: 'g',
                    children: [

                    ]
                }
            ]
        }
    ]
}

// 广度
const bfs = (root) => {

    const queue = [root];

    while(queue.length > 0) {
        const n = queue.shift();
        console.log(n.value); // 
        n.children.forEach((child) => {
            queue.push(child)
        })
    }
}
bfs(tree)