92 lines
1.8 KiB
C
92 lines
1.8 KiB
C
|
|
#include <stdlib.h>
|
|
#include "node.h"
|
|
|
|
node_t *node_create(void *data) {
|
|
node_t *temp = malloc(sizeof(node_t));
|
|
|
|
temp->data = data;
|
|
temp->left = temp->right = NULL;
|
|
|
|
return temp;
|
|
}
|
|
|
|
node_t *node_search(node_t *root, void *data, node_comparator func) {
|
|
int cmp;
|
|
if (root == NULL) {
|
|
return root;
|
|
}
|
|
|
|
node_t *temp = node_create(data);
|
|
cmp = func(root, temp);
|
|
free(temp);
|
|
|
|
if (cmp == 0) {
|
|
return root;
|
|
}
|
|
|
|
if (cmp < 0) {
|
|
return node_search(root->left, data, func);
|
|
} else {
|
|
return node_search(root->right, data, func);
|
|
}
|
|
}
|
|
|
|
node_t *node_insert(node_t *node, void *data, node_comparator func) {
|
|
if (node == NULL) {
|
|
return node_create(data);
|
|
}
|
|
|
|
node_t *temp = node_create(data);
|
|
int cmp = func(node, temp);
|
|
free(temp);
|
|
|
|
if (cmp < 0) {
|
|
node->left = node_insert(node->left, data, func);
|
|
} else {
|
|
node->right = node_insert(node->right, data, func);
|
|
}
|
|
return node;
|
|
}
|
|
|
|
node_t *node_find_leftmost(node_t *root) {
|
|
if (root == NULL) {
|
|
return NULL;
|
|
} else if (root->left != NULL) {
|
|
return node_find_leftmost(root->left);
|
|
}
|
|
return root;
|
|
}
|
|
|
|
node_t *node_remove(node_t *root, void *data, node_comparator func) {
|
|
if (root == NULL) {
|
|
return NULL;
|
|
}
|
|
node_t *temp = node_create(data);
|
|
int cmp = func(root, temp);
|
|
free(temp);
|
|
|
|
if (cmp > 0) {
|
|
root->right = node_remove(root->right, data, func);
|
|
} else if (cmp < 0) {
|
|
root->left = node_remove(root->left, data, func);
|
|
} else {
|
|
if ((root->left == NULL) && (root->right == NULL)) {
|
|
free(root);
|
|
return NULL;
|
|
} else if ((root->left == NULL) || (root->right == NULL)) {
|
|
if (root->left == NULL) {
|
|
temp = root->right;
|
|
} else {
|
|
temp = root->left;
|
|
}
|
|
free(temp);
|
|
} else {
|
|
temp = node_find_leftmost(root->right);
|
|
root->data = temp->data;
|
|
root->right = node_remove(root->right, temp->data, func);
|
|
}
|
|
}
|
|
return root;
|
|
}
|