c语言实现用递归算法实现统计二叉树的度为 1 的结点个数
时间: 2024-01-22 17:19:56 浏览: 27
二叉树的度是指一个结点拥有的子树个数,度为 1 的结点只有一个子树。统计二叉树的度为 1 的结点个数可以通过递归遍历二叉树来实现。
具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点的定义
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 统计度为 1 的结点个数
int count(TreeNode *root) {
if (root == NULL) {
return 0;
}
int cnt = 0;
if (root->left != NULL && root->right == NULL || root->left == NULL && root->right != NULL) {
cnt++;
}
cnt += count(root->left);
cnt += count(root->right);
return cnt;
}
int main() {
// 构造二叉树
TreeNode *root = (TreeNode *) malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *) malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode *) malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode *) malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode *) malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = (TreeNode *) malloc(sizeof(TreeNode));
root->right->right->left->val = 6;
root->right->right->left->left = NULL;
root->right->right->left->right = NULL;
root->right->right->right = NULL;
// 统计度为 1 的结点个数
int cnt = count(root);
printf("度为 1 的结点个数为 %d\n", cnt);
return 0;
}
```
运行结果:
```
度为 1 的结点个数为 2
```
这里构造了一个二叉树进行测试,可以根据实际需求来构造不同的二叉树进行测试。