C语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 09:14:01 浏览: 71
以下是 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) {
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data);
} else {
root->right = insertNode(root->right, data);
}
return root;
}
// 查找节点
Node* findNode(Node* root, int data) {
if (root == NULL) {
return NULL;
}
if (data == root->data) {
return root;
} else if (data < root->data) {
return findNode(root->left, data);
} else {
return findNode(root->right, data);
}
}
// 删除节点
Node* deleteNode(Node* 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) { // 无左子树
Node* tmp = root->right;
free(root);
return tmp;
} else if (root->right == NULL) { // 无右子树
Node* tmp = root->left;
free(root);
return tmp;
}
// 有两个子节点,找到右子树中的最小值节点
Node* tmp = root->right;
while (tmp->left != NULL) {
tmp = tmp->left;
}
// 将右子树中的最小值节点替换到待删除节点位置
root->data = tmp->data;
root->right = deleteNode(root->right, tmp->data);
}
return root;
}
// 中序遍历
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
// 读入一串字符
char str[100];
printf("请输入一串数字(以空格或回车分隔):\n");
fgets(str, 100, stdin);
// 将字符转换为数字并插入二叉排序树
Node* root = NULL;
char* p = str;
while (*p != '\0') {
if (*p >= '0' && *p <= '9') {
int data = 0;
while (*p >= '0' && *p <= '9') {
data = data * 10 + (*p - '0');
p++;
}
root = insertNode(root, data);
} else {
p++;
}
}
// 输出中序遍历结果
printf("中序遍历结果:");
inorderTraversal(root);
printf("\n");
// 查找节点
int findData;
printf("请输入要查找的数字:");
scanf("%d", &findData);
Node* findNodeResult = findNode(root, findData);
if (findNodeResult == NULL) {
printf("未找到该数字!\n");
} else {
printf("已找到数字 %d!\n", findNodeResult->data);
}
// 插入节点
int insertData;
printf("请输入要插入的数字:");
scanf("%d", &insertData);
root = insertNode(root, insertData);
printf("插入后的中序遍历结果:");
inorderTraversal(root);
printf("\n");
// 删除节点
int deleteData;
printf("请输入要删除的数字:");
scanf("%d", &deleteData);
root = deleteNode(root, deleteData);
printf("删除后的中序遍历结果:");
inorderTraversal(root);
printf("\n");
return 0;
}
```
这段代码实现了二叉排序树的创建、查找、插入和删除等操作。其中,`createNode` 函数用于创建一个新节点,`insertNode` 函数用于插入节点,`findNode` 函数用于查找节点,`deleteNode` 函数用于删除节点,`inorderTraversal` 函数用于中序遍历二叉树。在 `main` 函数中,先读入一串字符,然后将其转换为数字并插入二叉排序树。接着输出中序遍历结果,然后进行查找、插入和删除操作,并输出相应的中序遍历结果。
阅读全文