首先用c语言实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 11:10:02 浏览: 91
下面是C语言实现读入一串字符创建一棵二叉排序树的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉排序树的结点结构体
typedef struct TreeNode {
int data; // 结点数据
struct TreeNode* left; // 左子结点指针
struct TreeNode* right; // 右子结点指针
} TreeNode;
// 插入结点操作
TreeNode* insert(TreeNode* root, int data) {
if (root == NULL) {
// 如果根结点为空,则新建一个结点作为根结点
root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = data;
root->left = NULL;
root->right = NULL;
} else if (data < root->data) {
// 如果新插入的数据小于根结点的数据,则插入到左子树中
root->left = insert(root->left, data);
} else {
// 如果新插入的数据大于等于根结点的数据,则插入到右子树中
root->right = insert(root->right, data);
}
return root;
}
// 查找结点操作
TreeNode* search(TreeNode* root, int data) {
if (root == NULL) {
// 如果根结点为空,则返回NULL表示未找到
return NULL;
} else if (data == root->data) {
// 如果当前结点的数据等于要查找的数据,则返回当前结点
return root;
} else if (data < root->data) {
// 如果要查找的数据小于当前结点的数据,则在左子树中查找
return search(root->left, data);
} else {
// 如果要查找的数据大于当前结点的数据,则在右子树中查找
return search(root->right, data);
}
}
// 删除结点操作
TreeNode* delete(TreeNode* root, int data) {
if (root == NULL) {
// 如果根结点为空,则返回NULL表示未找到
return NULL;
} else if (data < root->data) {
// 如果要删除的数据小于当前结点的数据,则在左子树中删除
root->left = delete(root->left, data);
} else if (data > root->data) {
// 如果要删除的数据大于当前结点的数据,则在右子树中删除
root->right = delete(root->right, data);
} else {
// 如果当前结点的数据等于要删除的数据
if (root->left == NULL && root->right == NULL) {
// 如果当前结点没有子结点,则直接删除
free(root);
root = NULL;
} else if (root->left == NULL) {
// 如果当前结点只有右子结点,则用右子结点代替当前结点
TreeNode* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) {
// 如果当前结点只有左子结点,则用左子结点代替当前结点
TreeNode* temp = root;
root = root->left;
free(temp);
} else {
// 如果当前结点既有左子结点又有右子结点,则找到右子树中最小的结点代替当前结点
TreeNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
}
return root;
}
// 中序遍历二叉排序树
void inorder(TreeNode* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
TreeNode* root = NULL;
int n, data;
printf("请输入结点个数:");
scanf("%d", &n);
printf("请输入每个结点的数据:");
for (int i = 0; i < n; i++) {
scanf("%d", &data);
root = insert(root, data);
}
printf("中序遍历二叉排序树:");
inorder(root);
printf("\n请输入要查找的数据:");
scanf("%d", &data);
TreeNode* node = search(root, data);
if (node != NULL) {
printf("已找到结点,数据为%d\n", node->data);
} else {
printf("未找到结点\n");
}
printf("请输入要插入的数据:");
scanf("%d", &data);
root = insert(root, data);
printf("中序遍历二叉排序树:");
inorder(root);
printf("\n请输入要删除的数据:");
scanf("%d", &data);
root = delete(root, data);
printf("中序遍历二叉排序树:");
inorder(root);
return 0;
}
```
示例输入:
```
请输入结点个数:7
请输入每个结点的数据:5 3 7 2 4 6 8
请输入要查找的数据:4
请输入要插入的数据:1
请输入要删除的数据:5
```
示例输出:
```
中序遍历二叉排序树:2 3 4 5 6 7 8
已找到结点,数据为4
中序遍历二叉排序树:1 2 3 4 5 6 7 8
中序遍历二叉排序树:1 2 3 4 6 7 8
```
阅读全文