Go語言怎么實(shí)現(xiàn)二叉樹遍歷

這篇文章主要講解了“Go語言怎么實(shí)現(xiàn)二叉樹遍歷”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Go語言怎么實(shí)現(xiàn)二叉樹遍歷”吧！

1. 二叉樹的定義

二叉樹需滿足的條件

① 本身是有序樹

② 樹中包含的各個(gè)節(jié)點(diǎn)的長度不能超過2，即只能是0、1或者2

2. 前序遍歷

前序遍歷二叉樹的順序：根——》左——》右

package main

import "fmt"

//定義結(jié)構(gòu)體
type Student struct {
	Name  string
	Age   int
	Score float32
	left  *Student //左子樹指針
	right *Student //右子樹指針
}

//二叉樹定義
func main() {
	//根節(jié)點(diǎn)
	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

	//調(diào)用遍歷函數(shù)
	Req(&root)

}

//遞歸算法遍歷整個(gè)二叉樹
func Req(tmp *Student) {
	for tmp == nil {
		return
	}
	fmt.Println(tmp)
	//遍歷左子樹
	Req(tmp.left)
	//遍歷右子樹
	Req(tmp.right)
}

輸出結(jié)果如下

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

3. 中序遍歷

中序遍歷：左&mdash;&mdash;》根&mdash;&mdash;》右

package main

import "fmt"

//定義結(jié)構(gòu)體
type Student struct {
	Name  string
	Age   int
	Score float32
	left  *Student //左子樹指針
	right *Student //右子樹指針
}

//二叉樹定義
func main() {
	//根節(jié)點(diǎn)
	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

	//調(diào)用遍歷函數(shù)
	Req(&root)

}

//遞歸算法遍歷整個(gè)二叉樹
func Req(tmp *Student) {
	for tmp == nil {
		return
	}

	//遍歷左子樹
	Req(tmp.left)

	//輸出root節(jié)點(diǎn)
	fmt.Println(tmp)

	//遍歷右子樹
	Req(tmp.right)
}

輸出結(jié)果如下

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

4. 后序遍歷

后序遍歷：左&mdash;&mdash;》右&mdash;&mdash;》根

package main

import "fmt"

//定義結(jié)構(gòu)體
type Student struct {
	Name  string
	Age   int
	Score float32
	left  *Student //左子樹指針
	right *Student //右子樹指針
}

//二叉樹定義
func main() {
	//根節(jié)點(diǎn)
	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

	//調(diào)用遍歷函數(shù)
	Req(&root)

}

//遞歸算法遍歷整個(gè)二叉樹
func Req(tmp *Student) {
	for tmp == nil {
		return
	}

	//遍歷左子樹
	Req(tmp.left)

	//遍歷右子樹
	Req(tmp.right)

	//輸出root節(jié)點(diǎn)
	fmt.Println(tmp)

}

輸出結(jié)果如下

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

感謝各位的閱讀，以上就是“Go語言怎么實(shí)現(xiàn)二叉樹遍歷”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Go語言怎么實(shí)現(xiàn)二叉樹遍歷這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！