前言：

樹可以有許多不同的形狀，并且它們可以在每個(gè)節(jié)點(diǎn)允許的子節(jié)點(diǎn)數(shù)量或它們?cè)诠?jié)點(diǎn)內(nèi)組織數(shù)據(jù)值的方式上有所不同。 而在其中最常用的樹之一是二叉樹。 二叉樹是一棵樹，其中每個(gè)節(jié)點(diǎn)最多可以有兩個(gè)孩子。 一個(gè)孩子被識(shí)別為左孩子，另一個(gè)孩子被識(shí)別為右孩子。

二叉樹是一種數(shù)據(jù)結(jié)構(gòu)，在每個(gè)節(jié)點(diǎn)下面最多存在兩個(gè)其他節(jié)點(diǎn)。即一個(gè)節(jié)點(diǎn)要么連接至一個(gè)、兩個(gè)節(jié)點(diǎn)或不連接其他節(jié)點(diǎn)。

樹形結(jié)構(gòu)的深度（也被稱作高度）則被定義為根節(jié)點(diǎn)為根節(jié)點(diǎn)至某個(gè)節(jié)點(diǎn)間的最長(zhǎng)路徑，而節(jié)點(diǎn)的深度則表示當(dāng)當(dāng)前節(jié)點(diǎn)至樹根節(jié)點(diǎn)間的邊數(shù)。二叉樹有許多不同的形狀和大小。 形狀取決于節(jié)點(diǎn)的數(shù)量和節(jié)點(diǎn)的鏈接方式。

下圖說明了由九個(gè)節(jié)點(diǎn)組成的二叉樹的三種不同形狀：

Go 語(yǔ)言實(shí)現(xiàn)二叉樹

定義二叉樹的結(jié)構(gòu)

package main
import (
"fmt"
"math/rand"
"time"
)
type Tree struct {
Left *Tree
Value int
Right *Tree
}

二叉樹遍歷

func traverse(t *Tree) {
if t == nil {
return
}
traverse(t.Left)
fmt.Print(t.Value, " ")
traverse(t.Right)
}

traverse()函數(shù)通過遞歸方式訪問二叉樹的全部節(jié)點(diǎn)。

創(chuàng)建二叉樹

利用create()函數(shù)利用隨機(jī)整數(shù)填寫二叉樹：

func create(n int) *Tree {
var t *Tree
rand.Seed(time.Now().Unix())
for i := 0; i < 2 * n; i++ {
temp := rand.Intn(n * 2)
t = insert(t, temp)
}
return t
}

插入值

insert 函數(shù)：

• 第一個(gè) if 語(yǔ)句在插入時(shí)如果是空樹，就把插入的節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)，并創(chuàng)建為 &Tree{nil, v, nil}
• 第二個(gè) if 語(yǔ)句確定插入值是否已在二叉樹中存在。若存在，函數(shù)將直接返回且不執(zhí)行任何操作
• 第三個(gè) if 語(yǔ)句檢查插入的值位于當(dāng)前節(jié)點(diǎn)的左孩子節(jié)點(diǎn)還是右孩子節(jié)點(diǎn)，并插入到相應(yīng)的位置。

func insert(t *Tree, v int) *Tree {
if t == nil {
return &Tree{nil, v, nil}
}
if v == t.Value {
return t
}
if v < t.Value {
t.Left = insert(t.Left, v)
return t
}
t.Right = insert(t.Right, v)
return t
}

測(cè)試

package main
import (
"fmt"
"math/rand"
"time"
)
type Tree struct {
Left *Tree
Value int
Right *Tree
}
func traverse(t *Tree) {
if t == nil {
return
}
traverse(t.Left)
fmt.Print(t.Value, " ")
traverse(t.Right)
}
func create(n int) *Tree {
var t *Tree
rand.Seed(time.Now().Unix())
for i := 0; i < 2*n; i++ {
temp := rand.Intn(n * 2)
t = insert(t, temp)
}
return t
}
func insert(t *Tree, v int) *Tree {
if t == nil {
return &Tree{nil, v, nil}
}
if v == t.Value {
return t
}
if v < t.Value {
t.Left = insert(t.Left, v)
return t
}
t.Right = insert(t.Right, v)
return t
}
func main() {
tree := create(10)
fmt.Println("The value of the root of the tree is", tree.Value)
traverse(tree)
fmt.Println()
tree = insert(tree, -10)
tree = insert(tree, -2)
traverse(tree)
fmt.Println()
fmt.Println("The value of the boot of the the tree is", tree.Value)
}

運(yùn)行結(jié)果：

The value of the root of the tree is 18
0 1 4 5 6 8 9 10 12 14 15 18 19
-10 -2 0 1 4 5 6 8 9 10 12 14 15 18 19
The value of the boot of the the tree is 18

到此這篇關(guān)于 Go 數(shù)據(jù)結(jié)構(gòu)之二叉樹詳情的文章就介紹到這了,更多相關(guān) Go 二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論