树的深度与广度优先遍历
文章目录
树结构
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: null
},
{
val: 'e',
children: null
}
]
},
{
val: 'c',
children: [
{
val: 'f',
children: null
},
{
val: 'g',
children: null
}
]
}
]
}

1、深度优先遍历(DFS)
- 访问根节点
- 对根节点的children挨个进行DFS
const dfs = (root) => {
if (!root.val) return
console.log(root.val) // 访问根节点
if (root.children) root.children.forEach(dfs) // 对根节点的children挨个进行dfs
}
dfs(tree)
2、广度优先遍历(BFS)
- 新建一个队列,将根节点入队
- 队头出队并访问
- 队头的children挨个入队
- 重复二、三步直至队列为空
const bfs = (root) => {
const queue = [root] // 1、新建一个队列,将根节点入队
while(queue.length) { // 4、队列为空,跳出循环
const head = queue.shift() // 2、队头出队
console.log(head.val) // 2、访问队头
if (head.children) { // 3、队头的children依次入队
head.children.forEach(child => queue.push(child))
}
}
}
bfs(tree)
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论