树的深度优先和广度优先遍历

作者:Annan

更新于:几秒前

字数统计:265 字

阅读时长:1 分钟

阅读量:

以看书为例子 深度优先遍历就是看第一章节然后和第一章节内容，然后看完第一章节再看第二章节以及内容。 广度优先遍历就是先看标题>>所有目录>>所有小节>>内容。

深度优先遍历(DFS)

1. 访问根节点。
2. 对根节点的children挨个进行深度优先遍历。

递归

const dfs = (root) => {
  if(root === null) return
  root.children.forEach(leaf => {
    console.log(leaf.val)
    dfs(leaf)
  })
}

栈

const dfs = (root) => {
  if(root === null) return
  const stack = [root]
  while(stack.length > 0) {
    const node = stack.pop();
    console.log(node.val)
    node.children.forEach(leaf => {
      stack.push(leaf)
    })
  }
}

广度优先遍历(BFS)

1. 新建一个队列，把根节点入队。

2. 遍历队列

   • 把队头出队并访问。

   • 把队头的children 挨个入队。

重复2，直到队列为空。

const bfs = (root) => {
    if (!root) return;

    const queue = [root];

    while (queue.length > 0) {
        const node = queue.shift();
        console.log(node.val);

        node.children.forEach(leaf => {
          queue.push(leaf);
        });
    	}
    }
}

Contributors

Annan