极客笔记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步 - 在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步 - 在主函数中创建一个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结构的树数据结构，而在第二个示例中，我们使用了队列数据结构来执行该程序。