使用C语言编程有菜单的实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作
时间: 2023-08-21 10:10:57 浏览: 95
以下是使用C语言编写的菜单实现读入一串字符创建一棵二叉排序树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树节点结构体
typedef struct BSTNode {
int data;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
// 二叉排序树的查找操作
BSTNode *BSTSearch(BSTNode *root, int key) {
if (!root || root->data == key) {
return root;
}
if (key < root->data) {
return BSTSearch(root->left, key);
} else {
return BSTSearch(root->right, key);
}
}
// 二叉排序树的插入操作
void BSTInsert(BSTNode **root, int key) {
if (!(*root)) {
BSTNode *newNode = (BSTNode*)malloc(sizeof(BSTNode));
newNode->data = key;
newNode->left = NULL;
newNode->right = NULL;
*root = newNode;
return;
}
if (key < (*root)->data) {
BSTInsert(&((*root)->left), key);
} else {
BSTInsert(&((*root)->right), key);
}
}
// 二叉排序树的删除操作
BSTNode *BSTDelete(BSTNode *root, int key) {
if (!root) {
return root;
}
if (key < root->data) {
root->left = BSTDelete(root->left, key);
} else if (key > root->data) {
root->right = BSTDelete(root->right, key);
} else {
BSTNode *temp;
if (!root->left) {
temp = root->right;
free(root);
return temp;
} else if (!root->right) {
temp = root->left;
free(root);
return temp;
}
temp = root->right;
while (temp->left) {
temp = temp->left;
}
root->data = temp->data;
root->right = BSTDelete(root->right, temp->data);
}
return root;
}
// 二叉排序树的中序遍历操作
void BSTInorder(BSTNode *root) {
if (root) {
BSTInorder(root->left);
printf("%d ", root->data);
BSTInorder(root->right);
}
}
// 菜单的实现
int main() {
BSTNode *root = NULL;
int choice, key;
char str[100];
printf("请输入一串数字,用空格隔开:");
fgets(str, 100, stdin);
char *p = str;
while (*p != '\0') {
if (*p >= '0' && *p <= '9') {
key = atoi(p);
BSTInsert(&root, key);
while (*p >= '0' && *p <= '9') {
p++;
}
} else {
p++;
}
}
do {
printf("\n1. 查找\n2. 插入\n3. 删除\n4. 遍历\n0. 退出\n");
printf("请选择操作:");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("请输入要查找的数:");
scanf("%d", &key);
if (BSTSearch(root, key)) {
printf("找到了\n");
} else {
printf("没找到\n");
}
break;
case 2:
printf("请输入要插入的数:");
scanf("%d", &key);
BSTInsert(&root, key);
break;
case 3:
printf("请输入要删除的数:");
scanf("%d", &key);
root = BSTDelete(root, key);
break;
case 4:
printf("中序遍历结果:");
BSTInorder(root);
printf("\n");
break;
case 0:
printf("再见!\n");
break;
default:
printf("输入有误,请重新输入\n");
break;
}
} while (choice != 0);
return 0;
}
```
该程序先读入一串数字,用空格隔开,然后创建一棵二叉排序树。接着,通过菜单界面,用户可以选择查找、插入、删除、遍历或退出操作。每次操作后,程序会显示相应的结果或提示。
阅读全文