0

hola buenas me gustaria que me puedan ayudar a resolver este problema estoy intentando Eliminar el nodo menor de un arbol binario de busqueda, pero el problema es que si el nodo menor es el padre de otros nose como reemplazarlo ? o si por ejemplo ese nodo es el ultimo tambien. tengo este codigo pero cuando imprimo me sale null

public class ArbolBinarioOrdenado {
    
    
       class Nodo
    {
        int info;
        Nodo izq, der;
    }
    Nodo raiz;
    int cant;
    int altura;

    public ArbolBinarioOrdenado() {
        raiz=null;
    }
    
    
      public void borrarMenor() {
        if (raiz!=null) {
            if (raiz.izq==null)
                raiz=raiz.der;
            else {
                Nodo atras=raiz;
                Nodo reco=raiz.izq;
                while (reco.izq!=null) {
                    atras=reco;
                    reco=reco.izq;
                    
            
                }    
                atras.izq=reco.der;
                
            }                  
        }
    
    }
    
    
    
    
}  

el problema como les comento es que nose como podria hacer considerando que el nodo menor pueda ser el padre de otros, en mi programa si valido que no se ingresen numeros repetidos entonces por alli esta facil porque no se pueden repetir numeros, pero les agradeceria si me ayudaran a poder eliminar ese nodo

1 respuesta 1

1

En un árbol de búsqueda binario, conceptualmente, los nodos de la izquierda siempre serán menores a su padre, y los de la derecha siempre serán mayores (entiendo que en tu implementación validas que no haya números repetidos).

Por esta razón, si un nodo X tiene un hijo izquierdo sabemos que X no es nuestro nodo menor. Su hijo izquierdo es por definición menor que X.

En este sentido nuestro nodo menor puede tener dos casos:

  1. No tiene hijos, en cuyo caso eliminamos la referencia desde tu nodo atras.
  2. Tiene un hijo derecho y puedes reemplazar este hijo derecho por el nodo que estas eliminando (atras.izq = reco.der).

Eso desde una vista puramente teorica. Ahora bien, en tu implementación te recomiendo revisarla para ver si estas haciendo el recorrido de la manera que esperas, por ejemplo:

if (raiz.izq==null)
    raiz=raiz.der;

en esa parte de tu codigo me parece que estas asumiendo que la raiz del arbol no puede ser tu nodo menor hasta donde entiendo, pero puede que la raiz del arbol sea efectivamente el nodo con el menor valor.

Espero sea de ayuda!

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.