任意输入一组数据作为二叉排序树中结点的键值,创建一棵二叉排序树,然后对给定的值进行查找 C语言
时间: 2024-02-22 14:57:51 浏览: 89
好的,我会尽力回答你的问题。以下是一个示例程序,它可以创建一个二叉排序树并在其中查找给定的键值。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树结点结构体
typedef struct BSTNode {
int key; // 键值
struct BSTNode *left; // 左子树指针
struct BSTNode *right; // 右子树指针
} BSTNode;
// 创建新结点
BSTNode *create_node(int key) {
BSTNode *node = (BSTNode*)malloc(sizeof(BSTNode));
node->key = key;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入结点
BSTNode *insert_node(BSTNode *root, int key) {
if (root == NULL) {
return create_node(key);
}
if (key < root->key) {
root->left = insert_node(root->left, key);
} else if (key > root->key) {
root->right = insert_node(root->right, key);
}
return root;
}
// 查找结点
BSTNode *search_node(BSTNode *root, int key) {
if (root == NULL || root->key == key) {
return root;
}
if (key < root->key) {
return search_node(root->left, key);
} else {
return search_node(root->right, key);
}
}
// 打印二叉排序树
void print_bst(BSTNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->key);
print_bst(root->left);
print_bst(root->right);
}
int main() {
// 创建二叉排序树
BSTNode *root = NULL;
int n;
printf("请输入结点个数:");
scanf("%d", &n);
printf("请输入结点的键值:");
for (int i = 0; i < n; i++) {
int key;
scanf("%d", &key);
root = insert_node(root, key);
}
printf("二叉排序树为:");
print_bst(root);
printf("\n");
// 查找结点
int search_key;
printf("请输入要查找的键值:");
scanf("%d", &search_key);
BSTNode *node = search_node(root, search_key);
if (node == NULL) {
printf("未找到结点 %d\n", search_key);
} else {
printf("已找到结点 %d\n", node->key);
}
return 0;
}
```
这个程序中,我们使用了递归来创建和查找二叉排序树中的结点。`insert_node` 函数用来插入新的结点,`search_node` 函数用来查找指定键值的结点。我们还定义了一个 `print_bst` 函数,用来打印整棵二叉排序树。
在程序运行时,你需要输入结点的个数和每个结点的键值。然后程序会创建一棵二叉排序树,并打印出来。接着,你需要输入要查找的键值,程序会在二叉排序树中查找该结点,并输出查找结果。
希望这个程序可以帮助你理解二叉排序树的创建和查找过程。
阅读全文