使用C语言实现任意输入一组数据作为二叉排序树中结点的键值,创建一棵二叉排序树,然后对给定的值进行查找。
时间: 2024-03-23 14:36:10 浏览: 81
好的,我可以为您解答这个问题。
首先,让我们来了解一下什么是二叉排序树。二叉排序树,也被称为二叉查找树或者二叉搜索树,是一种特殊的二叉树,它的每个节点都包含一个键值,且满足以下条件:
1. 左子树中所有结点的键值都小于根结点的键值。
2. 右子树中所有结点的键值都大于根结点的键值。
3. 左右子树都是二叉排序树。
那么,我们来看一下如何使用C语言实现二叉排序树的创建和查找。
首先,我们需要定义二叉排序树的结构体,包含键值和左右子树指针:
```c
typedef struct Node {
int key;
struct Node* left;
struct Node* right;
} Node;
```
接着,我们可以编写一个函数来创建二叉排序树:
```c
Node* createBST(Node* root, int key) {
if (root == NULL) { // 如果根结点为空,创建新结点
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if (key < root->key) { // 如果键值小于根结点,插入到左子树
root->left = createBST(root->left, key);
} else if (key > root->key) { // 如果键值大于根结点,插入到右子树
root->right = createBST(root->right, key);
}
return root;
}
```
该函数接受两个参数,一个是根结点指针,一个是要插入的键值。如果根结点为空,创建新结点并返回;否则,根据键值的大小关系插入到左子树或右子树中。
接下来,我们可以编写一个函数来查找给定的键值:
```c
Node* search(Node* root, int key) {
if (root == NULL || root->key == key) { // 如果找到了或到达叶子结点,返回结点指针
return root;
}
if (key < root->key) { // 如果键值小于根结点,继续在左子树中查找
return search(root->left, key);
} else { // 如果键值大于根结点,继续在右子树中查找
return search(root->right, key);
}
}
```
该函数接受两个参数,一个是根结点指针,一个是要查找的键值。如果找到了或到达叶子结点,返回结点指针;否则,根据键值的大小关系继续在左子树或右子树中查找。
最后,我们可以编写主函数来测试二叉排序树的创建和查找:
```c
int main() {
Node* root = NULL;
int key;
printf("请输入键值,以-1结束:\n");
while (scanf("%d", &key) && key != -1) { // 循环读入键值,以-1结束
root = createBST(root, key); // 创建二叉排序树
}
printf("请输入要查找的键值:\n");
scanf("%d", &key);
Node* result = search(root, key); // 查找键值
if (result != NULL) {
printf("找到了,结点键值为%d\n", result->key);
} else {
printf("没找到\n");
}
return 0;
}
```
该程序首先读入一组键值,以-1结束,然后创建二叉排序树。接着,读入要查找的键值,然后在二叉排序树中查找。最后,输出查找结果。
希望这个回答能够帮助您解决问题!
阅读全文