极客教程Golang程序 执行后序树形遍历
在Go中，后序树形遍历是一种技术，先访问左边的子节点，然后是右边的子节点，最后是根节点，这就是顺序的定义。这种顺序经常被用来对树进行某些活动，包括释放树所消耗的内存。我们将使用两种方法实现后序树的遍历，第一种方法使用切片，第二种方法使用堆栈。
语法
func append(slice, element_1, element_2…, element_N) []T
append函数用于向一个数组片断添加值。它需要一些参数。第一个参数是我们希望添加的数组，后面是要添加的值。然后，该函数返回包含所有值的数组的最终片断。
方法1：使用分片
在这个方法中，首先检查根节点是否为空。如果是，我们返回一个空的片断。如果不是，我们继续探索左、右子树并将结果添加到我们的结果片中。然后，我们将当前节点的值加入到结果片中，再返回结果片。
算法
- 第1步 – 创建一个包main，并在程序中声明fmt(格式包)和strings包，其中main产生可执行代码，fmt帮助格式化输入和输出。
-
第2步– 创建一个TreeNode结构来表示二叉树的节点。
-
第3步– 创建一个名为post_order_traversal的函数，以后序方式遍历该树。
-
第4步– 验证根节点是否为空。如果是的话，返回一个空的片断。
-
第5步 – 在Left子节点上调用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]
方法2：使用堆栈来实现后序遍历
在这种方法中，为了跟踪后序遍历过程中要访问的节点，我们使用一个堆栈。根节点首先被推到堆栈中。在每次迭代之后，我们从堆栈中删除顶部节点，将其值添加到结果片中，然后再将顶部节点的左右子节点推回堆栈中。通过以这种方式反向访问节点，我们可以通过将数值以适当的后序附加到结果片的前面来建立结果片。
算法
- 第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]
结论
我们用两个例子执行了后序树的遍历程序。在第一个例子中，我们使用结果片来存储左、右子树探索后的结果，在第二个例子中，我们使用堆栈来执行操作