极客教程Golang程序 计算树中叶子节点数量
在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步– 在主函数中创建一个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：使用队列来计算树中叶子节点的数量
这种方法使用一个队列来跟踪下一个要访问的节点。当向队列中添加节点时，它从添加根节点开始。然后，它重复地从前面取下下一个节点，确定它是否是一个叶子节点（也就是说，如果它的左边和右边的子节点是空的），如果它的子节点不是空的，就把它们加到队列的后面。一个count变量，每次遇到叶子节点时都会增加，用来跟踪叶子节点的数量。在访问完每个节点后，该函数返回计数。
算法
- 第1步– 创建一个包main，并在程序中声明fmt（格式包）和strings包，其中main产生可执行代码，fmt帮助格式化输入和输出。
-
第2步– 创建一个名为TreeNode的结构，它有节点值的字段和指向其左右子节点的指针，以代表树中的一个节点。
-
第3步– 创建一个名为count_leaf_nodes的函数，以TreeNode指针为参数，返回树中叶子节点的数量。
-
第4步 – 创建一个队列，并将其根节点和计数设置为0。
-
第5步–
a. 当队列中仍然包含节点时，从队列中删除初始节点。
b. 如果被删除的节点是一个叶子节点（也就是说，如果它的左边和右边的子节点是空的），则增加计数。
c. 如果被排队的节点的左边子节点不是空的，就排队。
d. 如果去排队节点的右边子节点不是空的，就排队。
- 第6步 – 将计数返回给函数。
-
第7步– 在主函数中创建一个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结构的树数据结构，在第二个例子中，我们使用队列数据结构来执行程序。