Hello,
After about a week of trying to figure out how to write a function that would take into consideration all aspects of deleting a node from a binary tree... I succeeded. After writing the function, I looked at it, and said to myself, "There has to be a way to make this easier to write and easier to read."
Since I am teaching myself, I wanted the communities input as to how I could have approached this differently, how I can reduce my code, if necessary (I have a feeling I could have used recursion), comments, critisism, etc. Below is the code:
Code:
void delete_node(BTREE *node, int value)
{
BTREE *current = NULL, *del_node = NULL, *child = NULL;
BTREE *parent = NULL, *x = NULL;
current = node;
while (current != NULL) {
if (value == current->num) {
del_node = current;
//case 1: node is a leaf (no descendants)
if ((del_node->left == NULL) && (del_node->right == NULL)) {
//if the node to delete is to the left of root
if (parent->left == del_node) {
parent->left = NULL;
free(del_node);
printf("Node deleted\n");
break;
}
//if the node to delete is to the right of root
else if (parent->right == del_node) {
parent->right = NULL;
free(del_node);
printf("Node deleted\n");
break;
}
}
//case 2: node has one child
else if ((del_node->left == NULL) || (del_node->right == NULL)) {
printf("Node has one child\n");
//if the node to delete is to the left of root
if (parent->left == del_node) {
if (del_node->left != NULL) {
child = del_node->left;
parent->left = child;
free(del_node);
break;
}
else if (del_node->right != NULL) {
child = del_node->right;
parent->left = child;
free(del_node);
break;
}
}
//if the node to delete is to the right of root
else if (parent->right == del_node) {
if (del_node->left != NULL) {
child = del_node->left;
parent->right = child;
free(del_node);
break;
}
else if (del_node->right != NULL) {
child = del_node->right;
parent->right = child;
free(del_node);
break;
}
}
}
//case 3: node has two children
else if ((del_node->left != NULL) && (del_node->right != NULL)) {
printf("Node has two children\n");
x = del_node;
//if the node to delete is root
if (parent == NULL) {
child = del_node->right;
if (child->left == NULL) {
child->left = del_node->left;
free(del_node);
break;
}
else {
while (child->left != NULL) {
parent = child;
child = parent->left;
}
x->num = child->num;
parent->left = child->right;
del_node = child;
free(del_node);
break;
}
}
//if the node to delete is to the left of root
else if (parent->left == del_node) {
child = del_node->right;
if (child->left == NULL) {
parent->left = child;
child->left = del_node->left;
free(del_node);
break;
}
else {
while (child->left != NULL) {
parent = child;
child = parent->left;
}
x->num = child->num;
parent->left = child->right;
del_node = child;
free(del_node);
break;
}
}
//if the node to delete is to the right of root
else if (parent->right == del_node) {
child = del_node->right;
if (child->left == NULL) {
parent->right = child;
child->left = del_node->left;
free(del_node);
break;
}
else {
while (child->left != NULL) {
parent = child;
child = parent->left;
}
x->num = child->num;
parent->left = child->right;
del_node = child;
free(del_node);
break;
}
}
}
}
//if value is less than the node's value - go left
else if (value < current->num) {
parent = current;
current = current->left;
}
//if value is greater than the node's value - go right
else {
parent = current;
current = current->right;
}
}
}
Thank you for taking the time to read this thread and provide any comments.