数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Go语言程序实现后序树遍历
在Go语言中，后序树遍历是一种先访问左子树，再访问右子树，最后访问根节点的技术。这种顺序常用于在树上执行某些操作，例如释放树已使用的内存。我们将使用两种方法实现后序树遍历：第一种使用切片，第二种使用栈。
语法
func append(slice, element_1, element_2…, element_N) []T
append函数用于向数组切片添加值。它接受多个参数。第一个参数是要添加值的数组，后面跟着要添加的值。然后，该函数返回包含所有值的最终数组切片。
方法一：使用切片
在此方法中，首先检查根节点是否为空。如果是，则返回空切片。如果不是，则继续遍历左子树和右子树，并将结果添加到结果切片中。然后，在将当前节点的值添加到结果之后，返回结果切片。
算法
步骤1 − 创建一个名为main的包，并在程序中声明fmt（格式化包）和strings包，其中main生成可执行代码，fmt帮助格式化输入和输出。
步骤2 − 创建一个TreeNode结构体来表示二叉树的节点。
步骤3 − 创建一个名为post_order_traversal的函数来后序遍历树。
步骤4 − 检查根节点是否为空。如果是，则返回空切片。
步骤5 − 对左子节点调用post_order_traversal函数来迭代遍历左子树。
步骤6 − 对右子节点调用post_order_traversal函数来迭代遍历右子树。
步骤7 − 将当前节点的值添加到结果切片中。
步骤8 − 返回结果切片。
步骤9 − 后序遍历函数递归地遍历树，将结果记录在切片中。该函数按遇到的顺序将节点的值添加到结果切片中，即后序遍历顺序。
示例
在这个示例中，我们将使用切片来存储在遍历左子树和右子树之后的结果。
package main
import "fmt"
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left_val *TreeNode
Right_val *TreeNode
}
func post_order_traversal(root *TreeNode) []int {
var result []int
if root == nil {
return result
}
result = append(result, post_order_traversal(root.Left_val)...)
result = append(result, post_order_traversal(root.Right_val)...)
result = append(result, root.Val)
return result
}
func main() {
root := &TreeNode{Val: 10} //assign values to the list
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 := post_order_traversal(root)
fmt.Println("The postorder traversal is created here:")
fmt.Println(result) //print the postorder traversal
}
输出
The postorder traversal is created here: [40 50 20 30 10]
方法二：使用栈实现后序遍历
在此方法中，我们使用栈来跟踪后序遍历期间要访问的节点。首先将根节点压入栈中。每次迭代后，我们从栈中弹出顶节点，将其值添加到结果切片中，然后将顶节点的右子节点和左子节点压回栈中。通过这种方式反向访问节点，我们可以通过将值添加到结果切片的前端来构建结果切片，从而得到正确的后序遍历顺序。
算法
步骤1 − 创建一个名为main的包，并在程序中声明fmt（格式化包）和strings包，其中main生成可执行代码，fmt帮助格式化输入和输出。
步骤2 − 创建一个TreeNode结构体来表示二叉树的节点。
步骤3 − 创建一个名为post_order_traversal的函数来后序遍历树。
步骤4 − 检查根节点是否为空。如果是，则返回空切片。
步骤5 − 从头创建一个栈，并将根节点添加到其中。
步骤6 − 重复这些步骤，直到栈为空。
a. 从栈中弹出顶节点。
b. 将节点的值作为前缀添加到结果切片中。
c. 将左子节点和右子节点添加到栈中。
步骤7 − 返回切片的结果
步骤8 − 使用fmt.Println()函数（其中ln表示换行）将结果打印到控制台。
示例
在这个示例中，我们将使用栈来实现后序遍历。
package main
import "fmt"
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left_val *TreeNode
Right_val *TreeNode
}
func post_order_traversal(root *TreeNode) []int {
var result []int
if root == nil {
return result
}
stack := []*TreeNode{root}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append([]int{node.Val}, result...)
if node.Left_val != nil {
stack = append(stack, node.Left_val)
}
if node.Right_val != nil {
stack = append(stack, node.Right_val)
}
}
return result
}
func main() {
root := &TreeNode{Val: 10} //assign the values to the list
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 := post_order_traversal(root)
fmt.Println("The postorder traversal created here is:")
fmt.Println(result)
}
输出
The postorder traversal created here is: [40 50 20 30 10]
结论
我们使用两个例子执行了后序树遍历程序。在第一个例子中，我们使用结果切片来存储在遍历左子树和右子树之后的结果；在第二个例子中，我们使用栈来执行此操作。
192 次浏览
