编写算法计算出树中度分别为0,1,2的结点数C语言
时间: 2024-11-15 11:21:26 浏览: 17
在C语言中,编写算法来计算树中度为0(叶子节点),1(单分支节点),和2(有两个分支的节点)的数量通常涉及到遍历二叉树的过程。这里提供一种简单的递归方法:
首先,我们定义一个结构体`Node`表示树中的每个节点,包含数据`data`和两个指向左右子节点的指针`left`和`right`。
```c
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
```
接下来,我们可以创建三个计数器变量:`num_zeros`, `num_ones`, 和 `num_twos`,分别对应度为0、1和2的节点。
```c
int num_zeros = 0;
int num_ones = 0;
int num_twos = 0;
void countDegrees(Node* root) {
if (root == NULL) {
return; // 如果遇到空节点,则直接返回
}
// 判断当前节点的度
if (root->left == NULL && root->right == NULL) { // 度为0
num_zeros++;
} else if (root->left != NULL && root->right == NULL || root->left == NULL && root->right != NULL) { // 度为1
num_ones++;
} else if (root->left != NULL && root->right != NULL) { // 度为2
num_twos++;
}
// 递归处理左子树和右子树
countDegrees(root->left);
countDegrees(root->right);
}
```
最后,在主函数中初始化根节点,并调用`countDegrees`函数:
```c
int main() {
Node* root = createYourTree(); // 替换为实际的树节点构造函数
countDegrees(root);
printf("Number of nodes with degree 0: %d\n", num_zeros);
printf("Number of nodes with degree 1: %d\n", num_ones);
printf("Number of nodes with degree 2: %d\n", num_twos);
return 0;
}
```
这个算法假设输入的树是有效的二叉树。如果树不是二叉树,可能需要稍作修改。注意,这里未包含错误处理和输入验证部分,你需要根据实际情况添加这部分代码。同时,`createYourTree()`是你需要自定义的部分,用于创建具体的树结构。
阅读全文