Hike News
Hike News

Golang資料結構-day15-二元樹(binary tree)

Golang 本文总阅读量次

introduction

結構體會有一些自己的字段(屬性)
但單一節點中定有兩個為自身指針類型的字段，分別指向左子樹及右子樹
binary tree

  • 最上方的節點稱為根節點
  • 最下方未在指向任何節點的節點，稱為葉節點

定義

1
2
3
4
5
6
7
8
9
10
type Student struct {
	//資訊域
	Name  string
	Age   int
	Score float64
	
	//指標域
	Left  *Student
	Right *Student
}
  • 指標域的指針可為nil，不一定要指向其他節點

創建節點並插入子樹

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

type Student struct {
	Name string
	Age int
	score float64
	Left *Student
	Right *Student
}

func main(){
	//創建節點
	var Root *Student = &Student{
		Name : "Tom",
		Age : 20,
		score : 70.0,
	}

	var Left Student = Student{
		Name : "Amy",
		Age : 18,
		score : 60.0,
	}

	//於根節點插入左子樹
	Root.Left = &Left

	var Right *Student = new(Student)
	Right.Name = "Tommy"
	Right.Age = 19
	Right.score = 50

	//於根節點插入右子樹
	Root.Right = Right

	left_2 := Student{
		Name : "Tony",
		Age : 50,
		score : 87.5,
	}

	//於左子樹節點再插入左子樹
	Left.Left = &left_2
}

遍歷二元樹

  • 二元樹可以拆分成無數個小二元樹，使用遞歸解決遍歷問題
  • 深度優先遍歷 : 逐條分支遍歷 [V]
  • 廣度優先遍歷 : 層層向外遍歷

前序遍歷

先遍歷根節點資訊-前序遍歷

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

import "fmt"

type Student struct {
	Name string
	Age int
	score float64
	Left *Student
	Right *Student
}

func traversal(Node *Student){
	
	//設定出口條件：當前節點為空則return
	if Node == nil {
		return
	}
	
	//1.遍歷根節點
	fmt.Println(*Node)
	
	//2.遍歷左子樹
	traversal(Node.Left)
	
	//3.遍歷右子樹
	traversal(Node.Right)
}


func main(){
	var Root *Student = &Student{
		Name : "Tom",
		Age : 20,
		score : 70.0,
	}

	var Left Student = Student{
		Name : "Amy",
		Age : 18,
		score : 60.0,
	}
	Root.Left = &Left

	var Right *Student = new(Student)
	Right.Name = "Tommy"
	Right.Age = 19
	Right.score = 50
	Root.Right = Right

	left_2 := Student{
		Name : "Tony",
		Age : 50,
		score : 87.5,
	}
	Left.Left = &left_2
    
	//遍歷二元樹
	traversal(Root)
}

中序遍歷

先遍歷左(右)子樹節點的資訊，再遍歷根節點-中序遍歷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func traversal(Node *Student){
	
	//設定出口條件：當前節點為空則return
	if Node == nil {
		return
	}
	
	//1.遍歷左子樹
	traversal(Node.Left)
	
	//2.遍歷根節點
	fmt.Println(*Node)
	
	//3.遍歷右子樹
	traversal(Node.Right)
}

後序遍歷

先遍歷左(右)子樹，再遍歷右(左)子樹，最後為根節點資訊-後序遍歷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func traversal(Node *Student){
	
	//設定出口條件：當前節點為空則return
	if Node == nil {
		return
	}
	
	//1.遍歷左子樹
	traversal(Node.Left)
	
	//2.遍歷右子樹
	traversal(Node.Right)
	
	//3.遍歷根節點
	fmt.Println(*Node)
}

tips

  • 根節點再不同時候遍歷，決定了為前序，中序、還是後序遍歷
Golang