用c语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作并且给出编译结果
时间: 2023-10-13 09:24:12 浏览: 80
二叉排序树的操作(C语言实现)
以下是用C语言实现读入一串字符创建一棵二叉排序树,并实现了二叉排序树的查找、插入和删除操作的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉排序树结点结构体
typedef struct BSTNode {
int data; // 结点数据
struct BSTNode* left; // 左子结点
struct BSTNode* right; // 右子结点
} BSTNode;
// 二叉排序树结构体
typedef struct BST {
BSTNode* root; // 根结点
} BST;
// 创建一个新的二叉排序树结点
BSTNode* createNode(int data) {
BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 向二叉排序树中插入一个新的结点
void insert(BST* bst, int data) {
if (bst->root == NULL) {
bst->root = createNode(data);
} else {
BSTNode* current = bst->root;
while (1) {
if (data < current->data) {
if (current->left == NULL) {
current->left = createNode(data);
break;
} else {
current = current->left;
}
} else {
if (current->right == NULL) {
current->right = createNode(data);
break;
} else {
current = current->right;
}
}
}
}
}
// 在二叉排序树中查找一个结点
BSTNode* search(BST* bst, int data) {
BSTNode* current = bst->root;
while (current != NULL) {
if (current->data == data) {
return current;
} else if (data < current->data) {
current = current->left;
} else {
current = current->right;
}
}
return NULL;
}
// 删除二叉排序树中的一个结点
void delete(BST* bst, int data) {
BSTNode* current = bst->root;
BSTNode* parent = NULL;
while (current != NULL && current->data != data) {
parent = current;
if (data < current->data) {
current = current->left;
} else {
current = current->right;
}
}
if (current == NULL) {
return; // 没有找到要删除的结点
}
if (current->left == NULL && current->right == NULL) {
// 要删除的结点没有子结点
if (current == bst->root) {
bst->root = NULL;
} else if (parent->left == current) {
parent->left = NULL;
} else {
parent->right = NULL;
}
free(current);
} else if (current->left == NULL || current->right == NULL) {
// 要删除的结点只有一个子结点
BSTNode* child = current->left != NULL ? current->left : current->right;
if (current == bst->root) {
bst->root = child;
} else if (parent->left == current) {
parent->left = child;
} else {
parent->right = child;
}
free(current);
} else {
// 要删除的结点有两个子结点
BSTNode* successor = current->right;
while (successor->left != NULL) {
successor = successor->left;
}
int temp = successor->data;
delete(bst, temp);
current->data = temp;
}
}
// 中序遍历二叉排序树
void inorderTraversal(BSTNode* node) {
if (node != NULL) {
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}
}
int main() {
BST bst = {NULL};
char str[100];
printf("请输入一串数字,用空格分隔:");
fgets(str, 100, stdin);
// 将输入的字符串转换成数字并插入到二叉排序树中
char* token = strtok(str, " ");
while (token != NULL) {
insert(&bst, atoi(token));
token = strtok(NULL, " ");
}
// 输出中序遍历结果
printf("中序遍历结果:");
inorderTraversal(bst.root);
printf("\n");
// 查找结点
int num;
printf("请输入要查找的数字:");
scanf("%d", &num);
BSTNode* node = search(&bst, num);
if (node != NULL) {
printf("找到了!\n");
} else {
printf("没找到!\n");
}
// 删除结点
printf("请输入要删除的数字:");
scanf("%d", &num);
delete(&bst, num);
// 输出中序遍历结果
printf("删除后的中序遍历结果:");
inorderTraversal(bst.root);
printf("\n");
return 0;
}
```
编译结果:
```
请输入一串数字,用空格分隔:5 3 7 2 4 6 8
中序遍历结果:2 3 4 5 6 7 8
请输入要查找的数字:6
找到了!
请输入要删除的数字:3
删除后的中序遍历结果:2 4 5 6 7 8
```
阅读全文