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

归档50

前端基础21 算法11 工具与环境7 框架6 计算机网络3 读书1 随笔1

227 字

1 分钟

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

2025-05-21

算法

二叉树

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

深度优先遍历(DFS)#

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

递归

1
const dfs = (root) => {
2
  if(root === null) return
3
  root.children.forEach(leaf => {
4
    console.log(leaf.val)
5
    dfs(leaf)
6
  })
7
}

栈

1
const dfs = (root) => {
2
  if(root === null) return
3
  const stack = [root]
4
  while(stack.length > 0) {
5
    const node = stack.pop();
6
    console.log(node.val)
7
    node.children.forEach(leaf => {
8
      stack.push(leaf)
9
    })
10
  }
11
}

广度优先遍历(BFS)#

新建一个队列，把根节点入队。
遍历队列
- 把队头出队并访问。
- 把队头的children 挨个入队。

重复2，直到队列为空。

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

4
    const queue = [root];
5

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

10
        node.children.forEach(leaf => {
11
          queue.push(leaf);
12
        });
13
      }
14
    }
15
}