编写c程序,计算二叉树中度为1的结点数
时间: 2024-02-05 12:10:28 浏览: 36
以下是一份计算二叉树中度为1的结点数的C程序:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
int countSingleDegreeNodes(Node *root) {
if (root == NULL) {
return 0;
}
int count = 0;
if (root->left == NULL && root->right != NULL) {
count++;
} else if (root->left != NULL && root->right == NULL) {
count++;
}
count += countSingleDegreeNodes(root->left);
count += countSingleDegreeNodes(root->right);
return count;
}
int main() {
// 构造一棵二叉树
Node *root = (Node*) malloc(sizeof(Node));
root->data = 1;
root->left = (Node*) malloc(sizeof(Node));
root->left->data = 2;
root->left->left = NULL;
root->left->right = (Node*) malloc(sizeof(Node));
root->left->right->data = 3;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (Node*) malloc(sizeof(Node));
root->right->data = 4;
root->right->left = (Node*) malloc(sizeof(Node));
root->right->left->data = 5;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = NULL;
int count = countSingleDegreeNodes(root);
printf("The count of single degree nodes in the binary tree is %d\n", count);
return 0;
}
```
在这个程序中,我们首先定义了一个节点结构体 `Node`,它包括三个成员变量:`data` 存储节点的数据,`left` 存储左子节点的指针,`right` 存储右子节点的指针。
接着,我们实现了一个名为 `countSingleDegreeNodes` 的函数,它用于计算二叉树中度为1的结点数。该函数采用递归的方式遍历二叉树,对于每个节点,如果它的左子树为空但右子树非空,或者它的左子树非空但右子树为空,那么它就是一个度为1的节点,计数器加1。然后分别递归遍历左子树和右子树,将计数器累加起来并返回。
最后,我们在 `main` 函数中构造了一棵二叉树,并调用 `countSingleDegreeNodes` 函数计算其中的度为1的节点数。