c语言如何构造二叉排序树?请给出代码
时间: 2024-01-20 14:38:55 浏览: 75
以下是一个简单的二叉排序树的实现,包括插入、删除、查找和遍历操作。
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
Node* create_node(int data) {
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void insert(Node **root, int data) {
if (*root == NULL) {
*root = create_node(data);
return;
}
if (data < (*root)->data) {
insert(&(*root)->left, data);
} else if (data > (*root)->data) {
insert(&(*root)->right, data);
}
}
Node* find(Node *root, int data) {
if (root == NULL) {
return NULL;
}
if (data < root->data) {
return find(root->left, data);
} else if (data > root->data) {
return find(root->right, data);
} else {
return root;
}
}
Node* find_min(Node *root) {
if (root == NULL) {
return NULL;
}
if (root->left == NULL) {
return root;
} else {
return find_min(root->left);
}
}
Node* delete(Node *root, int data) {
if (root == NULL) {
return NULL;
}
if (data < root->data) {
root->left = delete(root->left, data);
} else if (data > root->data) {
root->right = delete(root->right, data);
} else {
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
} else if (root->left == NULL) {
Node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node *temp = root->left;
free(root);
return temp;
} else {
Node *temp = find_min(root->right);
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
}
return root;
}
void inorder_traversal(Node *root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
}
int main() {
Node *root = NULL;
insert(&root, 5);
insert(&root, 3);
insert(&root, 7);
insert(&root, 1);
insert(&root, 9);
inorder_traversal(root);
printf("\n");
root = delete(root, 5);
inorder_traversal(root);
printf("\n");
Node *node = find(root, 7);
printf("%d\n", node->data);
return 0;
}
```
阅读全文