深度广度优先遍历.md

深度广度优先遍历

深度优先遍历

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

算法口诀

访问根节点，

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