1

Estoy tratando de hacer un metodo que elimine un nodo de un arbol binario de busqueda de manera recursiva pero el codigo que tengo deja todo como exactamente igual.

public void borrar (Node nodo, int n){ // recibe el nodo raiz
   if (nodo == null){ // si el nodo es null no hace nada mas
     return;
    }
   else if (nodo.data==n){ // se mira si el dato del nodo es el que se quiere borrar
      if (nodo.left == null && nodo.right == null){ // si el nodo es una hoja simplemente se elimina
         nodo = null;
         return;
        }
      else if (nodo.left != null && nodo.right == null){// si el nodo solo tiene un hijo izquierdo el nodo se hace igual a ese hijo izquierdo
         nodo = nodo.left;                             
         return;
        }
      else if (nodo.left == null && nodo.right != null){// si el nodo solo tiene un hijo derecho el nodo se hace igual a ese hijo derecho
         nodo = nodo.right;
         return;
        }
      else { // si el nodo tiene dos hijos, como el ultimo elemento de la raiz izquierda siempre es menor al primer de la raiz derecha
         Node a = nodo.right; // el nodo pasa a ser la raiz izq y se pone esa raiz derecha como hija der de ese mismo nodo
         nodo = nodo.left;
         Node aux = nodo;
         while (true){
             if (nodo.right!=null){
                aux = a.right;
                }
             else {
                aux.right = a;
                break;
                }
            }
            return;
        }
    }

   if (n<nodo.data){ // recursion si el numero buscado es menor al que esta en el nodo actual se invoca a si mismo con el hijo izq
     borrar (nodo.left,n);
    }
   else { 
     borrar (nodo.right,n);// en cambio si es mayor o igual se invoca a si mismo con el hijo der 
    }
}
1
  • 1
    Es porque hiciste un metodo de buscar pero no eliminas en ningun momento el 9 nov. 2017 a las 15:22

1 respuesta 1

2

EL problema es que no eliminas el nodo. Al poner la variable a null simplemente estás perdiendo la referencia al nodo a borrar, pero el nodo sigue en el árbol: imagina que tienes una variable de tipo nodo que sea la raíz de un árbol con dos hijos:

Nodo raiz= ...; //dos hijos

Si yo creo una variable nueva que apunte a la raíz:

Nodo aux=raiz;

Tengo dos referencias (variables) apuntando al mismo objeto.

Si ahora pongo a null cualquiera de ellas:

raiz=null;

El árbol seguirá existiendo en la otra. Por tanto, si quieres borrar un nodo, lo que tienes que hacer es eliminar todas las referencias para que el reolector de basura se deshaga de ese nodo. Imagina que queremos quitar el nodo izquierdo, lo que tienes que hacer es:

//Hemos pasado el nodo árbol a nuestro método como el parámetro "nodo"
if (nodo.left!=null && nodo.left.data==n) { // encontramos el elemento a borrar
  Nodo aux=nodo.left;
  // código para recolocar los nodos hijos del que vamos a borrar...
  //supongamos que tiene un único hijo:
  nodo.left=aux.left;
  return; //salimos, el nodo original ya no está en el árbol y aux será borrada al salir del método
}

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.