数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Go语言程序实现先序遍历二叉树
在 Go 编程语言中，先序遍历是一种树遍历技术，其中首先访问根节点，然后访问左子树，最后访问右子树。它使用一个递归函数，该函数在根节点、左子节点、右子节点以及最后再次访问左子节点上调用自身。当节点为 nil 时，递归的基本情况出现。在本程序中，我们将使用两种方法（TreeNode 结构体和栈）来执行先序遍历。
方法 1：使用 TreeNode 结构体
此方法构建了一个树节点结构，其中包含一个 Value 字段，一个指向左子节点的指针和一个指向右子节点的指针。pre_order_traversal 函数使用指向根节点的指针，以先序方式递归访问树中的根节点、左子树，然后是右子树。main 函数在创建示例树后调用 pre_order_traversal 方法来打印树的先序遍历。
算法
步骤 1 − 创建一个 package main 并声明 fmt（格式化包）包在程序中，其中 main 生成可执行代码，而 fmt 帮助格式化输入和输出。
步骤 2 − 创建一个 TreeNode 结构体，其中包含 int 类型的 value，以及 TreeNode 类型的 left_val 和 right_val。
步骤 3 − 创建一个函数 pre_order_traversal，并在该函数中返回当前节点是否为空。打印当前节点的值。
步骤 4 − 在下一步中，使用当前节点的左子节点作为参数调用 pre_order_traversal 来遍历左子树。
步骤 5 − 使用当前节点的右子节点作为参数调用 pre_order_traversal 来遍历右子树。
步骤 6 − 对于每个子节点，重复步骤 1-4，直到所有节点都被访问。
步骤 7 − 此算法通过递归遍历树，首先访问根节点，然后访问左子树，最后访问右子树。当树的一个分支结束或所有节点都被访问时，递归结束。
示例
在本示例中，我们将使用 TreeNode 结构体来实现先序遍历。让我们看一下代码。
package main
import "fmt"
// Define a tree node structure
type TreeNode struct {
Value int
Left_val *TreeNode
Right_val *TreeNode
}
// Function to traverse the tree in pre-order
func pre_order_traversal(root *TreeNode) {
if root == nil {
return
}
fmt.Print(root.Value, " ")
pre_order_traversal(root.Left_val)
pre_order_traversal(root.Right_val)
}
func main() {
// Create a tree
root := &TreeNode{Value: 10}
root.Left_val = &TreeNode{Value: 20}
root.Right_val = &TreeNode{Value: 30}
root.Left_val.Left_val = &TreeNode{Value: 40}
root.Left_val.Right_val = &TreeNode{Value: 50}
// Call the pre-order traversal function
fmt.Print("Pre-order traversal: ")
pre_order_traversal(root)
fmt.Println()
}
输出
Pre-order traversal: 10 20 40 50 30
方法 2：使用栈
此方法使用栈来跟踪需要访问的节点。该方法重复执行以下操作：从栈中删除一个节点，打印其值，并按顺序将它的右子节点和左子节点压入栈中。栈以根节点开始。这会导致树的先序遍历，其中每个节点的左子节点在它的右子节点之前被检查。
算法
步骤 1 − 创建一个 package main 并声明 fmt（格式化包）包在程序中，其中 main 生成可执行代码，而 fmt 帮助格式化输入和输出。
步骤 2 − 创建一个 TreeNode 结构体，其中包含 int 类型的 value，以及 TreeNode 类型的 left_val 和 right_val。
步骤 3 − 创建一个函数 pre_order_traversal，并在该函数中返回根节点是否为空。
步骤 4 − 在下一步中，从根节点向上创建一个栈。
步骤 5 − 通过检查栈的长度是否大于 0 来运行循环，并在栈仍然满的情况下重复执行以下操作 −
a. 从栈顶删除节点并将其分配给名为 curr 的变量。
b. 打印当前值。
步骤 6 − 在 main 函数中，将调用该函数，并使用 fmt.Println() 函数执行打印语句，其中 ln 表示换行。
示例
在本示例中，我们将使用栈来演示先序遍历。让我们通过代码查看执行过程。
package main
import (
"fmt"
)
// Define a tree node structure
type TreeNode struct {
Value int
Left_val *TreeNode
Right_val *TreeNode
}
// Traverse the tree in pre-order using a stack
func pre_order_traversal(root *TreeNode) {
if root == nil {
return
}
stack := []*TreeNode{root}
for len(stack) > 0 {
curr := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Print(curr.Value, " ")
if curr.Right_val != nil {
stack = append(stack, curr.Right_val)
}
if curr.Left_val != nil {
stack = append(stack, curr.Left_val)
}
}
}
func main() {
// Create a tree
root := &TreeNode{Value: 10}
root.Left_val = &TreeNode{Value: 20}
root.Right_val = &TreeNode{Value: 30}
root.Left_val.Left_val = &TreeNode{Value: 40}
root.Left_val.Right_val = &TreeNode{Value: 50}
// Call the pre-order traversal function
fmt.Print("Pre-order traversal: ")
pre_order_traversal(root)
fmt.Println()
}
输出
Pre-order traversal: 10 20 40 50 30
结论
我们使用两个示例执行了上述程序。在第一个示例中，我们使用了 TreeNode 结构体，在第二个示例中，我们使用了 TreeNode 结构体上的栈来演示先序遍历。
882 次浏览
