给出N(N<1000)个整数,用它们构建一个二叉排序树。请计算以元素K为根的子树节点个数。 输入说明: 第一行输入N和K,第二行输入N个整数。 输出说明:以元素K为根的子树节点个数 输入样例:7 11 12 15 11 8 6 10 3 输出样例:5 用c语言实现,写出代码
时间: 2024-10-02 10:02:54 浏览: 18
在 C 语言中,我们可以使用递归的方式来实现这个问题。首先,我们需要定义一个结构体表示二叉树节点,并实现插入节点、查找节点以及计算子树大小的功能。这是一个简单的示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 插入节点到二叉排序树
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) {
return (TreeNode*)malloc(sizeof(TreeNode));
}
if (val < root->val) {
root->left = insertIntoBST(root->left, val);
} else {
root->right = insertIntoBST(root->right, val);
}
return root;
}
// 查找给定值的节点,返回非空指针表示找到,NULL表示未找到
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) {
return root;
}
if (root->val > val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
// 计算以给定节点为根的子树大小
int countSubtreeSize(TreeNode* root) {
if (!root) {
return 0;
}
return 1 + countSubtreeSize(root->left) + countSubtreeSize(root->right);
}
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 = insertIntoBST(root, num);
}
// 找到k对应的节点并计算子树大小
TreeNode* node = searchBST(root, k);
if (node) {
printf("%d\n", countSubtreeSize(node));
} else {
printf("0\n"); // 如果没找到k,子树大小为0
}
return 0;
}
```
这个程序首先读取输入的整数列表,然后构建一个二叉排序树。接着,它会查找给定的值 K 并计算其子树的节点数量。