資料結構
網路
關係資料庫管理系統 (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 次瀏覽
