Removing items from a tree structure

Question

I have this struct:

typedef struct Tree {
  int arrel;
  struct Tree *dret;
  struct Tree *esq;
  unsigned int talla;
} Tree;

With the following methods:

void crearArbre (struct Tree *arbre, int val_arrel)
{
  arbre->arrel = val_arrel;
  arbre->dret = NULL;
  arbre->esq = NULL;
  arbre->talla = 0;
}
int inserir (struct Tree *arbre, int valor) //Insert method
{
  struct Tree *aux = arbre;
  struct Tree *ant = NULL;
  while (aux != NULL && aux->arrel - valor != 0)
    {
      ant = aux;
      if (aux->arrel > valor)
    {
      aux = aux->esq;
    }
      else
    aux = aux->dret;
    }
  if (aux == NULL)
    {
      if (ant->arrel > valor)
    {
      //ant -> esq -> arrel = valor;
      ant->esq = (struct Tree *) malloc (sizeof (struct Tree));
      ant->esq->arrel = valor;
      //crearArbre(ant -> esq ,valor);
    }
      else
    {
      ant->dret = (struct Tree *) malloc (sizeof (struct Tree));
      ant->dret->arrel = valor;
    }
    }
  arbre->talla += 1;
  return 0;

}
int rem (struct Tree *arbre, int valor) //Remove method
{
  if (arbre == NULL)
    return NULL;
  if (valor < arbre->arrel)
    {
      return rem (arbre->esq, valor);
    }
  else if (valor > arbre->arrel)
    {
      return rem (arbre->dret, valor);
    }
  else
    {
      int val = arbre->arrel;
      arbre = NULL; //Not sure about this
      free (arbre); //?
      return val;
    }
}
void printarArbre (struct Tree *arbre) //Post order printing method
{
  if (arbre != NULL)
    {
      printarArbre (arbre->esq);
      printarArbre (arbre->dret);
      printf ("%d -> ", arbre->arrel);
    } 

}

I have been testing the struct by inserting some numbers, find them and finally remove some elements. But, after I remove an element from the tree and calling free(), if I call printarArbre(), in the position that was the element previously removed, if I set (arbre = NULL) and then free(arbre), why is it still being printed? Do I need a flag to indicate whether a node has been removed?

Ah....I see: in `int rem(struct Tree *arbre,...` `arbre` is a value. if you set it to null, only the local value is set to null, but not the `arbe` of the caller. — Paul Ogilvie, May 20 '20 at 13:42
I think here you can find the answer: [C - what happens to memory after free](https://stackoverflow.com/questions/18582089/c-what-happens-to-memory-after-free) — Kasper, May 20 '20 at 13:43
And of course, setting `arbre` to null and _then_ calling `free(arbre)` will never free the memory because free doesn't know what to free (it receives a null value of course). — Paul Ogilvie, May 20 '20 at 13:44
@PaulOgilvie but in the method, arbre is a reference so I can set it to null right? — Josep, May 20 '20 at 13:46
Ok, so first of alll I will remove the statement arbre = NULL; — Josep, May 20 '20 at 13:47
It is a value, not a reference as in C++. You can set it to null, but the parent won't see it. You can free it, and the parent will see that there are no more values in the struct (or the program aborts with seg fault). — Paul Ogilvie, May 20 '20 at 13:47
I take note. Should I declare a global pointer and then inside the method call `free(global_ptr)`? — Josep, May 20 '20 at 13:52

score 0 · Accepted Answer · answered May 20 '20 at 13:50

Please see also the comments. The proper way would be:

int rem (struct Tree **arbreIn, int valor) //Remove method
{
  struct Tree *arbre= *arbreIn; // shorthand
  if (arbre == NULL)
    return NULL;
  if (valor < arbre->arrel)
    {
      return rem (&(arbre->esq), valor);
    }
  else if (valor > arbre->arrel)
    {
      return rem (&(arbre->dret), valor);
    }
  else
    {
      int val = arbre->arrel;
      free (arbre);    // free the node
      *arbreIn = NULL; // set the parent's pointer (esq or dret) to null
      return val;
    }
}

Removing items from a tree structure

1 Answers1