c语言首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 21:26:28 浏览: 100
好的,让我们逐步来实现该程序。
首先,我们需要定义二叉排序树的结构体,如下所示:
```c
typedef struct Node{
int data;
struct Node *left;
struct Node *right;
}Node;
```
接着,我们需要实现创建二叉排序树的函数,该函数接收一个字符串作为输入,并返回一个指向根节点的指针。具体实现如下:
```c
Node *createBST(char *str){
Node *root = NULL;
while(*str){
if(*str >= '0' && *str <= '9'){
int num = 0;
while(*str >= '0' && *str <= '9'){
num = num * 10 + (*str - '0');
str++;
}
root = insertNode(root, num);
}
else{
str++;
}
}
return root;
}
```
在上述代码中,我们首先定义了一个指向根节点的指针 `root`,并将其初始化为 `NULL`。然后,我们遍历字符串中的每个字符,如果当前字符是数字,则将其转换为整数,并调用 `insertNode` 函数将其插入到二叉排序树中。
接下来,我们需要实现二叉排序树的查找操作。该操作接收一个指向根节点的指针以及待查找的元素值作为输入,并返回一个指向匹配节点的指针。具体实现如下:
```c
Node *searchNode(Node *root, int value){
if(root == NULL || root->data == value){
return root;
}
else if(root->data > value){
return searchNode(root->left, value);
}
else{
return searchNode(root->right, value);
}
}
```
在上述代码中,我们首先判断当前节点是否为空或者是否等于待查找值。如果是,则直接返回当前节点指针。否则,如果待查找值小于当前节点的值,则继续在左子树中查找;否则,在右子树中查找。
接下来,我们需要实现二叉排序树的插入操作。该操作接收一个指向根节点的指针以及待插入的元素值作为输入,并返回一个指向根节点的指针。具体实现如下:
```c
Node *insertNode(Node *root, int value){
if(root == NULL){
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
else if(root->data > value){
root->left = insertNode(root->left, value);
}
else{
root->right = insertNode(root->right, value);
}
return root;
}
```
在上述代码中,我们首先判断当前节点是否为空。如果是,则说明已经找到合适的位置,创建一个新节点并将其返回。否则,如果待插入值小于当前节点的值,则继续在左子树中插入;否则,在右子树中插入。
最后,我们需要实现二叉排序树的删除操作。该操作接收一个指向根节点的指针以及待删除的元素值作为输入,并返回一个指向根节点的指针。具体实现如下:
```c
Node *deleteNode(Node *root, int value){
if(root == NULL){
return root;
}
else if(root->data > value){
root->left = deleteNode(root->left, value);
}
else if(root->data < value){
root->right = deleteNode(root->right, value);
}
else{
if(root->left == NULL){
Node *temp = root->right;
free(root);
return temp;
}
else if(root->right == NULL){
Node *temp = root->left;
free(root);
return temp;
}
Node *temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
Node *minValueNode(Node *node){
Node *current = node;
while(current && current->left != NULL){
current = current->left;
}
return current;
}
```
在上述代码中,我们首先判断当前节点是否为空。如果是,则直接返回。否则,如果待删除值小于当前节点的值,则继续在左子树中删除;否则,在右子树中删除。当找到匹配节点时,我们需要判断其有几个子节点。如果只有一个子节点,则将其子节点替换为当前节点;否则,我们需要找到其右子树中最小的节点,将其值赋给当前节点,并在右子树中删除该节点。
至此,我们已经完成了该程序的所有部分,完整代码如下所示:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node *left;
struct Node *right;
}Node;
Node *createBST(char *str);
Node *searchNode(Node *root, int value);
Node *insertNode(Node *root, int value);
Node *deleteNode(Node *root, int value);
Node *minValueNode(Node *node);
int main(){
char str[100];
printf("请输入一串数字:");
scanf("%s", str);
Node *root = createBST(str);
printf("二叉排序树创建完成!\n");
int choice, value;
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", &value);
if(searchNode(root, value) != NULL){
printf("找到了!\n");
}
else{
printf("未找到!\n");
}
break;
case 2:
printf("请输入待插入值:");
scanf("%d", &value);
root = insertNode(root, value);
printf("插入成功!\n");
break;
case 3:
printf("请输入待删除值:");
scanf("%d", &value);
root = deleteNode(root, value);
printf("删除成功!\n");
break;
case 4:
exit(0);
break;
default:
printf("无效操作!\n");
break;
}
}
return 0;
}
Node *createBST(char *str){
Node *root = NULL;
while(*str){
if(*str >= '0' && *str <= '9'){
int num = 0;
while(*str >= '0' && *str <= '9'){
num = num * 10 + (*str - '0');
str++;
}
root = insertNode(root, num);
}
else{
str++;
}
}
return root;
}
Node *searchNode(Node *root, int value){
if(root == NULL || root->data == value){
return root;
}
else if(root->data > value){
return searchNode(root->left, value);
}
else{
return searchNode(root->right, value);
}
}
Node *insertNode(Node *root, int value){
if(root == NULL){
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
else if(root->data > value){
root->left = insertNode(root->left, value);
}
else{
root->right = insertNode(root->right, value);
}
return root;
}
Node *deleteNode(Node *root, int value){
if(root == NULL){
return root;
}
else if(root->data > value){
root->left = deleteNode(root->left, value);
}
else if(root->data < value){
root->right = deleteNode(root->right, value);
}
else{
if(root->left == NULL){
Node *temp = root->right;
free(root);
return temp;
}
else if(root->right == NULL){
Node *temp = root->left;
free(root);
return temp;
}
Node *temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
Node *minValueNode(Node *node){
Node *current = node;
while(current && current->left != NULL){
current = current->left;
}
return current;
}
```
阅读全文