用c语言编写程序,实现基于二叉排序树的查找;(1)输入一组记录,构造一棵二叉排序树,并且输出这棵二叉排序树的中序序列;(2)给定一个关键字值,对所构造的二叉排序树进行查找,并输出查找的结果。输入格式:第一行的n +1个数,每两个整数之间以空格分隔,前面n个数表示n个记录的关键字,最后的数字0表示输入结束。第二行的数表示要查找的记录的关键字值。输出格式:两行数据,第一行的数据表示二叉排序树的中序序列,第二行的数据表示查找结果。
时间: 2024-03-25 10:38:48 浏览: 26
好的,这是一个比较典型的二叉排序树查找问题,我来给你讲解一下。
首先,我们需要定义一个二叉排序树节点的结构体,包括关键字和左右子节点指针。代码如下:
```c
typedef struct BSTNode {
int key;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
```
然后,我们需要实现二叉排序树的插入操作,代码如下:
```c
BSTNode* insert(BSTNode *root, int key) {
if (root == NULL) {
BSTNode *node = (BSTNode *)malloc(sizeof(BSTNode));
node->key = key;
node->left = NULL;
node->right = NULL;
return node;
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
}
return root;
}
```
接着,我们需要实现中序遍历二叉排序树,输出中序序列。代码如下:
```c
void inorder(BSTNode *root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
```
最后,我们需要实现二叉排序树的查找操作,代码如下:
```c
BSTNode* search(BSTNode *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
#include <stdio.h>
#include <stdlib.h>
typedef struct BSTNode {
int key;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
BSTNode* insert(BSTNode *root, int key) {
if (root == NULL) {
BSTNode *node = (BSTNode *)malloc(sizeof(BSTNode));
node->key = key;
node->left = NULL;
node->right = NULL;
return node;
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
}
return root;
}
void inorder(BSTNode *root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
BSTNode* search(BSTNode *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);
}
}
int main() {
int n, key, search_key;
BSTNode *root = NULL;
scanf("%d", &n);
while (n--) {
scanf("%d", &key);
if (key == 0) {
break;
}
root = insert(root, key);
}
scanf("%d", &search_key);
inorder(root);
printf("\n");
BSTNode *result = search(root, search_key);
if (result == NULL) {
printf("Not found\n");
} else {
printf("Found\n");
}
return 0;
}
```
输入格式如下:
```
10 5 3 1 4 8 9 7 6 10 0
8
```
输出格式如下:
```
1 3 4 5 6 7 8 9 10
Found
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)