实验C语言编译实现有菜单的并且首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作
时间: 2023-10-13 16:26:28 浏览: 80
好的,这个实验涉及到二叉排序树的基本操作,需要用到指针和动态内存分配等知识点。我提供一份参考代码,帮助你完成这个实验:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建一个新的节点
TreeNode *newNode(int val) {
TreeNode *node = malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 向二叉排序树中插入一个节点
void insert(TreeNode **root, int val) {
if (*root == NULL) {
*root = newNode(val);
return;
}
if (val < (*root)->val) {
insert(&(*root)->left, val);
} else {
insert(&(*root)->right, val);
}
}
// 在二叉排序树中查找一个节点
TreeNode *find(TreeNode *root, int val) {
if (root == NULL) {
return NULL;
}
if (root->val == val) {
return root;
}
if (val < root->val) {
return find(root->left, val);
} else {
return find(root->right, val);
}
}
// 删除二叉排序树中的一个节点
TreeNode *delete(TreeNode *root, int val) {
if (root == NULL) {
return root;
}
if (val < root->val) {
root->left = delete(root->left, val);
} else if (val > root->val) {
root->right = delete(root->right, val);
} else {
if (root->left == NULL) {
TreeNode *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreeNode *temp = root->left;
free(root);
return temp;
}
TreeNode *temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->val = temp->val;
root->right = delete(root->right, temp->val);
}
return root;
}
// 中序遍历二叉排序树
void inorder(TreeNode *root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
// 主函数
int main() {
TreeNode *root = NULL;
char op;
int val;
while (1) {
printf("请选择操作:\n");
printf("1.插入节点\n");
printf("2.查找节点\n");
printf("3.删除节点\n");
printf("4.中序遍历\n");
printf("5.退出\n");
scanf(" %c", &op);
switch (op) {
case '1':
printf("请输入插入节点的值:");
scanf("%d", &val);
insert(&root, val);
printf("插入成功!\n");
break;
case '2':
printf("请输入查找节点的值:");
scanf("%d", &val);
TreeNode *node = find(root, val);
if (node == NULL) {
printf("未找到该节点!\n");
} else {
printf("已找到该节点!\n");
}
break;
case '3':
printf("请输入删除节点的值:");
scanf("%d", &val);
root = delete(root, val);
printf("删除成功!\n");
break;
case '4':
printf("中序遍历结果为:");
inorder(root);
printf("\n");
break;
case '5':
printf("程序已退出!\n");
return 0;
default:
printf("输入有误,请重新选择!\n");
break;
}
}
return 0;
}
```
在这个实验中,我们用到了一个 `TreeNode` 结构体表示二叉排序树的节点,包含了节点的值以及左右子节点的指针。我们还使用了指向指针的指针来实现插入和删除操作,以及动态内存分配来创建新的节点。最后,我们通过一个死循环的菜单来让用户选择需要执行的操作,完成了这个实验的要求。
阅读全文