数据结构
网络
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 次浏览
