日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Go?數據結構之二叉樹詳情_Golang

作者：宇宙之一粟 ? 更新時間： 2022-07-01 編程語言

前言：

樹可以有許多不同的形狀，并且它們可以在每個節點允許的子節點數量或它們在節點內組織數據值的方式上有所不同。 而在其中最常用的樹之一是二叉樹。 二叉樹是一棵樹，其中每個節點最多可以有兩個孩子。 一個孩子被識別為左孩子，另一個孩子被識別為右孩子。

二叉樹是一種數據結構，在每個節點下面最多存在兩個其他節點。即一個節點要么連接至一個、兩個節點或不連接其他節點。

樹形結構的深度（也被稱作高度）則被定義為根節點為根節點至某個節點間的最長路徑，而節點的深度則表示當當前節點至樹根節點間的邊數。二叉樹有許多不同的形狀和大小。 形狀取決于節點的數量和節點的鏈接方式。

下圖說明了由九個節點組成的二叉樹的三種不同形狀：

Go 語言實現二叉樹

定義二叉樹的結構

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()函數通過遞歸方式訪問二叉樹的全部節點。

創建二叉樹

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

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 函數：

  • 第一個 if 語句在插入時如果是空樹，就把插入的節點設置為根節點，并創建為?&Tree{nil, v, nil}
  • 第二個 if 語句確定插入值是否已在二叉樹中存在。若存在，函數將直接返回且不執行任何操作
  • 第三個 if 語句檢查插入的值位于當前節點的左孩子節點還是右孩子節點，并插入到相應的位置。
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
}

測試

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)
}

運行結果：

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

原文鏈接：https://blog.51cto.com/yuzhou1su/5278948

欄目分類
最近更新