用C语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-16 10:24:52 浏览: 83
好的,以下是用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 if (val > (*root)->val) {
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);
} else {
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 && (*root)->right == NULL) {
free(*root);
*root = NULL;
} 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 *temp = findMin((*root)->right);
(*root)->val = temp->val;
delete(&((*root)->right), temp->val);
}
}
}
void print(TreeNode *root) {
if (root != NULL) {
print(root->left);
printf("%d ", root->val);
print(root->right);
}
}
int main() {
TreeNode *root = NULL;
char s[100];
printf("请输入一串数字,以空格分隔:\n");
fgets(s, 100, stdin);
char *p = s;
while (*p != '\0') {
int val = strtol(p, &p, 10);
insert(&root, val);
}
printf("二叉排序树的中序遍历结果为:\n");
print(root);
printf("\n");
printf("请输入要查找的数字:\n");
int val;
scanf("%d", &val);
TreeNode *node = search(root, val);
if (node != NULL) {
printf("%d 存在于二叉排序树中。\n", val);
} else {
printf("%d 不存在于二叉排序树中。\n", val);
}
printf("请输入要插入的数字:\n");
scanf("%d", &val);
insert(&root, val);
printf("插入 %d 后,二叉排序树的中序遍历结果为:\n", val);
print(root);
printf("\n");
printf("请输入要删除的数字:\n");
scanf("%d", &val);
delete(&root, val);
printf("删除 %d 后,二叉排序树的中序遍历结果为:\n", val);
print(root);
printf("\n");
return 0;
}
```
该程序首先读入一串数字,以空格分隔,然后创建一棵二叉排序树。接着实现了二叉排序树的查找、插入和删除操作,并输出中序遍历结果。
阅读全文