c语言编程实现: (1)输入一数列,建立二叉排序树; (2)对所建立的二叉排序树进行查找操作,找到了就显示,找不到就插入; (3)对所建立的二叉排序树进行删除操作。
时间: 2023-12-19 15:07:35 浏览: 48
以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 建立二叉排序树
TreeNode *build_bst(int *nums, int size) {
TreeNode *root = NULL;
for (int i = 0; i < size; i++) {
root = insert_bst(root, nums[i]);
}
return root;
}
// 插入节点到二叉排序树
TreeNode *insert_bst(TreeNode *root, int val) {
if (!root) {
root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = val;
root->left = NULL;
root->right = NULL;
} else if (val < root->val) {
root->left = insert_bst(root->left, val);
} else if (val > root->val) {
root->right = insert_bst(root->right, val);
}
return root;
}
// 查找节点并插入或返回
TreeNode *search_bst(TreeNode *root, int val) {
if (!root) {
root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = val;
root->left = NULL;
root->right = NULL;
} else if (val == root->val) {
return root;
} else if (val < root->val) {
root->left = search_bst(root->left, val);
} else {
root->right = search_bst(root->right, val);
}
return root;
}
// 删除节点并重建二叉排序树
TreeNode *delete_bst(TreeNode *root, int val) {
if (!root) {
return NULL;
} else if (val < root->val) {
root->left = delete_bst(root->left, val);
} else if (val > root->val) {
root->right = delete_bst(root->right, val);
} else {
if (!root->left) {
TreeNode *tmp = root->right;
free(root);
return tmp;
} else if (!root->right) {
TreeNode *tmp = root->left;
free(root);
return tmp;
} else {
TreeNode *tmp = root->right;
while (tmp->left) {
tmp = tmp->left;
}
root->val = tmp->val;
root->right = delete_bst(root->right, tmp->val);
}
}
return root;
}
// 中序遍历二叉排序树
void inorder_traversal(TreeNode *root) {
if (root) {
inorder_traversal(root->left);
printf("%d ", root->val);
inorder_traversal(root->right);
}
}
int main() {
int nums[] = {5, 3, 7, 2, 4, 6, 8};
int size = sizeof(nums) / sizeof(nums[0]);
printf("建立二叉排序树...\n");
TreeNode *root = build_bst(nums, size);
printf("二叉排序树中序遍历结果:\n");
inorder_traversal(root);
printf("\n");
printf("查找节点 5 并插入或返回...\n");
root = search_bst(root, 5);
printf("查找节点 1 并插入或返回...\n");
root = search_bst(root, 1);
printf("二叉排序树中序遍历结果:\n");
inorder_traversal(root);
printf("\n");
printf("删除节点 5...\n");
root = delete_bst(root, 5);
printf("二叉排序树中序遍历结果:\n");
inorder_traversal(root);
printf("\n");
return 0;
}
```
这里我们使用了结构体定义二叉排序树节点,使用了递归实现插入、查找和删除操作。其中,`build_bst` 函数用来建立二叉排序树,它遍历输入的数列,调用 `insert_bst` 函数插入节点到二叉排序树中。`insert_bst` 函数则是用来插入节点到二叉排序树中的。
`search_bst` 函数用来查找节点。如果节点不存在,就插入节点并返回;如果找到了,就返回该节点。
`delete_bst` 函数用来删除节点。如果节点不存在,就返回 NULL;如果要删除的节点是叶子节点,就直接删除;如果要删除的节点只有一个子节点,就将其子节点代替该节点;如果要删除的节点有两个子节点,就找到它右子树的最小值节点代替该节点,并删除该最小值节点。
最后,我们在 `main` 函数中测试了这些函数的实现,并通过中序遍历验证了二叉排序树的正确性。