資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Go語言實現二叉樹資料結構
在Go語言中，二叉樹是一種樹形資料結構，其中每個節點最多有兩個子節點，分別稱為左子節點和右子節點。Go語言內建的資料結構和操作，例如結構體和指標，可以用來建立二叉樹。樹的節點可以被視為具有欄位的結構體，這些欄位用於儲存每個節點的值以及指向任何左子節點或右子節點的指標。有三種類型的樹遍歷——前序遍歷、中序遍歷和後序遍歷。我們將使用兩種方法來實現二叉樹資料結構。第一種方法使用前序遍歷，第二種方法使用中序遍歷。
方法一：使用前序遍歷
此方法生成一個二叉樹，它有兩個子節點，值分別為20和30，以及一個值為10的根節點。值為20的節點的右子節點的值為50，而值為20的節點的左子節點的值為40。然後列印二叉樹的前序遍歷。讓我們透過程式碼和演算法來理解這個概念。
演算法
步驟1 − 建立一個名為main的包，並在程式中宣告fmt（格式化包），其中main生成可執行程式碼，fmt幫助格式化輸入和輸出。
步驟2 − 建立一個名為Node的結構體，用於表示二叉樹中的一個節點，它具有三個欄位：value、left_val和right_val。Value儲存節點的值，而left_val和right_val分別儲存指向其左子節點和右子節點的指標。
步驟3 − 在main函式中，建立一個值為10的根節點，兩個值為20和30的子節點，並將它們分別指定為根節點的左子節點和右子節點。
步驟4 − 為值為20的節點建立兩個新的子節點，值分別為40和50，作為其左子節點和右子節點。
步驟5 − 建立preorder函式，以進行前序遍歷二叉樹。此函式以節點作為引數，列印節點的值。
步驟6 − 如果當前節點有左子節點和右子節點，則preorder函式會遞迴地呼叫自身來處理這些節點。透過這種方式，函式會對二叉樹中的每個節點進行前序訪問。
步驟7 − 要完成二叉樹的前序遍歷，請在根節點上執行preorder函式。列印訪問的節點的值，按訪問順序列印。
步驟8 − 使用fmt.Println()函式執行列印語句，其中ln表示換行。
示例
在這個例子中，我們將列印前序遍歷。
package main
import "fmt"
type Node struct {
value int
left_val *Node //create and left_val and right_val node
right_val *Node
}
func main() {
root := &Node{value: 10} //assign the linked list required elements
root.left_val = &Node{value: 20}
root.right_val = &Node{value: 30}
root.left_val.left_val = &Node{value: 40}
root.left_val.right_val = &Node{value: 50}
fmt.Println("The pre-order traversal is given as:")
preOrder(root)
}
func preOrder(node *Node) {
if node == nil {
return
}
fmt.Println(node.value)
preOrder(node.left_val)
preOrder(node.right_val)
}
輸出
The pre-order traversal is given as: 10 20 40 50 30
方法二：使用中序遍歷
此方法生成一個二叉樹，它有兩個子節點，值分別為2和6，以及一個值為40的根節點。值為20的節點的右子節點的值為30，而值為20的節點的左子節點的值為10。值為60的節點的右子節點的值為70，而值為60的節點的左子節點的值為50。然後列印二叉樹的中序遍歷。
演算法
步驟1 − 建立一個名為main的包，並在程式中宣告fmt（格式化包），其中main生成可執行程式碼，fmt幫助格式化輸入和輸出。
步驟2 − 建立一個名為Node的結構體，用於表示二叉樹中的一個節點，它具有三個欄位：value、left_val和right_val。Value儲存節點的值，而left_val和right_val分別儲存指向其左子節點和右子節點的指標。
步驟3 − 在main函式中，建立一個值為40的根節點，兩個值為20和60的子節點，並將它們分別指定為根節點的左子節點和右子節點。
步驟4 − 為值為20的節點建立兩個新的子節點，值分別為10和30，作為其左子節點和右子節點。
步驟5 − 為值為60的節點建立另外兩個新的子節點，值分別為50和70，作為其左子節點和右子節點。
步驟6 − 建立inOrder函式，以進行中序遍歷二叉樹。此函式以節點作為引數。
步驟7 − 如果當前節點有左子節點，inOrder函式首先遞迴地呼叫自身來處理該節點。
步驟8 − 然後列印當前節點的值。
步驟9 − 最後，如果當前節點有右子節點，則該方法遞迴地呼叫自身。透過這種方式，該函式會依次訪問二叉樹中的所有節點。
步驟10 − 要開始二叉樹的中序遍歷，請在根節點上呼叫inOrder函式。列印訪問的節點的值，按訪問順序列印。
示例
在這個例子中，我們將列印中序遍歷。
package main
import "fmt"
type Node struct {
value int
left_val *Node //create left_val and right_val elements
right_val *Node
}
func main() {
root := &Node{value: 40} //fill the linked list with the elements
root.left_val = &Node{value: 20}
root.right_val = &Node{value: 60}
root.left_val.left_val = &Node{value: 10}
root.left_val.right_val = &Node{value: 30}
root.right_val.left_val = &Node{value: 50}
root.right_val.right_val = &Node{value: 70}
fmt.Println("The In-order traversal created here is:")
inOrder(root)
}
func inOrder(node *Node) {
if node == nil {
return
}
inOrder(node.left_val)
fmt.Println(node.value)
inOrder(node.right_val)
}
輸出
The In-order traversal created here is: 10 20 30 40 50 60 70
結論
我們使用兩種方法執行了實現二叉樹資料結構的程式。在第一個例子中，我們列印了二叉樹的前序遍歷，在第二個例子中，我們列印了二叉樹的中序遍歷。
2K+ 次瀏覽
