資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學Go語言程式實現中序遍歷
在Go程式語言中，樹是一種常用的資料結構，類似於倒置的樹，節點之間存在父子關係。在樹中，每個節點都有一個值和零個或多個子節點。根節點是沒有父節點的節點，葉子節點是沒有子節點的節點。樹可以用於各種任務，包括在層次結構中儲存、排序和搜尋資料。我們將使用兩種方法來執行中序樹遍歷。
語法
func make ([] type, size, capacity)
Go語言中的`make`函式用於建立陣列/對映，它接受要建立的變數型別、大小和容量作為引數。
func append(slice, element_1, element_2…, element_N) []T
`append`函式用於向陣列切片新增值。它接受多個引數。第一個引數是要向其中新增值的陣列，後跟要新增的值。然後，該函式返回包含所有值的最終陣列切片。
演算法
步驟1 - 建立一個`main`包，並在程式中宣告`fmt`(格式化包)和`strings`包，其中`main`生成可執行程式碼，`fmt`幫助格式化輸入和輸出。
步驟2 - 定義一個`TreeNode`結構體來表示二叉樹節點，其中包含一個值、指向左子節點的指標和指向右子節點的指標。
步驟3 - 定義一個`inorder_traversal`函式，該函式接受指向二叉樹根節點的指標，並返回一個數字切片，表示樹的中序遍歷。
步驟4 - 如果根節點為nil，則`inorder_traversal`函式應返回一個空切片。
步驟5 - 如果根節點不為空，則將對左子節點進行`inorder_traversal`呼叫的結果新增到輸出切片中。
步驟6 - 輸出切片應包含當前節點的值。
步驟7 - 切片對右子節點進行`inorder_traversal`呼叫的結果。
步驟8 - 將輸出切片返回給函式。
步驟9 - 在`main`函式中建立一個二叉樹，並對根節點呼叫`inorder_traversal`。
步驟10 - 使用`fmt.Println()`函式（其中`ln`表示換行）將中序遍歷的結果列印到控制檯。
示例1
在這個例子中，我們使用遞迴來執行程式。
package main
import "fmt"
// Definition for a binary tree node
type TreeNode struct {
Val int
Left_val *TreeNode
Right_val *TreeNode
}
func inorder_traversal(root *TreeNode) []int {
output := make([]int, 0)
if root == nil {
return output
}
output = append(output, inorder_traversal(root.Left_val)...)
output = append(output, root.Val)
output = append(output, inorder_traversal(root.Right_val)...)
return output
}
func main() {
root := &TreeNode{Val: 10}
root.Left_val = &TreeNode{Val: 20}
root.Right_val = &TreeNode{Val: 30}
root.Left_val.Left_val = &TreeNode{Val: 40}
root.Left_val.Right_val = &TreeNode{Val: 50}
output := inorder_traversal(root)
fmt.Println("The inorder traversal is given as:")
fmt.Println(output) //print the inorder tree traversal
}
輸出
The inorder traversal is given as: [40 20 50 10 30]
示例2
在這個例子中，我們將使用棧來實現中序樹遍歷。
package main
import "fmt"
// Definition for a binary tree node
type TreeNode struct {
Val int
Left_val *TreeNode
Right_val *TreeNode
}
func inorder_traversal(root *TreeNode) []int {
result := make([]int, 0)
stack := make([]*TreeNode, 0)
curr := root
for curr != nil || len(stack) > 0 {
for curr != nil {
stack = append(stack, curr)
curr = curr.Left_val
}
curr = stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, curr.Val)
curr = curr.Right_val
}
return result
}
func main() {
root := &TreeNode{Val: 10}
root.Left_val = &TreeNode{Val: 20}
root.Right_val = &TreeNode{Val: 30}
root.Left_val.Left_val = &TreeNode{Val: 40}
root.Left_val.Right_val = &TreeNode{Val: 50}
result := inorder_traversal(root)
fmt.Println("The inorder traversal can be represented as:")
fmt.Println(result) //print the inorder tree traversal
}
輸出
The inorder traversal can be represented as: [40 20 50 10 30]
結論
我們使用兩種方法執行了中序遍歷程式。在第一個示例中，我們使用了遞迴，在第二個示例中，我們使用了棧。
609 次瀏覽
