详解Go语言如何实现二叉树遍历

130 阅读 0 评论 86 点赞

我是靠谱客的博主贪玩红牛，这篇文章主要介绍详解Go语言如何实现二叉树遍历，现在分享给大家，希望可以做个参考。

1. 二叉树的定义

二叉树需满足的条件

① 本身是有序树

② 树中包含的各个节点的长度不能超过2，即只能是0、1或者2

2. 前序遍历

前序遍历二叉树的顺序：根——》左——》右

复制代码

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
package main

import "fmt"

//定义结构体
type Student struct {
	Name  string
	Age   int
	Score float32
	left  *Student //左子树指针
	right *Student //右子树指针
}

//二叉树定义
func main() {
	//根节点
	var root Student
	root.Name = "root"
	root.Age = 18
	root.Score = 88

	//一级左子树
	var left1 Student
	left1.Name = "left1"
	left1.Age = 20
	left1.Score = 80

	root.left = &left1

	//一级右子树
	var right1 Student
	right1.Name = "right1"
	right1.Age = 22
	right1.Score = 100

	root.right = &right1

	//二级左子树
	var left2 Student
	left2.Name = "left2"
	left2.Age = 25
	left2.Score = 90

	left1.left = &left2

	//调用遍历函数
	Req(&root)

}

//递归算法遍历整个二叉树
func Req(tmp *Student) {
	for tmp == nil {
		return
	}
	fmt.Println(tmp)
	//遍历左子树
	Req(tmp.left)
	//遍历右子树
	Req(tmp.right)
}

输出结果如下

&{root 18 88 0xc0000c0480 0xc0000c04b0}
&{left1 20 80 0xc0000c04e0 <nil>}
&{left2 25 90 <nil> <nil>}
&{right1 22 100 <nil> <nil>}

3. 中序遍历

中序遍历：左——》根——》右

复制代码

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
63
64
65
package main

import "fmt"

//定义结构体
type Student struct {
	Name  string
	Age   int
	Score float32
	left  *Student //左子树指针
	right *Student //右子树指针
}

//二叉树定义
func main() {
	//根节点
	var root Student
	root.Name = "root"
	root.Age = 18
	root.Score = 88

	//一级左子树
	var left1 Student
	left1.Name = "left1"
	left1.Age = 20
	left1.Score = 80

	root.left = &left1

	//一级右子树
	var right1 Student
	right1.Name = "right1"
	right1.Age = 22
	right1.Score = 100

	root.right = &right1

	//二级左子树
	var left2 Student
	left2.Name = "left2"
	left2.Age = 25
	left2.Score = 90

	left1.left = &left2

	//调用遍历函数
	Req(&root)

}

//递归算法遍历整个二叉树
func Req(tmp *Student) {
	for tmp == nil {
		return
	}

	//遍历左子树
	Req(tmp.left)

	//输出root节点
	fmt.Println(tmp)

	//遍历右子树
	Req(tmp.right)
}

输出结果如下

&{left2 25 90 <nil> <nil>}
&{left1 20 80 0xc000114510 <nil>}
&{root 18 88 0xc0001144b0 0xc0001144e0}
&{right1 22 100 <nil> <nil>}

4. 后序遍历

后序遍历：左——》右——》根

复制代码

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
63
64
65
66
package main

import "fmt"

//定义结构体
type Student struct {
	Name  string
	Age   int
	Score float32
	left  *Student //左子树指针
	right *Student //右子树指针
}

//二叉树定义
func main() {
	//根节点
	var root Student
	root.Name = "root"
	root.Age = 18
	root.Score = 88

	//一级左子树
	var left1 Student
	left1.Name = "left1"
	left1.Age = 20
	left1.Score = 80

	root.left = &left1

	//一级右子树
	var right1 Student
	right1.Name = "right1"
	right1.Age = 22
	right1.Score = 100

	root.right = &right1

	//二级左子树
	var left2 Student
	left2.Name = "left2"
	left2.Age = 25
	left2.Score = 90

	left1.left = &left2

	//调用遍历函数
	Req(&root)

}

//递归算法遍历整个二叉树
func Req(tmp *Student) {
	for tmp == nil {
		return
	}

	//遍历左子树
	Req(tmp.left)

	//遍历右子树
	Req(tmp.right)

	//输出root节点
	fmt.Println(tmp)

}