首先用c语言实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 14:06:10 浏览: 61
好的,以下是实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的结构体
typedef struct BST {
int data;
struct BST *left, *right;
} BST;
// 插入节点
BST* insertNode(BST *root, int data) {
// 如果根节点为空,则新建一个节点并返回
if (root == NULL) {
root = (BST*) malloc(sizeof(BST));
root->data = data;
root->left = root->right = NULL;
return root;
}
// 如果插入的值小于当前节点的值,则插入到左子树
if (data < root->data) {
root->left = insertNode(root->left, data);
}
// 如果插入的值大于等于当前节点的值,则插入到右子树
else {
root->right = insertNode(root->right, data);
}
return root;
}
// 查找节点
BST* searchNode(BST *root, int data) {
// 如果根节点为空,则返回NULL
if (root == NULL) {
return NULL;
}
// 如果查找的值等于当前节点的值,则返回当前节点
if (data == root->data) {
return root;
}
// 如果查找的值小于当前节点的值,则在左子树中查找
if (data < root->data) {
return searchNode(root->left, data);
}
// 如果查找的值大于当前节点的值,则在右子树中查找
else {
return searchNode(root->right, data);
}
}
// 删除节点
BST* deleteNode(BST *root, int data) {
BST *temp;
if (root == NULL) {
printf("Element not found\n");
}
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 && root->right) {
temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, root->data);
}
else {
temp = root;
if (root->left == NULL) {
root = root->right;
}
else if (root->right == NULL) {
root = root->left;
}
free(temp);
}
}
return root;
}
// 查找最小值
BST* findMin(BST *root) {
if (root == NULL) {
return NULL;
}
else if (root->left == NULL) {
return root;
}
else {
return findMin(root->left);
}
}
// 中序遍历
void inorder(BST *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
int n, i, x;
BST *root = NULL;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter the elements: ");
for (i = 0; i < n; i++) {
scanf("%d", &x);
root = insertNode(root, x);
}
printf("Inorder traversal of the BST: ");
inorder(root);
printf("\nEnter the element to search: ");
scanf("%d", &x);
BST *temp = searchNode(root, x);
if (temp == NULL) {
printf("Element not found\n");
}
else {
printf("Element found\n");
}
printf("Enter the element to delete: ");
scanf("%d", &x);
root = deleteNode(root, x);
printf("Inorder traversal of the BST after deletion: ");
inorder(root);
return 0;
}
```
在该代码中,我们使用了递归来实现二叉排序树的插入、查找和删除。我们还实现了中序遍历用于输出二叉排序树的元素。
阅读全文