資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Go 語言程式：計算樹中葉節點的數量
在 Go 程式語言中，樹是一種資料結構，其中每個節點都有一個值和零到多個子節點。根節點是沒有任何父節點的節點，而葉節點是沒有任何子節點的節點。樹可以用於各種任務，包括在分層結構中儲存、排序和搜尋資料。我們將使用兩種方法來計算樹中葉節點的數量。在第一種方法中使用 TreeNode 結構體，而在第二個示例中使用佇列來執行程式。
方法 1：使用 TreeNode 結構體
此方法實現了 count_leaf_nodes 函式，該函式以根節點作為引數並返回樹中葉節點的數量。它還使用 TreeNode 結構體構建樹資料結構。count_leaf_nodes 函式由 main 函式呼叫以計算已設定的示例樹的葉節點。程式將輸出 4 作為結果。
演算法
步驟 1 − 建立一個名為 main 的包，並在程式中宣告 fmt（格式包）和 strings 包，其中 main 生成可執行程式碼，fmt 幫助格式化輸入和輸出。
步驟 2 − 建立一個名為 TreeNode 的結構體，該結構體具有用於節點值以及指向其左子節點和右子節點的指標的欄位，以表示樹中的節點。
步驟 3 − 建立一個名為 count_leaf_nodes 的函式，該函式以 TreeNode 指標作為引數並返回樹中葉節點的數量。
步驟 4 − 在 count_leaf_nodes 函式中驗證根節點是否為 nil。如果是，則返回 0，因為沒有葉節點。
步驟 5 − 如果根節點不為 nil，則檢查左子節點和右子節點是否為 nil。如果是，則返回 1，因為此節點是葉節點。
步驟 6 − 如果它們不為空，則遞迴呼叫 countLeafNodes 在左子節點和右子節點上，然後返回兩個結果的總和。
步驟 7 − 在 main 函式中建立一個 TreeNode 結構體例項以表示樹的根節點，並將它的左子節點和右子節點設定為其他 TreeNode 結構體例項以表示樹的其餘部分。
步驟 8 − 使用根節點作為引數呼叫 count_leaf_nodes 方法。該函式的輸出將是樹中葉節點的數量。
示例
在此示例中，我們將使用 TreeNode 結構體來實現樹中葉節點的數量。
package main
import "fmt"
type TreeNode struct { //create a TreeNode struct whose values are to be counted
Val int
Left_val *TreeNode
Right_val *TreeNode
}
func count_leaf_nodes(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left_val == nil && root.Right_val == nil {
return 1
}
return count_leaf_nodes(root.Left_val) + count_leaf_nodes(root.Right_val)
}
func main() {
root := &TreeNode{Val: 10,
Left_val: &TreeNode{Val: 20, //assign values to the list
Left_val: &TreeNode{Val: 40,
Left_val: nil,
Right_val: nil,
},
Right_val: &TreeNode{Val: 50,
Left_val: nil,
Right_val: nil,
},
},
Right_val: &TreeNode{Val: 30,
Left_val: &TreeNode{Val: 60,
Left_val: nil,
Right_val: nil,
},
Right_val: &TreeNode{Val: 70,
Left_val: nil,
Right_val: nil,
},
},
}
fmt.Println("The total no. of leaf nodes in the tree are:")
fmt.Println(count_leaf_nodes(root)) // output:4
}
輸出
The total no. of leaf nodes in the tree are: 4
方法 2：使用佇列計算樹中葉節點的數量
此方法使用佇列跟蹤要訪問的下一個節點。在將節點新增到佇列時，它首先新增根節點。然後，它重複地從前面獲取下一個節點，確定它是否是葉節點（即，如果它的左子節點和右子節點為 nil），如果它們不為 nil，則將它的子節點新增到佇列的後面。一個計數變數用於跟蹤葉節點的數量，每次遇到葉節點時都會增加該變數。訪問每個節點後，函式返回計數。
演算法
步驟 1 − 建立一個名為 main 的包，並在程式中宣告 fmt（格式包）和 strings 包，其中 main 生成可執行程式碼，fmt 幫助格式化輸入和輸出。
步驟 2 − 建立一個名為 TreeNode 的結構體，該結構體具有用於節點值以及指向其左子節點和右子節點的指標的欄位，以表示樹中的節點。
步驟 3 − 建立一個名為 count_leaf_nodes 的函式，該函式以 TreeNode 指標作為引數並返回樹中葉節點的數量。
步驟 4 − 建立一個佇列，並將其根節點和計數設定為 0。
步驟 5 −
a. 當佇列仍然包含節點時，從佇列中出隊初始節點。
b. 如果出隊的節點是葉節點（即，如果它的左子節點和右子節點為 nil），則增加計數。
c. 如果出隊的節點的左子節點不為空，則將其入隊。
d. 如果出隊的節點的右子節點不為空，則將其入隊。
步驟 6 − 將計數返回給函式。
步驟 7 − 在 main 函式中建立一個 TreeNode 結構體例項以表示樹的根節點，並將它的左子節點和右子節點設定為其他 TreeNode 結構體例項以表示樹的其餘部分。
示例
在此示例中，我們將使用佇列資料結構來實現程式。
package main
import "fmt"
type TreeNode struct { //create a TreeNode struct whose leaf nodes are to be counted
Val int
Left_val *TreeNode
Right_val *TreeNode
}
func count_leaf_nodes(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root} //use a queue to count no. of leaf nodes
count := 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node.Left_val == nil && node.Right_val == nil {
count++
}
if node.Left_val != nil {
queue = append(queue, node.Left_val)
}
if node.Right_val != nil {
queue = append(queue, node.Right_val)
}
}
return count
}
func main() {
root := &TreeNode{Val: 1,
Left_val: &TreeNode{Val: 2,
Left_val: &TreeNode{Val: 4, //assign the values to the list
Left_val: nil,
Right_val: nil,
},
Right_val: &TreeNode{Val: 5,
Left_val: nil,
Right_val: nil,
},
},
Right_val: &TreeNode{Val: 3,
Left_val: &TreeNode{Val: 6,
Left_val: nil,
Right_val: nil,
},
Right_val: &TreeNode{Val: 7,
Left_val: nil,
Right_val: nil,
},
},
}
fmt.Println("The no. of leaf nodes in the tree are:")
fmt.Println(count_leaf_nodes(root)) //output:4
}
輸出
The no. of leaf nodes in the tree are: 4
結論
我們使用兩個示例執行了計算樹中葉節點數量的程式。在第一個示例中，我們使用 TreeNode 結構體使用樹資料結構，在第二個示例中，我們使用佇列資料結構來執行程式。
352 次瀏覽
