首先用c语言实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 07:24:12 浏览: 32
好的,下面是完整的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 二叉排序树的查找
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
}
if (root->val > val) {
return searchBST(root->left, val);
}
else {
return searchBST(root->right, val);
}
}
// 二叉排序树的插入
TreeNode* insertBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
if (root->val > val) {
root->left = insertBST(root->left, val);
}
else {
root->right = insertBST(root->right, val);
}
return root;
}
// 寻找以node为根节点的子树中最小的节点
TreeNode* findMin(TreeNode* node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}
// 二叉排序树的删除
TreeNode* deleteBST(TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (root->val > val) {
root->left = deleteBST(root->left, val);
}
else if (root->val < val) {
root->right = deleteBST(root->right, val);
}
else {
if (root->left == NULL) {
TreeNode* right = root->right;
free(root);
return right;
}
else if (root->right == NULL) {
TreeNode* left = root->left;
free(root);
return left;
}
else {
TreeNode* minNode = findMin(root->right);
root->val = minNode->val;
root->right = deleteBST(root->right, minNode->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 s[100];
printf("请输入一串字符:");
scanf("%s", s);
// 将字符转换为数字并插入二叉排序树中
for (int i = 0; s[i] != '\0'; i++) {
int val = s[i] - '0';
root = insertBST(root, val);
}
// 中序遍历二叉排序树并输出
printf("中序遍历结果:");
inorder(root);
printf("\n");
// 查找二叉排序树中的某个值
int target;
printf("请输入要查找的值:");
scanf("%d", &target);
TreeNode* node = searchBST(root, target);
if (node == NULL) {
printf("未找到该值\n");
}
else {
printf("已找到该值\n");
}
// 删除二叉排序树中的某个节点
int del;
printf("请输入要删除的值:");
scanf("%d", &del);
root = deleteBST(root, del);
// 中序遍历二叉排序树并输出
printf("中序遍历结果:");
inorder(root);
printf("\n");
return 0;
}
```
输入一串字符后,程序会将其转换为数字并插入二叉排序树中。然后可以进行查找、插入、删除等操作。最后输出二叉排序树的中序遍历结果。