用c语言写出以下代码,用二叉链表作为二叉排序树的存储结构,实现以下功能: (1)输入一个整数数列,生成一颗二叉排序树。 (2)在二叉排序树中查找元素。 (3)在二叉排序树种插入元素。 (4)在二叉排序树中删除元素。 (5)对二叉排序树进行中序遍历,输出结果。
时间: 2024-01-07 20:23:45 浏览: 38
以下是用C语言实现二叉排序树的代码,实现了输入整数数列生成二叉排序树、查找元素、插入元素、删除元素和中序遍历的功能:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的结点结构
typedef struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
// 创建新结点
BSTNode* createNode(int data) {
BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 向二叉排序树中插入元素
BSTNode* insert(BSTNode* root, int data) {
if (root == NULL) {
return createNode(data);
} else if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
// 在二叉排序树中查找元素
BSTNode* search(BSTNode* 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);
}
}
// 在二叉排序树中删除元素
BSTNode* delete(BSTNode* root, int data) {
if (root == NULL) {
return root;
} else if (data < root->data) {
root->left = delete(root->left, data);
} else if (data > root->data) {
root->right = delete(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 = delete(root->right, temp->data);
}
return root;
}
// 中序遍历二叉排序树
void inorderTraversal(BSTNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
BSTNode* root = NULL;
// 输入整数数列,生成二叉排序树
int n;
printf("请输入整数数列的长度:");
scanf("%d", &n);
printf("请输入整数数列:");
for (int i = 0; i < n; i++) {
int data;
scanf("%d", &data);
root = insert(root, data);
}
// 在二叉排序树中查找元素
int searchData;
printf("请输入要查找的元素:");
scanf("%d", &searchData);
BSTNode* searchResult = search(root, searchData);
if (searchResult != NULL) {
printf("元素 %d 在二叉排序树中找到了。\n", searchData);
} else {
printf("元素 %d 在二叉排序树中未找到。\n", searchData);
}
// 在二叉排序树中插入元素
int insertData;
printf("请输入要插入的元素:");
scanf("%d", &insertData);
root = insert(root, insertData);
// 在二叉排序树中删除元素
int deleteData;
printf("请输入要删除的元素:");
scanf("%d", &deleteData);
root = delete(root, deleteData);
// 中序遍历二叉排序树
printf("中序遍历结果:");
inorderTraversal(root);
printf("\n");
return 0;
}
```