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