1

El código que estoy haciendo acerca de cómo encontrar un NODO en un ÁRBOL BINARIO no funciona, me sirve solo para los nodos que se encuentran directamente a la izquierda de la RAÍZ del arbol.

A continuación escribo el código

public Nodo encontrarNodo(Nodo raiz, String dato){

        if(raiz!=null){
                if(raiz.getIzquierda()!=null){

                    if(dato.equals(raiz.getDato())){

                        return raiz;
                    }else{
                        return encontrarNodo(raiz.getIzquierda(), dato);
                    }
                }

                if(raiz.getDerecha()!=null){
                    if(dato.equals(raiz.getDato())){
                            return raiz;
                    } else{
                            return encontrarNodo(raiz.getDerecha(), dato);
                    }   
                }
        }

        return null;


    }
2

1 respuesta 1

1

Para ver si un dato está en el árbol, el dato tiene que estar en la raíz, en su subárbol izquierdo o en su subárbol derecho.

Dicho de otra forma:

  • Si el árbol está vacío, el dato no puede estar en el árbol.
  • Si el dato está en la raíz, entonces he encontrado el nodo.
  • Si no está en la raíz, entonces hay que mirar en el subárbol izquierdo (recursividad)
  • Si no está en el subárbol izquierdo, hay que mirar en el subárbol derecho. (recursividad)
  • Si no está en el subárbol derecho (y por lo tanto tampoco en el izquierdo, ni en la raíz) es que el dato no está en el árbol.

Pasando esto a código:

public Nodo encontrarNodo(Nodo raiz, String dato) {
  Nodo retval;
  if (raiz == null) {
     retval = null; // Árbol vacío o callejón sin salida.
  } else {
     if (dato.equals(raiz.getDato()) {
        retval = raiz; // El dato está en la raíz.
     } else {
        Nodo izq = encontrarNodo(raiz.getIzquierda(), dato);
        if (izq == null) {
           Nodo der = encontrarNodo(raiz.getDerecha(), dato);
           if (der == null) {
             retval = null; // El dato no se ha encontrado
           }  else {
             retval = der; // El dato estaba en algún nodo del subárbol derecho
           }
        } else {
           retval = izq; // El dato estaba en algún nodo del subárdbol izquierdo
        }
     }
  }
  return retval;
} 

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

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