请用c语言代码实现二叉排序树。任意给定一组数据,建立一棵二叉排序树,对它进行查找、插入、删除操作。二叉排序树存储结构如下:typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;
时间: 2024-03-24 18:39:33 浏览: 63
好的,下面是C语言代码实现二叉排序树的例子:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 插入节点
int insert(BiTree *T, int data) {
if (*T == NULL) {
*T = (BiTree)malloc(sizeof(BiTNode));
if (!*T) {
return 0;
}
(*T)->data = data;
(*T)->lchild = NULL;
(*T)->rchild = NULL;
return 1;
}
if (data == (*T)->data) {
return 0;
}
if (data < (*T)->data) {
return insert(&((*T)->lchild), data);
} else {
return insert(&((*T)->rchild), data);
}
}
// 创建二叉排序树
void createBST(BiTree *T, int arr[], int n) {
int i;
for (i = 0; i < n; i++) {
insert(T, arr[i]);
}
}
// 中序遍历
void inorderTraversal(BiTree T) {
if (T != NULL) {
inorderTraversal(T->lchild);
printf("%d ", T->data);
inorderTraversal(T->rchild);
}
}
// 查找节点
BiTree search(BiTree T, int data) {
if (T == NULL || T->data == data) {
return T;
}
if (data < T->data) {
return search(T->lchild, data);
} else {
return search(T->rchild, data);
}
}
// 删除节点
int delete(BiTree *T, int data) {
if (*T == NULL) {
return 0;
}
if (data == (*T)->data) {
BiTree p;
if ((*T)->lchild == NULL) {
p = *T;
*T = (*T)->rchild;
free(p);
} else if ((*T)->rchild == NULL) {
p = *T;
*T = (*T)->lchild;
free(p);
} else {
p = (*T)->rchild;
while (p->lchild != NULL) {
p = p->lchild;
}
(*T)->data = p->data;
delete(&((*T)->rchild), p->data);
}
return 1;
}
if (data < (*T)->data) {
return delete(&((*T)->lchild), data);
} else {
return delete(&((*T)->rchild), data);
}
}
int main() {
BiTree T = NULL;
int arr[] = {5, 3, 8, 1, 4, 7, 9};
int n = sizeof(arr) / sizeof(int);
createBST(&T, arr, n);
printf("二叉排序树中序遍历:\n");
inorderTraversal(T);
int searchData = 4;
BiTree searchResult = search(T, searchData);
if (searchResult != NULL) {
printf("\n找到了节点 %d\n", searchData);
} else {
printf("\n没有找到节点 %d\n", searchData);
}
int deleteData = 3;
int deleteResult = delete(&T, deleteData);
if (deleteResult) {
printf("删除节点 %d 后,二叉排序树中序遍历:\n", deleteData);
inorderTraversal(T);
} else {
printf("删除节点 %d 失败\n", deleteData);
}
return 0;
}
```
上面的代码中,我们首先定义了二叉排序树的结点结构体 `BiTNode`,其中包含了结点值和左右孩子指针。然后,我们定义了二叉排序树的指针类型 `BiTree`。
接着,我们实现了二叉排序树的插入操作。插入操作需要判断插入的节点是否已经存在,如果已经存在则直接返回。如果节点不存在,则需要按照二叉排序树的规则将其插入到左子树或右子树中。
然后,我们实现了创建二叉排序树的函数 `createBST()`,它用于将任意给定的一组数据建立一棵二叉排序树。创建二叉排序树的过程就是不断调用插入函数将数据插入到树中的过程。
接着,我们实现了二叉排序树的中序遍历函数 `inorderTraversal()`,它按照中序遍历的顺序输出树中的节点值。
然后,我们实现了二叉排序树的查找函数 `search()`,它用于查找树中是否存在指定的节点。
最后,我们实现了二叉排序树的删除函数 `delete()`,它用于删除树中的指定节点。删除节点的过程需要考虑三种情况:删除节点没有孩子节点、删除节点只有一个孩子节点、删除节点有两个孩子节点。
在主函数中,我们首先创建了一棵二叉排序树,然后按照中序遍历的顺序输出树中的节点值。接着,我们尝试查找树中的一个节点和删除树中的一个节点,并输出删除节点后的中序遍历结果。
注意,由于没有给出题目中给定的数据,所以我在代码中用了一个预设的数据数组来创建二叉排序树。在实际编程中,需要根据题目要求读入数据或者生成数据。
阅读全文