用C语言实现:二叉排序树。任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除操作。
时间: 2024-03-14 14:46:45 浏览: 92
好的,我可以为您解答这个问题。
首先,二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它满足以下条件:
1. 左子树所有节点的值均小于父节点的值;
2. 右子树所有节点的值均大于父节点的值;
3. 左右子树都是二叉排序树。
因此,我们可以利用这个性质来实现插入、查找、删除操作。
以下是用C语言实现二叉排序树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node, *Tree;
// 插入操作
void insert(Tree *t, int x) {
if (*t == NULL) {
*t = (Node*)malloc(sizeof(Node));
(*t)->data = x;
(*t)->left = (*t)->right = NULL;
} else {
if (x < (*t)->data) {
insert(&((*t)->left), x);
} else if (x > (*t)->data) {
insert(&((*t)->right), x);
}
}
}
// 查找操作
Node* search(Tree t, int x) {
if (t == NULL) {
return NULL;
} else if (x < t->data) {
return search(t->left, x);
} else if (x > t->data) {
return search(t->right, x);
} else {
return t;
}
}
// 删除操作
Node* delete(Tree *t, int x) {
Node *tmp = NULL;
if (*t == NULL) {
return NULL;
} else if (x < (*t)->data) {
(*t)->left = delete(&((*t)->left), x);
} else if (x > (*t)->data) {
(*t)->right = delete(&((*t)->right), x);
} else if ((*t)->left && (*t)->right) { // 有两个子节点
tmp = (*t)->right;
while (tmp->left) {
tmp = tmp->left;
}
(*t)->data = tmp->data;
(*t)->right = delete(&((*t)->right), (*t)->data);
} else { // 有一个或无子节点
tmp = *t;
if ((*t)->left == NULL) {
*t = (*t)->right;
} else if ((*t)->right == NULL) {
*t = (*t)->left;
}
free(tmp);
}
return *t;
}
// 遍历操作
void inorder(Tree t) {
if (t) {
inorder(t->left);
printf("%d ", t->data);
inorder(t->right);
}
}
// 测试代码
int main() {
int arr[] = {5, 3, 7, 1, 9, 4, 6, 2, 8};
int len = sizeof(arr) / sizeof(arr[0]);
Tree t = NULL;
// 插入操作
for (int i = 0; i < len; i++) {
insert(&t, arr[i]);
}
// 遍历操作
inorder(t);
// 查找操作
Node *node = search(t, 7);
if (node) {
printf("\nFound %d\n", node->data);
} else {
printf("\nNot found\n");
}
// 删除操作
delete(&t, 3);
// 遍历操作
inorder(t);
return 0;
}
```
以上代码中,我们定义了一个`Node`结构体来表示二叉排序树的节点,包括数据、左子节点和右子节点。`Tree`是指向`Node`指针的类型,表示整个二叉排序树。`insert()`函数用来插入节点,`search()`函数用来查找节点,`delete()`函数用来删除节点,`inorder()`函数用来遍历二叉排序树。主函数中,我们先创建一个整型数组`arr`作为测试数据,然后按顺序插入到二叉排序树中。接着,我们进行遍历、查找和删除操作,最后输出遍历结果。
注意,以上代码只是二叉排序树的一种实现方式,还有其他实现方式,具体实现可以根据实际需求进行调整。
阅读全文