用c语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作
时间: 2023-10-13 08:29:19 浏览: 36
以下是用C语言实现读入一串字符创建一棵二叉排序树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
void insert(TreeNode** root, int val) {
if (*root == NULL) {
*root = (TreeNode*)malloc(sizeof(TreeNode));
(*root)->val = val;
(*root)->left = NULL;
(*root)->right = NULL;
return;
}
if (val < (*root)->val) {
insert(&((*root)->left), val);
} else {
insert(&((*root)->right), val);
}
}
TreeNode* search(TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
}
if (val < root->val) {
return search(root->left, val);
}
return search(root->right, val);
}
TreeNode* findMin(TreeNode* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
void delete(TreeNode** root, int val) {
if (*root == NULL) {
return;
}
if (val < (*root)->val) {
delete(&((*root)->left), val);
} else if (val > (*root)->val) {
delete(&((*root)->right), val);
} else {
if ((*root)->left == NULL) {
TreeNode* temp = *root;
*root = (*root)->right;
free(temp);
} else if ((*root)->right == NULL) {
TreeNode* temp = *root;
*root = (*root)->left;
free(temp);
} else {
TreeNode* minNode = findMin((*root)->right);
(*root)->val = minNode->val;
delete(&((*root)->right), minNode->val);
}
}
}
void printInOrder(TreeNode* root) {
if (root == NULL) {
return;
}
printInOrder(root->left);
printf("%d ", root->val);
printInOrder(root->right);
}
int main() {
TreeNode* root = NULL;
char str[100];
fgets(str, 100, stdin);
char* p = str;
while (*p != '\n') {
int num = 0;
while (*p >= '0' && *p <= '9') {
num = num * 10 + (*p - '0');
p++;
}
insert(&root, num);
p++;
}
printf("In order traversal:\n");
printInOrder(root);
printf("\n");
int val;
printf("Enter a number to search: ");
scanf("%d", &val);
TreeNode* node = search(root, val);
if (node == NULL) {
printf("Not found\n");
} else {
printf("Found\n");
}
printf("Enter a number to delete: ");
scanf("%d", &val);
delete(&root, val);
printf("In order traversal after deletion:\n");
printInOrder(root);
printf("\n");
return 0;
}
```
该代码读入一串字符,每次读取一个数字并插入到二叉排序树中。然后可以进行查找、插入和删除等操作。其中,查找和删除的实现方法比较简单,具体见代码注释。插入操作也比较简单,可以递归地将新节点插入到合适的位置。