白筱汐

想都是问题,做都是答案

0%

树的广度优先遍历(BFS)

前言

树的广度优先遍历(Breadth-First Search, BFS)是一种用于遍历或搜索树数据结构的算法。
在广度优先遍历中,从根节点开始,按层级顺序逐层访问节点,先访问当前层级的所有节点,然后再访问下一层级的节点。

js代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function bfs(root) {
let queue = [root];
while (queue.length) {
let node = queue.shift();
console.log(node.val);
if (node.children) {
node.children.forEach(child => {
queue.push(child);
})
}
}
}

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

bfs(tree); // a b c d e f g

go代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package main

import "fmt"

type Node struct {
Val string
Child []*Node
}

func newNode(val string) *Node {
return &Node{
Val: val,
Child: make([]*Node, 0),
}
}

func (n *Node) AddChild(children ...*Node) {
n.Child = append(n.Child, children...)
}

func Bfs(root *Node) {
queue := make([]*Node, 0)
queue = append(queue, root)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Println(node.Val)
if len(node.Child) > 0 {
for _, child := range node.Child {
queue = append(queue, child)
}
}
}
}

func main() {
a := newNode("a")
b := newNode("b")
c := newNode("c")
d := newNode("d")
e := newNode("e")
f := newNode("f")
g := newNode("g")
a.AddChild(b, c)
b.AddChild(d, e)
c.AddChild(f, g)

Bfs(a) // a b c d e f g
}