任意给定一组数据设计一个c语言算法,建立一棵二叉排序树,对它进行查找插入删除等操作,c语言实现
时间: 2024-01-29 07:05:03 浏览: 105
好的,以下是基于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* node = (BSTNode*)malloc(sizeof(BSTNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入结点
BSTNode* insert(BSTNode* node, int data) {
if (node == NULL) {
return createNode(data);
} else if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
}
return node;
}
// 查找结点
BSTNode* search(BSTNode* node, int data) {
if (node == NULL || node->data == data) {
return node;
} else if (data < node->data) {
return search(node->left, data);
} else if (data > node->data) {
return search(node->right, data);
}
return NULL;
}
// 寻找最小结点
BSTNode* findMin(BSTNode* node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}
// 删除结点
BSTNode* delete(BSTNode* node, int data) {
if (node == NULL) {
return NULL;
} else if (data < node->data) {
node->left = delete(node->left, data);
} else if (data > node->data) {
node->right = delete(node->right, data);
} else {
// 没有子节点或只有一个子节点的情况
if (node->left == NULL) {
BSTNode* temp = node->right;
free(node);
return temp;
} else if (node->right == NULL) {
BSTNode* temp = node->left;
free(node);
return temp;
}
// 有两个子节点的情况
BSTNode* temp = findMin(node->right);
node->data = temp->data;
node->right = delete(node->right, temp->data);
}
return node;
}
// 中序遍历
void inorder(BSTNode* node) {
if (node != NULL) {
inorder(node->left);
printf("%d ", node->data);
inorder(node->right);
}
}
int main() {
BSTNode* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("中序遍历结果:");
inorder(root);
printf("\n");
BSTNode* node = search(root, 30);
printf("查找结果:%d\n", node->data);
root = delete(root, 50);
printf("删除50后的中序遍历结果:");
inorder(root);
printf("\n");
return 0;
}
```
上述代码中,`createNode()`函数用于创建一个新的结点,`insert()`函数用于向二叉排序树中插入一个元素,`search()`函数用于查找二叉排序树中是否存在某个元素,`findMin()`函数用于寻找二叉排序树中最小的元素,`delete()`函数用于删除二叉排序树中的某个元素,`inorder()`函数用于中序遍历整棵二叉排序树。在 `main()` 函数中,我们演示了如何使用这些函数来建立一棵二叉排序树,并对其进行了插入、查找、删除等操作。
阅读全文