Allen Allen - 26 days ago 11
C Question

Trouble trying to eliminate a node from a tree (struct)

As the title says I'm trying to remove a node from a tree having 2 cases:


  • the node is a leaf that not connected to anything

  • the node is connected to another node



I was able to make a working function for the second case (the most difficult for me), but the first one (that seemed easy) causes a segmentation fault no matter what I try.

Here is the definition of struct:

struct node {
int value;
struct node *sx;
struct node *dx;
};

typedef struct node *tree;


Here is the module that perform the operation of elimination:

void destroy_node(tree Y, int elem) {
if (Y->value < elem)
destroy_node(Y->dx, elem);
if (Y->value > elem)
destroy_node(Y->sx, elem);
else { //
if (Y->sx == NULL && Y->dx == NULL) {
free(Y); <-- seg fault
Y = NULL; <-- seg fault
}
if (Y->sx != NULL && Y->dx == NULL) {
Y->value = (Y->sx)->value;
free(Y->sx);
Y->sx = NULL;
}
if (Y->sx == NULL && Y->dx != NULL) {
Y->value = (Y->dx)->value;
free(Y->dx);
Y->dx = NULL;
}
if (Y->sx != NULL && Y->dx != NULL)
printf("Can't eliminate that!\n");
}
print_everything(Y);
}


Here is the
main
call:

tree Y = T;
printf("Which one you want to destroy? ");
scanf("%d", &elem);
destroy_node(Y, elem);


To compile the function I use the command

gcc -std=gnu99 -Wall -Wextra c.c


My environment is a virtual machine ubuntu 17.04 with stock gcc

EDIT 1

Module that build a tree

tree insert_node(tree T, int val) {
if (T == NULL) {
T = (tree)malloc(sizeof(struct node));
T->value = val;
T->sx = NULL;
T->dx = NULL;
} else {
if ((T->value) < (val)) {
T->dx = insert_node(T->dx, val);
}
if ((T->value) > (val)) {
T->sx = insert_node(T->sx, val);
}
}
return T;
}


Here there is the call in the main of this module

printf("How many nodes your tree will have? ");
scanf("%d", &tot);
for (int i = 0; i < tot; i++) {
printf("What is the %d° node? ", (i + 1));
scanf("%d", &val);
T = insert_node(T, val);
}


P.S. If there are problem regarding the comprehensibility of the program I will copy paste the whole file

Answer Source

There are missing pieces in your function:

  • You do not check if Y != NULL. You would have undefined behavior on an empty tree.
  • There is a missing else after the first if statement. You mistakenly delete the node if Y->value <= elem.
  • You do not update the parent pointer when you delete a node.

You should change the API to return the updated value for the pointer argument:

tree destroy_node(tree Y, int elem) {
    tree res = Y;
    if (Y != NULL) {
        if (Y->value < elem) {
            Y->dx = destroy_node(Y->dx, elem);
        } else
        if (Y->value > elem) {
            Y->sx = destroy_node(Y->sx, elem);
        } else {
        if (Y->sx == NULL && Y->dx == NULL) {
            res = NULL;
            free(Y);
        } else
        if (Y->dx == NULL) {
            res = Y->sx;
            free(Y);
        } else
        if (Y->sx == NULL) {
            res = Y->dx;
            free(Y);
        } else {
            printf("Can't eliminate that!\n");
        }
    }
    return res;
}

Call from main as:

tree T;
...
printf("Which one you want to destroy? ");
if (scanf("%d", &elem) == 1)
    T = destroy_node(T, elem);

Of course you must find a solution to delete nodes with 2 branches.