编写一段C语言代码:任意输入一组数据作为二叉排序树中结点的键值,创建一棵二叉排序树,然后对给定的值进行查找。 题目分析: (该题考察的是二叉排序树的创建) 二叉排序树以lson-rson形式链式存储,对于二叉排序树,即根结点的左结点均小于根结点,根结点的右子结点都大于根结点(或反之);而在每一次插入一个结点时只需要与根结点比较,若比根结点小,则往左子树上插入,直到某一子树为空时,即该处为插入结点的位置,可以发现,每次插入新节点的位置都是叶结点。
时间: 2024-02-25 18:52:43 浏览: 62
以下是一段C语言代码,实现了任意输入一组数据作为二叉排序树中结点的键值,创建一棵二叉排序树,并对给定的值进行查找:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的结构体
struct BSTNode {
int val;
struct BSTNode *left;
struct BSTNode *right;
};
// 插入节点
struct BSTNode* insert(struct BSTNode* root, int val) {
// 若根节点为空,直接插入
if (root == NULL) {
struct BSTNode *newNode = (struct BSTNode*)malloc(sizeof(struct BSTNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 若插入值小于根节点的值,插入到左子树上
if (val < root->val) {
root->left = insert(root->left, val);
}
// 若插入值大于根节点的值,插入到右子树上
else if (val > root->val) {
root->right = insert(root->right, val);
}
return root;
}
// 查找节点
struct BSTNode* search(struct BSTNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
}
else if (val < root->val) {
return search(root->left, val);
}
else {
return search(root->right, val);
}
}
int main() {
int n, val;
struct BSTNode *root = NULL;
// 输入节点数目
printf("请输入节点数目:");
scanf("%d", &n);
// 输入节点的值,插入到二叉排序树中
printf("请输入节点的值:");
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
// 输入要查找的节点的值
printf("请输入要查找的节点的值:");
scanf("%d", &val);
// 在二叉排序树中查找该节点
struct BSTNode *node = search(root, val);
if (node == NULL) {
printf("没有找到该节点!\n");
}
else {
printf("找到了该节点!\n");
}
return 0;
}
```
在上述代码中,我们定义了一个结构体 `BSTNode` 作为二叉排序树的节点,其中包含了节点的值 `val`,以及左子树指针 `left` 和右子树指针 `right`。我们使用 `insert` 函数插入节点,使用 `search` 函数查找节点。在 `main` 函数中,首先输入节点数目,然后输入每个节点的值,将其插入到二叉排序树中。最后输入要查找的节点的值,使用 `search` 函数在二叉排序树中查找该节点。
阅读全文