请用C语言编写如下代码,在以二叉链表存储的二叉树中,求度为2的结点的个数
时间: 2024-02-11 16:09:01 浏览: 69
以下是用C语言编写的代码,用于在以二叉链表存储的二叉树中,求度为2的结点的个数:
```c
#include <stdio.h>
#include <stdlib.h>
/* 二叉树的结构体定义 */
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode, *Tree;
/* 求度为2的结点个数 */
int countDegree2(Tree root) {
if (root == NULL) {
return 0;
} else if (root->left != NULL && root->right != NULL) {
/* 当前结点度为2 */
return countDegree2(root->left) + countDegree2(root->right) + 1;
} else {
/* 当前结点度不为2 */
return countDegree2(root->left) + countDegree2(root->right);
}
}
int main() {
/* 构造二叉树 */
Tree root = (Tree)malloc(sizeof(TreeNode));
root->data = 1;
root->left = (Tree)malloc(sizeof(TreeNode));
root->left->data = 2;
root->left->left = NULL;
root->left->right = (Tree)malloc(sizeof(TreeNode));
root->left->right->data = 3;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (Tree)malloc(sizeof(TreeNode));
root->right->data = 4;
root->right->left = (Tree)malloc(sizeof(TreeNode));
root->right->left->data = 5;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (Tree)malloc(sizeof(TreeNode));
root->right->right->data = 6;
root->right->right->left = NULL;
root->right->right->right = NULL;
/* 求度为2的结点个数 */
int count = countDegree2(root);
printf("度为2的结点个数为:%d\n", count);
return 0;
}
```
这段代码首先定义了二叉树的结构体类型,然后实现了一个递归函数 `countDegree2`,用于求以 `root` 为根节点的二叉树中度为2的结点个数。如果当前结点的左右子树均不为空,则当前结点度为2,否则当前结点度不为2。最后,在 `main` 函数中构造了一个二叉树,并使用 `countDegree2` 函数求出度为2的结点个数。
阅读全文