首先用C语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 22:24:14 浏览: 105
好的,以下是C语言实现二叉排序树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的结点
typedef struct BSTNode {
int data;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
// 创建二叉排序树
BSTNode* createBST(int data) {
BSTNode *root = (BSTNode*) malloc(sizeof(BSTNode));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
// 插入结点
BSTNode* insertBST(BSTNode *root, int data) {
if (root == NULL) {
return createBST(data);
}
if (data < root->data) {
root->left = insertBST(root->left, data);
} else if (data > root->data) {
root->right = insertBST(root->right, data);
}
return root;
}
// 查找结点
BSTNode* searchBST(BSTNode *root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return searchBST(root->left, data);
} else {
return searchBST(root->right, data);
}
}
// 删除结点
BSTNode* deleteBST(BSTNode *root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = deleteBST(root->left, data);
} else if (data > root->data) {
root->right = deleteBST(root->right, data);
} else {
if (root->left == NULL) {
BSTNode *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
BSTNode *temp = root->left;
free(root);
return temp;
}
// 获取右子树中最小的结点
BSTNode *temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = deleteBST(root->right, temp->data);
}
return root;
}
// 中序遍历
void inorderBST(BSTNode *root) {
if (root != NULL) {
inorderBST(root->left);
printf("%d ", root->data);
inorderBST(root->right);
}
}
int main() {
int n, x;
scanf("%d", &n);
BSTNode *root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &x);
root = insertBST(root, x);
}
inorderBST(root);
printf("\n");
int k;
scanf("%d", &k);
BSTNode *node = searchBST(root, k);
if (node != NULL) {
printf("The element %d is found.\n", k);
} else {
printf("The element %d is not found.\n", k);
}
scanf("%d", &x);
root = insertBST(root, x);
inorderBST(root);
printf("\n");
scanf("%d", &x);
root = deleteBST(root, x);
inorderBST(root);
printf("\n");
return 0;
}
```
代码说明:
- `BSTNode` 结构体表示二叉排序树的结点,包括数据 `data` 以及左右子树指针 `left` 和 `right`。
- `createBST` 函数用于创建一棵只包含根节点的二叉排序树。
- `insertBST` 函数用于向二叉排序树中插入一个新的元素。
- `searchBST` 函数用于在二叉排序树中查找指定的元素。
- `deleteBST` 函数用于在二叉排序树中删除指定的元素。
- `inorderBST` 函数用于对二叉排序树进行中序遍历。
- `main` 函数中读入一串字符,依次插入到二叉排序树中。然后分别进行查找、插入、删除等操作,并输出中序遍历结果。
注意:以上代码仅作为二叉排序树实现的示例,实际应用中需要根据具体情况进行修改和优化。
阅读全文