用c语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-16 22:33:38 浏览: 20
以下是用C语言实现创建二叉排序树、查找、插入和删除的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node* left;
struct node* right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Node* insertNode(Node* root, int data) {
if (root == NULL) {
root = createNode(data);
}
else if (data < root->data) {
root->left = insertNode(root->left, data);
}
else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}
Node* findMin(Node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
Node* deleteNode(Node* root, int data) {
if (root == NULL) {
return root;
}
else if (data < root->data) {
root->left = deleteNode(root->left, data);
}
else if (data > root->data) {
root->right = deleteNode(root->right, data);
}
else {
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
}
else if (root->left == NULL) {
Node* temp = root;
root = root->right;
free(temp);
}
else if (root->right == NULL) {
Node* temp = root;
root = root->left;
free(temp);
}
else {
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}
Node* search(Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
else if (data < root->data) {
return search(root->left, data);
}
else {
return search(root->right, data);
}
}
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
Node* root = NULL;
int n, data;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter the elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &data);
root = insertNode(root, data);
}
printf("Inorder traversal of BST: ");
inorderTraversal(root);
printf("\n");
printf("Enter the element to be searched: ");
scanf("%d", &data);
Node* searchResult = search(root, data);
if (searchResult == NULL) {
printf("Element not found.\n");
}
else {
printf("Element found.\n");
}
printf("Enter the element to be inserted: ");
scanf("%d", &data);
root = insertNode(root, data);
printf("Inorder traversal of BST after insertion: ");
inorderTraversal(root);
printf("\n");
printf("Enter the element to be deleted: ");
scanf("%d", &data);
root = deleteNode(root, data);
printf("Inorder traversal of BST after deletion: ");
inorderTraversal(root);
printf("\n");
return 0;
}
```
注意:以上代码仅供参考,实际使用时需对代码进行适当修改和优化,以满足实际需求。