白筱汐

想都是问题,做都是答案

0%

树的深度优先遍历(DFS)

前言

树的深度优先遍历(Depth-First Search, DFS)是一种用于遍历或搜索树数据结构的算法。
在深度优先遍历中,从根节点开始,先访问当前节点,然后递归地访问其子节点,直到到达叶子节点。
然后回溯到上一级节点,继续访问其未被访问的子节点。

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
43
44
45
46
47
48
49
50
51
52
53
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd'
},
{
val: 'e'
}
]
},
{
val: 'c',
children: [
{
val: 'f'
},
{
val: 'g'
}
]
}
]
}

// 递归实现
function dfs(root) {
console.log(root.val);
if (root.children) {
root.children.forEach(child => {
dfs(child);
})
}
}

// 栈实现
function dfsStack(root) {
let stack = [root];
while (stack.length > 0) {
let node = stack.pop();
console.log(node.val);
if (node.children) {
const children = node.children;
// 为了保证和递归的访问顺序一致,反向遍历
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i]);
}
}
}
}

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
50
51
52
53
54
55
56
57
58
59
60
61
62
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 Dfs(root *Node) {
fmt.Println(root.Val)
if len(root.Child) > 0 {
for _, child := range root.Child {
Dfs(child)
}
}
}

func DfsStack(root *Node) {
stack := make([]*Node, 0)
stack = append(stack, root)
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(node.Val)
if len(node.Child) > 0 {
for i := len(node.Child) - 1; i >= 0; i-- {
stack = append(stack, node.Child[i])
}
}
}
}

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)

Dfs(a) // a b d e c f g

fmt.Println("--------------")

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