C语言编写给出N(N<1000)个整数,用它们构建一个二叉排序树。请计算以元素K为根的子树节点个数。 输入说明: 第一行输入N和K,第二行输入N个整数。 输出说明:以元素K为根的子树节点个数 输入样例:7 11 12 15 11 8 6 10 3 输出样例:5
时间: 2024-10-04 20:01:42 浏览: 92
在C语言中,你可以通过递归的方式来构建一个二叉搜索树并计算给定元素K作为根的子树节点个数。首先,你需要定义一个结构体表示二叉树节点,包含一个整数值和两个指向左右孩子的指针。然后按照以下步骤操作:
1. 定义一个函数`insert`用于插入节点,将输入的整数与当前根节点比较,如果小于根,向左子树递归插入;大于则向右子树递归插入。
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* insert(TreeNode* root, int val) {
if (root == NULL) {
return (TreeNode*)malloc(sizeof(TreeNode));
}
if (val < root->val) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
```
2. 接着定义一个辅助函数`count_subtree`,它接收当前节点、目标值K以及一个计数器,如果当前节点等于K,则增加计数,并递归地对左、右子树进行同样的操作。
```c
int count_subtree(TreeNode* node, int k, int count) {
if (node == NULL) {
return count;
}
if (node->val == k) {
count++;
}
count += count_subtree(node->left, k, count);
count += count_subtree(node->right, k, count);
return count;
}
```
3. 最后,在主函数中读取输入数据,创建一个空的根节点,然后插入所有数字,并调用`count_subtree`来计算结果。
```c
int main() {
int n, k;
scanf("%d %d", &n, &k);
TreeNode* root = NULL;
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
root = insert(root, num);
}
printf("%d\n", count_subtree(root, k, 0));
return 0;
}
```
当运行程序时,输入样例中的数据会构造一棵特定的二叉搜索树,然后计算出以元素11为根的子树节点数为5,这就是输出样例的答案。
阅读全文