Ya te enseñé a implementar un árbol binario en Java, insertar elementos, recorrer de 3 maneras distintas y buscar un elemento pero no vimos cómo eliminar un elemento de ese ABB.

Por ello es que en este corto post de programación en Java vamos a ver cómo eliminar un nodo, hoja o dato de un árbol binario sin importar su posición y respetando a los nodos hijos en caso de que tenga.

Eliminar nodo de árbol binario en Java

Vamos al código. Queda así:

public void eliminar(int busqueda) {
    this.raiz = this.eliminar(this.raiz, busqueda);
}

private Nodo eliminar(Nodo nodo, int busqueda) {
    if (nodo == null) {
        return nodo;
    }
    if (busqueda > nodo.getDato()) {
        nodo.setDerecha(this.eliminar(nodo.getDerecha(), busqueda));
    } else if (busqueda < nodo.getDato()) {
        nodo.setIzquierda(this.eliminar(nodo.getIzquierda(), busqueda));
    } else {
        if (nodo.getIzquierda() == null && nodo.getDerecha() == null) {
            nodo = null;
        } else if (nodo.getDerecha() != null) {
            nodo.setDato(this.sucesor(nodo));
            nodo.setDerecha(this.eliminar(nodo.getDerecha(), nodo.getDato()));
        } else {
            nodo.setDato(this.predecesor(nodo));
            nodo.setIzquierda(this.eliminar(nodo.getIzquierda(), nodo.getDato()));
        }
    }
    return nodo;
}

private int sucesor(Nodo nodo) {
    nodo = nodo.getDerecha();
    while (nodo.getIzquierda() != null) {
        nodo = nodo.getIzquierda();
    }
    return nodo.getDato();
}

private int predecesor(Nodo nodo) {
    nodo = nodo.getIzquierda();
    while (nodo.getDerecha() != null) {
        nodo = nodo.getDerecha();
    }
    return nodo.getDato();
}

Se está usando la recursión o recursividad como en varias operaciones con los árboles binarios. En este caso lo que hacemos es:

1. Si el nodo a eliminar no tiene hijos, simplemente lo eliminamos.
2. En caso de que tenga hijos, le asignamos el valor de su predecesor o sucesor y recorremos todos los nodos.

Código completo

Como puedes ver, arriba solo te dejé el código relevante para eliminar un nodo de un binary tree en Java y maneja enteros. Recuerda que ya he publicado la implementación completa:

Incluso así, aquí te dejo un ejemplo completo pero te recomiendo leer el post citado anteriormente.

/*
  ____          _____               _ _           _
 |  _ \        |  __ \             (_) |         | |
 | |_) |_   _  | |__) |_ _ _ __ _____| |__  _   _| |_ ___
 |  _ <| | | | |  ___/ _` | '__|_  / | '_ \| | | | __/ _ \
 | |_) | |_| | | |  | (_| | |   / /| | |_) | |_| | ||  __/
 |____/ \__, | |_|   \__,_|_|  /___|_|_.__/ \__, |\__\___|
         __/ |                               __/ |
        |___/                               |___/

    Blog:       https://parzibyte.me/blog
    Ayuda:      https://parzibyte.me/blog/contrataciones-ayuda/
    Contacto:   https://parzibyte.me/blog/contacto/

    Copyright (c) 2020 Luis Cabrera Benito
    Licenciado bajo la licencia MIT

    El texto de arriba debe ser incluido en cualquier redistribución
* */
class Nodo {
    private int dato;
    private Nodo izquierda, derecha;

    public Nodo(int dato) {
        this.dato = dato;
        this.izquierda = this.derecha = null;
    }

    public int getDato() {
        return dato;
    }

    public void setDato(int dato) {
        this.dato = dato;
    }

    public Nodo getIzquierda() {
        return izquierda;
    }

    public void setIzquierda(Nodo izquierda) {
        this.izquierda = izquierda;
    }

    public Nodo getDerecha() {
        return derecha;
    }

    public void setDerecha(Nodo derecha) {
        this.derecha = derecha;
    }

    public void imprimirDato() {
        System.out.println(this.getDato());
    }
}

class Arbol {
    private Nodo raiz;

    public Arbol() {

    }

    public boolean existe(int busqueda) {
        return existe(this.raiz, busqueda);
    }

    private boolean existe(Nodo n, int busqueda) {
        if (n == null) {
            return false;
        }
        if (n.getDato() == busqueda) {
            return true;
        } else if (busqueda < n.getDato()) {
            return existe(n.getIzquierda(), busqueda);
        } else {
            return existe(n.getDerecha(), busqueda);
        }

    }

    public void insertar(int dato) {
        if (this.raiz == null) {
            this.raiz = new Nodo(dato);
        } else {
            this.insertar(this.raiz, dato);
        }
    }

    public void eliminar(int busqueda) {
        this.raiz = this.eliminar(this.raiz, busqueda);
    }

    private Nodo eliminar(Nodo nodo, int busqueda) {
        if (nodo == null) {
            return nodo;
        }
        if (busqueda > nodo.getDato()) {
            nodo.setDerecha(this.eliminar(nodo.getDerecha(), busqueda));
        } else if (busqueda < nodo.getDato()) {
            nodo.setIzquierda(this.eliminar(nodo.getIzquierda(), busqueda));
        } else {
            if (nodo.getIzquierda() == null && nodo.getDerecha() == null) {
                nodo = null;
            } else if (nodo.getDerecha() != null) {
                nodo.setDato(this.sucesor(nodo));
                nodo.setDerecha(this.eliminar(nodo.getDerecha(), nodo.getDato()));
            } else {
                nodo.setDato(this.predecesor(nodo));
                nodo.setIzquierda(this.eliminar(nodo.getIzquierda(), nodo.getDato()));
            }
        }
        return nodo;
    }

    private int sucesor(Nodo nodo) {
        nodo = nodo.getDerecha();
        while (nodo.getIzquierda() != null) {
            nodo = nodo.getIzquierda();
        }
        return nodo.getDato();
    }

    private int predecesor(Nodo nodo) {
        nodo = nodo.getIzquierda();
        while (nodo.getDerecha() != null) {
            nodo = nodo.getDerecha();
        }
        return nodo.getDato();
    }

    private void insertar(Nodo padre, int dato) {
        if (dato > padre.getDato()) {
            if (padre.getDerecha() == null) {
                padre.setDerecha(new Nodo(dato));
            } else {
                this.insertar(padre.getDerecha(), dato);
            }
        } else {
            if (padre.getIzquierda() == null) {
                padre.setIzquierda(new Nodo(dato));
            } else {
                this.insertar(padre.getIzquierda(), dato);
            }
        }
    }

    private void preorden(Nodo n) {
        if (n != null) {
            n.imprimirDato();
            preorden(n.getIzquierda());
            preorden(n.getDerecha());
        }
    }

    private void inorden(Nodo n) {
        if (n != null) {
            inorden(n.getIzquierda());
            n.imprimirDato();
            inorden(n.getDerecha());
        }
    }

    private void postorden(Nodo n) {
        if (n != null) {
            postorden(n.getIzquierda());
            postorden(n.getDerecha());
            n.imprimirDato();
        }
    }

    public void preorden() {
        this.preorden(this.raiz);
    }

    public void inorden() {
        this.inorden(this.raiz);
    }

    public void postorden() {
        this.postorden(this.raiz);
    }
}

class Main {
    public static void main(String[] argumentos) {
        Arbol arbol = new Arbol();
        arbol.insertar(5);
        arbol.insertar(3);
        arbol.insertar(6);
        arbol.insertar(2);
        arbol.insertar(4);
        arbol.insertar(7);
        System.out.println("Recorriendo inorden:");
        arbol.inorden();
        arbol.eliminar(5);
        System.out.println("Recorriendo inorden despues de eliminar:");
        arbol.inorden();
    }
}

Por aquí te dejo más tutoriales de Java en mi blog.