[已解决]数据结构，树的操作

WY0708

请问大家，求一颗树中（不一定是二叉树）度为二的结点个数，怎么用C语言实现？

最佳答案

月排行榜 / 总排行榜

Mike_python小

2023-11-13 18:39:15

使用C语言计算树中度为二的结点个数

要计算一棵树中度为二的节点个数，可以使用深度优先搜索（DFS）的方式遍历整棵树。对于每个节点，我们需要统计其子节点或者子树中度为二的节点个数。

首先，我们需要定义树的数据结构，可以使用指针来表示树节点：

2. #include <stdio.h>
3. #include <stdlib.h>
5. struct TreeNode {
6.     int val;
7.     struct TreeNode** children; // 指向子节点的指针数组
8.     int numChildren; // 子节点的数量
9. };

复制代码

接下来，我们可以编写一个递归函数来计算度为二的节点个数。该函数遍历当前节点的子节点，并递归地调用自身以计算子节点或子树中度为二的节点个数。对于当前节点，如果其子节点数量等于2，则将结果计数器加一。

2. int countDegreeTwoNodes(struct TreeNode* root) {
3.     if (root == NULL) {
4.         return 0;
5.     }
7.     int count = 0;
9.     // 遍历当前节点的子节点
10.     for (int i = 0; i < root->numChildren; i++) {
11.         count += countDegreeTwoNodes(root->children[i]);
12.     }
14.     // 判断当前节点的子节点数量是否为2
15.     if (root->numChildren == 2) {
16.         count++;
17.     }
19.     return count;
20. }

复制代码

最后，在主函数中，我们可以构建树并调用上述函数来计算度为二的节点个数。

2. int main() {
3.     // 构建树结构并初始化
5.     // 调用计算函数
6.     int result = countDegreeTwoNodes(root);
7.     printf("度为二的节点个数为: %d\n", result);
9.     return 0;
10. }

复制代码

通过以上代码，我们可以实现统计树中度为二的节点个数的功能。希望对你有所帮助。如果还有其他问题，请随时提问。

跳转到最佳答案楼层

isdkz

你可以通过遍历树的方式来实现。以下是一个使用C语言的示例代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. struct TreeNode {
   
5.     int data;
   
6.     struct TreeNode *left;
   
7.     struct TreeNode *right;
   
8. };
   
9. 
   
10. int countNodesWithDegreeTwo(struct TreeNode *root) {
    
11.     if (root == NULL) {
    
12.         return 0;
    
13.     }
    
14.     int count = 0;
    
15.     if (root->left != NULL && root->right != NULL) {
    
16.         count = 1;
    
17.     }
    
18.     return count + countNodesWithDegreeTwo(root->left) + countNodesWithDegreeTwo(root->right);
    
19. }
    
20. 
    
21. int main() {
    
22.     // 创建树并初始化
    
23.     struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    
24.     root->data = 1;
    
25.     root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    
26.     root->left->data = 2;
    
27.     root->left->left = NULL;
    
28.     root->left->right = NULL;
    
29.     root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    
30.     root->right->data = 3;
    
31.     root->right->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    
32.     root->right->left->data = 4;
    
33.     root->right->left->left = NULL;
    
34.     root->right->left->right = NULL;
    
35.     root->right->right = NULL;
    
36. 
    
37.     int result = countNodesWithDegreeTwo(root);
    
38.     printf("度为二的结点个数为: %d\n", result);
    
39. 
    
40.     // 释放内存
    
41.     free(root->left);
    
42.     free(root->right->left);
    
43.     free(root->right);
    
44.     free(root);
    
45. 
    
46.     return 0;
    
47. }
    

复制代码

这段代码定义了一个树的结构，然后使用递归的方式遍历树，统计具有度为二的节点的个数。在这个例子中，我们假设树的节点包含整数数据。

Mike_python小

使用C语言计算树中度为二的结点个数

要计算一棵树中度为二的节点个数，可以使用深度优先搜索（DFS）的方式遍历整棵树。对于每个节点，我们需要统计其子节点或者子树中度为二的节点个数。

首先，我们需要定义树的数据结构，可以使用指针来表示树节点：

2. #include <stdio.h>
3. #include <stdlib.h>
5. struct TreeNode {
6.     int val;
7.     struct TreeNode** children; // 指向子节点的指针数组
8.     int numChildren; // 子节点的数量
9. };

复制代码

接下来，我们可以编写一个递归函数来计算度为二的节点个数。该函数遍历当前节点的子节点，并递归地调用自身以计算子节点或子树中度为二的节点个数。对于当前节点，如果其子节点数量等于2，则将结果计数器加一。

2. int countDegreeTwoNodes(struct TreeNode* root) {
3.     if (root == NULL) {
4.         return 0;
5.     }
7.     int count = 0;
9.     // 遍历当前节点的子节点
10.     for (int i = 0; i < root->numChildren; i++) {
11.         count += countDegreeTwoNodes(root->children[i]);
12.     }
14.     // 判断当前节点的子节点数量是否为2
15.     if (root->numChildren == 2) {
16.         count++;
17.     }
19.     return count;
20. }

复制代码

最后，在主函数中，我们可以构建树并调用上述函数来计算度为二的节点个数。

2. int main() {
3.     // 构建树结构并初始化
5.     // 调用计算函数
6.     int result = countDegreeTwoNodes(root);
7.     printf("度为二的节点个数为: %d\n", result);
9.     return 0;
10. }

复制代码

通过以上代码，我们可以实现统计树中度为二的节点个数的功能。希望对你有所帮助。如果还有其他问题，请随时提问。