任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除等操作的C语言代码
时间: 2024-02-19 20:02:35 浏览: 79
以下是基于C语言的二叉排序树算法实现,包含了查找、插入、删除等操作:
```c
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* create_node(int data)
{
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
void insert_node(struct node** root, int data)
{
if (*root == NULL) {
*root = create_node(data);
} else if (data < (*root)->data) {
insert_node(&((*root)->left), data);
} else if (data > (*root)->data) {
insert_node(&((*root)->right), data);
}
}
struct node* find_node(struct node* root, int data)
{
if (root == NULL) {
return NULL;
} else if (data < root->data) {
return find_node(root->left, data);
} else if (data > root->data) {
return find_node(root->right, data);
} else {
return root;
}
}
struct node* find_min_node(struct node* root)
{
struct node* current = root;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
struct node* delete_node(struct node* root, int data)
{
if (root == NULL) {
return NULL;
} else if (data < root->data) {
root->left = delete_node(root->left, data);
} else if (data > root->data) {
root->right = delete_node(root->right, data);
} else {
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
} else if (root->left == NULL) {
struct node* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) {
struct node* temp = root;
root = root->left;
free(temp);
} else {
struct node* temp = find_min_node(root->right);
root->data = temp->data;
root->right = delete_node(root->right, temp->data);
}
}
return root;
}
void inorder_traversal(struct node* root)
{
if (root != NULL) {
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
}
}
int main()
{
struct node* root = NULL;
insert_node(&root, 5);
insert_node(&root, 3);
insert_node(&root, 7);
insert_node(&root, 1);
insert_node(&root, 9);
printf("Inorder traversal: ");
inorder_traversal(root);
printf("\n");
struct node* found_node = find_node(root, 7);
if (found_node) {
printf("Found node with value %d\n", found_node->data);
} else {
printf("Node not found\n");
}
root = delete_node(root, 3);
printf("Inorder traversal after deletion: ");
inorder_traversal(root);
printf("\n");
return 0;
}
```
在这个实现中,我们使用了一个node结构体来表示二叉排序树的每个节点。在插入节点时,从根节点开始递归查找对应的插入位置。在查找节点时,同样也从根节点开始递归查找。在删除节点时,我们需要考虑删除的节点是否有左子树、右子树或两者都有的情况。
最后,我们使用中序遍历的方式来输出二叉排序树中的所有节点。
阅读全文