I have a BST and I want to add/delete/find/inorder_traversal/... on it. But when I want to delete an item, there is a problem.
initialize tree:
node_t *init() {
node_t *node = calloc(1, sizeof(node_t));
node->left = NULL;
node->right = NULL;
node->data = NULL;
return node;
}
add() function:
int add(node_t *node, void *data) {
if (node->data == NULL) { //first time when there is only root node exists
node->data = data;
printf("%d -> %p\n", (int)node->data, node);
return 0;
}
node_t *prev = NULL, *ptr;
ptr = node;
char type;
while (ptr) {
prev = ptr;
if (data < ptr->data) {
ptr = ptr->left;
type = 'l';
} else
if (data > ptr->data) {
ptr = ptr->right;
type = 'r';
}
}
if (type == 'l') {
node_t *node = calloc(1, sizeof(node_t));
node->data = data;
node->left = NULL;
node->right = NULL;
prev->left = node;
printf("%d -> %p\n", (int)node->data, node);
return 1;
} else
if (type == 'r') {
node_t *node = calloc(1, sizeof(node_t));
node->data = data;
node->left = NULL;
node->right = NULL;
prev->right = node;
printf("%d -> %p\n", (int)node->data, node);
return 1;
}
return -1;
}
del() function:
int del(node_t *node, void *data) {
if (data < node->data) {
del(node->left, data);
} else
if (data > node->data) {
del(node->right, data);
} else
if (data == node->data) {
if (node->left == NULL && node->right == NULL) { // leaf node
free(node);
return 0;
} else
if (node->left != NULL) { //node has only left child
node->data = node->left->data;
node->left->data = 0;
free(node->left);
return 0;
} else
if (node->right != NULL) { //node has only right child
node->data = node->right->data;
node->right->data = 0;
free(node->right);
return 0;
} else
if (node->left != NULL && node->right != NULL) { // node has two children
node_t *temp = min_value(node->right);
node->data = temp->data;
del(node->right, data);
return 0;
}
}
return -1;
}
main():
int main() {
node_t *tree;
tree = init();
add(tree, (void*)40);
add(tree, (void*)10);
add(tree, (void*)30);
add(tree, (void*)25);
add(tree, (void*)50);
add(tree, (void*)11);
add(tree, (void*)76);
preorder_traversal(tree);
printf("\n");
del(tree, (void*)30);
preorder_traversal(tree);
printf("\n");
return 0;
}
before deleting, I run inorder_traversal(), then delete number 30, and again run inorder_traversal(), but the output is as below:
40 10 11 25 30 50 76
40 10 11 0 25 50 76
Guys I would appreciate if you help me.
Also, min_value() function is as below:
node_t *min_value(node_t *node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}
min_value()code in the post