首先C语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 19:19:06 浏览: 100
下面是实现二叉排序树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *lchild, *rchild;
} Node;
Node *createNode(int data) {
Node *p = (Node *) malloc(sizeof(Node));
p->data = data;
p->lchild = NULL;
p->rchild = NULL;
return p;
}
void insert(Node **root, int data) {
if (*root == NULL) {
*root = createNode(data);
return;
}
if (data < (*root)->data) {
insert(&((*root)->lchild), data);
} else {
insert(&((*root)->rchild), data);
}
}
Node *search(Node *root, int data) {
if (root == NULL) {
return NULL;
}
if (root->data == data) {
return root;
}
if (data < root->data) {
return search(root->lchild, data);
} else {
return search(root->rchild, data);
}
}
void delete(Node **root, int data) {
if (*root == NULL) {
return;
}
if (data < (*root)->data) {
delete(&((*root)->lchild), data);
} else if (data > (*root)->data) {
delete(&((*root)->rchild), data);
} else {
if ((*root)->lchild == NULL && (*root)->rchild == NULL) {
free(*root);
*root = NULL;
} else if ((*root)->lchild == NULL) {
Node *temp = *root;
*root = (*root)->rchild;
free(temp);
} else if ((*root)->rchild == NULL) {
Node *temp = *root;
*root = (*root)->lchild;
free(temp);
} else {
Node *temp = (*root)->rchild;
while (temp->lchild != NULL) {
temp = temp->lchild;
}
(*root)->data = temp->data;
delete(&((*root)->rchild), temp->data);
}
}
}
void inorder(Node *root) {
if (root == NULL) {
return;
}
inorder(root->lchild);
printf("%d ", root->data);
inorder(root->rchild);
}
int main() {
Node *root = NULL;
char str[100];
printf("请输入一串数字,以空格隔开:\n");
fgets(str, 100, stdin);
char *p = str;
while (*p != '\0') {
int data = strtol(p, &p, 10);
insert(&root, data);
}
printf("中序遍历结果:");
inorder(root);
printf("\n");
int choice, data;
while (1) {
printf("请输入操作编号:\n");
printf("1.查找\n");
printf("2.插入\n");
printf("3.删除\n");
printf("4.退出\n");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("请输入要查找的数字:");
scanf("%d", &data);
Node *p = search(root, data);
if (p == NULL) {
printf("未找到该数字!\n");
} else {
printf("找到了数字 %d!\n", p->data);
}
break;
case 2:
printf("请输入要插入的数字:");
scanf("%d", &data);
insert(&root, data);
printf("插入成功!\n");
break;
case 3:
printf("请输入要删除的数字:");
scanf("%d", &data);
delete(&root, data);
printf("删除成功!\n");
break;
case 4:
return 0;
default:
printf("请输入正确的操作编号!\n");
}
printf("中序遍历结果:");
inorder(root);
printf("\n");
}
}
```
注意,以上代码中的 `fgets()` 函数可以读入一行字符串,将其转换为一串数字。在读入字符串时,我们可以使用 `strtol()` 函数将字符串转换为数字,同时移动指针 `p` 的位置。具体可以参考代码中的实现。
阅读全文