首先用C语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 20:29:19 浏览: 108
以下是用C语言实现二叉排序树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
};
// 创建一个新节点
struct BSTNode* createNode(int data) {
struct BSTNode* newNode = (struct BSTNode*)malloc(sizeof(struct BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 向二叉排序树中插入一个节点
struct BSTNode* insert(struct BSTNode* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
// 从二叉排序树中删除一个节点
struct BSTNode* deleteNode(struct BSTNode* root, int data) {
if (root == NULL) {
return NULL;
}
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) {
struct BSTNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct BSTNode* temp = root->left;
free(root);
return temp;
}
struct BSTNode* temp = root->right;
while (temp && temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// 在二叉排序树中查找一个节点
struct BSTNode* search(struct BSTNode* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return search(root->left, data);
} else {
return search(root->right, data);
}
}
// 中序遍历二叉排序树
void inorderTraversal(struct BSTNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// 测试程序
int main() {
struct BSTNode* root = NULL;
int option, data;
while (1) {
printf("\n1.Insert\n2.Delete\n3.Search\n4.Inorder Traversal\n5.Exit\n");
printf("Enter your option: ");
scanf("%d", &option);
switch (option) {
case 1:
printf("Enter the value to be inserted: ");
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
printf("Enter the value to be deleted: ");
scanf("%d", &data);
root = deleteNode(root, data);
break;
case 3:
printf("Enter the value to be searched: ");
scanf("%d", &data);
if (search(root, data) != NULL) {
printf("Value found in the tree.\n");
} else {
printf("Value not found in the tree.\n");
}
break;
case 4:
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");
break;
case 5:
exit(0);
default:
printf("Invalid option.\n");
}
}
return 0;
}
```
这个程序可以读入用户输入的选项,然后执行对应的操作(插入、删除、查找、遍历或退出)。用户可以在命令行中输入选项,然后输入对应的值进行操作。
阅读全文