数据结构
网络
关系数据库管理系统 (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 次浏览
