Eliminate node function from tree doesn't work in C

Question

I have to eliminate a node from the tree. I first tried to eliminate the node root, so I don't have to search the node and it works. But then I tried to do it by searching, and when the function calls itself, the program freezes after it passes the first if-statement...

The problem is in the function, void Eliminar(struct arbol *tree, int valor);:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct arbol
{
    int numero;
    struct arbol *izq;
    struct arbol *der;
};
struct arbol *raiz = NULL;
struct arbol *eliminador = NULL;
int encontrado = 0;
int right = 0, left = 0;
int crear_arbol(int dato);
struct arbol * crear_nodo(int valor);
void ImprimeDNI (struct arbol *tree);
void ImprimeIND (struct arbol *tree);
void ImprimeNDI (struct arbol *tree);
void Buscar (struct arbol *tree, int valor);
void Eliminar (struct arbol *tree,int valor);
int Eliminaroot ();
int Eliminarright(struct arbol *localizador);
int Eliminarleft(struct arbol *localizador);
int main ()
{
    int n, i;
    char opcion;
    int numero;
    puts("Ingrese la cantidad de numeros a ingresar");
    scanf("%d", &n);
    int numeros[n];
    puts("Ingrese los numeros separados por espacio o enter");
    for(i = 0; i < n; i++)
    {
        scanf("%d",&numeros[i]);
    }
    for(i = 0; i < n; i++)
    {
        crear_arbol(numeros[i]);
    }
    puts("");
    system("pause");
    system("cls");
    do
    {
        encontrado = 0;
        puts("******** OPCIONES ********");
        puts("|B o b| Para buscar un numero");
        puts("|E o e| Eliminar un nodo");
        puts("|I o i| Imprimir de las 3 formas principales");
        fflush(stdin);
        opcion = getch();
        switch(opcion)
        {
        case 'B': case 'b': puts("Ingrese el numero a buscar"); scanf("%d",&numero); Buscar(raiz,numero);
        if(encontrado == 0) {puts("El numero no esta en el arbol");} break;
        case 'E': case 'e': puts("Ingrese el numero a eliminar"); scanf("%d", &numero);
        if(raiz->numero == numero)
        {
            Eliminaroot();
        }
        else
        {
            Eliminar(raiz,numero);
            if(right == 0 && left == 0)
            {
                puts("No se encontro el numero");
            }
            if(right == 1)
            {
                Eliminarright(eliminador);
            }
            if(left == 1)
            {
                Eliminarleft(eliminador);
            }
        }
        break;
        case 'I': case 'i': ImprimeDNI(raiz); puts(""); ImprimeIND(raiz); puts(""); ImprimeNDI(raiz); puts(""); break;
        default: puts("Opcion Invalida"); break;
        }
        puts("");
        system("pause");
        system("cls");
    }while (opcion != 'T' || opcion != 't');
    return 0;
}
int crear_arbol(int dato)
{
    struct arbol *recorrer = raiz;
    struct arbol *nuevo;
    if(raiz == NULL)
    {
        raiz = crear_nodo(dato);
        return 1;
    }
    else
    {
        nuevo = crear_nodo(dato);
    }
    while (1) {
        if(recorrer->numero <= nuevo->numero)
        {
            if(recorrer->der == NULL)//si las ramas de donde esta el puntero que recorre son NULL, significa
            { //que es la ultima comparacion
                recorrer->der = nuevo;
                break;
            }
            recorrer = recorrer->der;
        }
        else
        {
            if(recorrer->izq == NULL)//lo mismo que el if de arriba
            {
                recorrer->izq = nuevo;
                break;
            }
            recorrer = recorrer->izq;
        }
    }//while
    return 1;
}
struct arbol * crear_nodo(int valor)
{
    struct arbol *aux;
    aux = (struct arbol*)malloc(sizeof(struct arbol));
    aux->numero = valor;
    aux->izq = NULL;
    aux->der = NULL;
    return aux;
}
void ImprimeDNI (struct arbol *tree)
{
    if(!tree)
        return;
    ImprimeDNI(tree->der);
    printf("%d, ", tree->numero);
    ImprimeDNI(tree->izq);
}
void ImprimeIND (struct arbol *tree)
{
    if(!tree)
        return;
    ImprimeIND(tree->izq);
    printf("%d, ", tree->numero);
    ImprimeIND(tree->der);
}
void ImprimeNDI (struct arbol *tree)
{
    if(!tree)
        return;
    printf("%d, ", tree->numero);
    ImprimeNDI(tree->der);
    ImprimeNDI(tree->izq);
}
void Buscar (struct arbol *tree, int valor)
{
    if(tree->numero == valor)
    {printf("El numero si se encuentra en el arbol"); encontrado = 1;}
    if(!tree)
        return;
    Buscar(tree->der, valor);
    Buscar(tree->izq,valor);
}
int Eliminaroot ()
{
    int encontrado = 0;
    struct arbol *aux = raiz;
    struct arbol *buscador = raiz->der;
    for(; buscador->der != NULL ; buscador = buscador->der)
    {
        if(buscador->izq != NULL)
        {
            encontrado = 1;
        for(; buscador->izq->izq != NULL ; buscador = buscador->izq)
        {
        }
        break;
        }//if
    }
    if(encontrado == 0)
    {
        if(raiz->der == NULL)
        {
            raiz = aux->izq;
            raiz->izq = aux->izq->izq;
            raiz->der = aux->izq->der;
        }
        else
        {
        raiz = aux->der;
        raiz->izq = aux->izq;
        raiz->der = aux->der->der;
        free(aux);
        }
    }
    else
    {
    raiz = buscador->izq;
    raiz->der = aux->der;
    raiz->izq = aux->izq;
    buscador->izq = NULL;
    free(aux);
    }
    return 1;
}
void Eliminar (struct arbol *tree, int valor)
{
    if(tree->izq->numero == valor)
    {
        eliminador = tree;
        left = 1;
    }
    puts("AAAA");
    if(tree->der->numero == valor)
    {
        eliminador = tree;
        right = 1;
    }
    if(!tree)
        return;
    Eliminar(tree->der, valor);
    Eliminar(tree->izq, valor);
}
int Eliminarright(struct arbol *localizador)
{
    return 1;
}
int Eliminarleft(struct arbol *localizador)
{
    return 1;
}*

Answer 1

@PéterTörök's answer gets you part of the way there. It looks to me like you have a standard binary tree setup with "value less than" on the left and "value greater than" on the right (or perhaps >= if you allow duplicates).

It would be awfully good to get rid of the global variables, though (Eliminar sets eliminador and also a left/right flag), which you can do by using pointers-to-pointers. Instead of having Eliminar take a tree node, it can take a pointer to a tree node, and update it when removing a node. Furthermore, once a node has been removed, you can stop:

int Eliminar(struct arbol **tree_p, int valor)
{
    struct arbol *tree = *tree_p;

    if (!tree)
        return 0; /* nothing to remove */ 
    if (tree->numero == valor) {
        /* this is the node to remove */
        *tree_p = rewrite(tree); /* rewrite subtree from here down, and update */
        return 1; /* indicate that we're done */
    }
    /* didn't find the node to remove ... use left or right subtree for next attempt */
    tree_p = tree->numero > valor ? &tree->der : &tree->izq;
    return Eliminar(tree_p, valor);
}

(not sure if I got left/right correct above; I leave that for you to work on :-) ).

It's easy now to turn the recursion into iteration. The hard part is rewrite(), because you can have both left and right sub-trees of tree. If you have only one, it's easy, but if you have both, it's not so easy anymore. Again, I leave that as an exercise... :-)

You can have Eliminar return the actual removed tree node (or NULL if valor is not in the tree); that can be useful in some cases. In either case, you just do: result = Eliminar(&root, valor); to update the root node and get a success/fail indicator.

Answer 2

As Nick suggested, you should check that tree is valid at the beginning of Eliminar. However, if the first if statement executes fine, tree can't be NULL. tree->der can, though - you should check that too before dereferencing it. And of course, the same for tree->izq in the first if - just because it isn't NULL the very first time you call this function, don't assume it never will.

A few further notes: you are searching for the node having the value valor in Eliminar (which is thus a bad name - you aren't eliminating the node there, only marking it for later removal).

If you find it, there is no point continuing the search, so you can return right away from both if branches.

Moreover, you handle separately the cases when you find valor in the left or right subtree, by setting the left or right flags, and calling Eliminarleft or Eliminarright accordingly. It would be much simpler to store directly the left or right subtree to be removed, so then you can drop the two flags and the two removal methods:

void Eliminar (struct arbol *tree, int valor)
{
    if(!tree)
        return;
    if(tree->izq && tree->izq->numero == valor)
    {
        eliminador = tree->izq;
        return;
    }
    puts("AAAA");
    if(tree->der && tree->der->numero == valor)
    {
        eliminador = tree->der;
        return;
    }
    Eliminar(tree->der, valor);
    Eliminar(tree->izq, valor);
}

...
Eliminar(raiz,numero);
if(!eliminador)
{
    puts("No se encontro el numero");
}
else
{
    Eliminar(eliminador);
}

This is cleaner, but we can go even further. Notice that you are checking the left and right subtrees in Eliminar, then recursing on the same. It suffices instead to check only tree itself, then recurse:

void Eliminar (struct arbol *tree, int valor)
{
    if(!tree)
        return;
    if(tree->numero == valor)
    {
        eliminador = tree;
        return;
    }
    puts("AAAA");
    Eliminar(tree->der, valor);
    Eliminar(tree->izq, valor);
}

Answer 3

You're not checking the tree pointer at the top of your function, so could be causing an access violation on a null pointer. Move your if (!tree) return; check to the top of the function.