Árbol Binario de Búsqueda en Java

Hola a todos, hoy os dejaré compartido el código del árbol binario de búsqueda que hemos hecho en el canal de Youtube.

Aquí os lo dejo para descargar:

http://yoitect.com/9nof

Para los últimos métodos añadidos, necesitáis la lista enlazada, de aquí:

Entrada Lista dinámica

Aquí tenéis el código:

Nodo Arbol Binario
package ejercicio_ed_15_discoduroderoer;

public class NodoArbolBinario<T extends Comparable<T>> {

    private T element;
    private NodoArbolBinario<T> parent;
    private NodoArbolBinario<T> left;
    private NodoArbolBinario<T> right;

    public NodoArbolBinario(T element) {
        this.element = element;
    }

    public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
        this.element = element;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }

    public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
        this.element = element;
        this.parent = parent;
    }

    public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
        this.element = element;
        this.left = left;
        this.right = right;
    }

    public T getElement() {
        return element;
    }

    public void setElement(T element) {
        this.element = element;
    }

    public NodoArbolBinario<T> getParent() {
        return parent;
    }

    public void setParent(NodoArbolBinario<T> parent) {
        this.parent = parent;
    }

    public NodoArbolBinario<T> getLeft() {
        return left;
    }

    public void setLeft(NodoArbolBinario<T> left) {
        this.left = left;
    }

    public NodoArbolBinario<T> getRight() {
        return right;
    }

    public void setRight(NodoArbolBinario<T> right) {
        this.right = right;
    }

}
Arbol binario

 

package ejercicio_ed_15_discoduroderoer;

import lista_dinamica.ListaDinamica;

/**
 * Arbol binario de busqueda o BST
 *
 * @author DDR
 * @param <T>
 */
public class BinarySearchTree<T extends Comparable<T>> {

    //Nodo principal
    private NodoArbolBinario<T> root;

    /**
     * Indica si el arbol esta vacio
     *
     * @return true si esta vacio
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * Devuelve el nodo root
     *
     * @return nodo root
     */
    public NodoArbolBinario<T> getRoot() {
        return root;
    }

    /**
     * Indica si el nodo pasado es el root
     *
     * @param nodo
     * @return true si el nodo es el root
     */
    public boolean isRoot(NodoArbolBinario<T> nodo) {
        return root == nodo;
    }

    /**
     * Indica si es una hoja el nodo pasado como parametro
     *
     * @param nodo
     * @return true si es una hoja
     */
    public boolean isLeaf(NodoArbolBinario<T> nodo) {
        return nodo.getLeft() == null && nodo.getRight() == null;
    }

    /**
     * Indica si el nodo pasado como parametro tiene nodos hijos
     *
     * @param nodo
     * @return
     */
    public boolean isInternal(NodoArbolBinario<T> nodo) {
        return !isLeaf(nodo);
    }

    /**
     * Añade un nodo de forma recursiva
     *
     * @param origen
     * @param elemento
     * @return nodo añadido
     */
    public NodoArbolBinario<T> add(NodoArbolBinario<T> origen, T elemento) {

        NodoArbolBinario<T> nodo = null;
        //Si el root es nulo, lo añade el primero
        if (root == null) {
            nodo = new NodoArbolBinario<>(elemento);
            root = nodo;
        } else if (origen == null) { //el parametro pasado es invalido
            System.out.println("El origen es nulo");
        } else {

            //Comparamos los elementos
            //Si el nodo del origen es mayor que el elemento pasado, pasa a la izquierda
            if (origen.getElement().compareTo(elemento) > 0) {

                //Si tiene nodo izquierdo, hago la llamada recursiva
                if (origen.getLeft() != null) {
                    nodo = add(origen.getLeft(), elemento);
                } else {
                    //Creo el nodo
                    nodo = new NodoArbolBinario<>(elemento);
                    //Indico que el padre del nodo creado
                    nodo.setParent(origen);
                    //Indico que el nodo es el nodo izquierdo del origen
                    origen.setLeft(nodo);
                }

            } else { //sino pasa a la derecha

                //Si tiene nodo derecho, hago la llamada recursiva
                if (origen.getRight() != null) {
                    nodo = add(origen.getRight(), elemento);
                } else {
                    //Creo el nodo
                    nodo = new NodoArbolBinario<>(elemento);
                    //Indico que el padre del nodo creado
                    nodo.setParent(origen);
                    //Indico que el nodo es el nodo izquierdo del origen
                    origen.setRight(nodo);
                }

            }

        }

        return nodo;

    }

    /**
     * Añade un nodo de forma iterativa
     *
     * @param elemento
     * @return nodo añadido
     */
    public NodoArbolBinario<T> add(T elemento) {

        NodoArbolBinario<T> nodo = null;
        //Si el root es nulo, lo añade el primero
        if (root == null) {
            nodo = new NodoArbolBinario<>(elemento);
            root = nodo;
        } else {

            //Creo un nodo auxuliar
            NodoArbolBinario<T> aux = root;
            boolean insertado = false;
            //No salgo hasta que este insertado
            while (!insertado) {

                //Comparamos los elementos
                //Si el nodo del origen es mayor que el elemento pasado, pasa a la izquierda
                if (aux.getElement().compareTo(elemento) > 0) {

                    //Si tiene nodo izquierdo, actualizo el aux
                    if (aux.getLeft() != null) {
                        aux = aux.getLeft();
                    } else {
                        //Creo el nodo
                        nodo = new NodoArbolBinario<>(elemento);
                        //Indico que el padre del nodo creado
                        nodo.setParent(aux);
                        aux.setLeft(nodo);
                        //indico que lo he insertado
                        insertado = true;
                    }

                } else {

                    if (aux.getRight() != null) {
                        aux = aux.getRight();
                    } else {
                        //Creo el nodo
                        nodo = new NodoArbolBinario<>(elemento);
                        //Indico que el padre del nodo creado
                        nodo.setParent(aux);
                        aux.setRight(nodo);
                        //indico que lo he insertado
                        insertado = true;
                    }

                }

            }

        }

        return nodo;

    }

    /**
     * Recorre los nodos, primero el padre y despues los hijos
     *
     * @param nodo
     */
    public void preorder(NodoArbolBinario<T> nodo) {

        System.out.println(nodo.getElement().toString());

        if (nodo.getLeft() != null) {
            preorder(nodo.getLeft());
        }

        if (nodo.getRight() != null) {
            preorder(nodo.getRight());
        }

    }

    /**
     * Recorre los nodos, lo recorre de izquierda a derecha
     *
     * @param nodo
     */
    public void inorder(NodoArbolBinario<T> nodo) {

        if (nodo.getLeft() != null) {
            inorder(nodo.getLeft());
        }

        System.out.println(nodo.getElement().toString());

        if (nodo.getRight() != null) {
            inorder(nodo.getRight());
        }

    }

    /**
     * Recorre los nodos, primero los hijos y luego el padre
     *
     * @param nodo
     */
    public void postorder(NodoArbolBinario<T> nodo) {

        if (nodo.getLeft() != null) {
            postorder(nodo.getLeft());
        }

        if (nodo.getRight() != null) {
            postorder(nodo.getRight());
        }

        System.out.println(nodo.getElement().toString());

    }

    /**
     * Determina la altura del arbol desde el nodo dado
     *
     * @param nodo
     * @return
     */
    public int height(NodoArbolBinario<T> nodo) {

        int height = 0;

        if (isInternal(nodo)) {

            if (nodo.getLeft() != null) {
                height = Math.max(height, height(nodo.getLeft()));
            }

            if (nodo.getRight() != null) {
                height = Math.max(height, height(nodo.getRight()));
            }

            height++;
        }

        return height;

    }

    /**
     * Devuelve la profundidad desde el nodo dado
     *
     * @param nodo
     * @return
     */
    public int depth(NodoArbolBinario<T> nodo) {

        int depth = 0;

        if (nodo != getRoot()) {
            depth = 1 + depth(nodo.getParent());
        }

        return depth;

    }

    private final int ONE_NODE_LEFT = 1;
    private final int ONE_NODE_RIGHT = 2;
    private final int TWO_NODES = 3;

    /**
     * Elimina el nodo indicados
     *
     * @param nodo
     */
    public void remove(NodoArbolBinario<T> nodo) {

        if (root == null) {
            System.out.println("No hay nodos que borrar");
        } else if (isLeaf(nodo)) {
            removeLeaf(nodo);
        } else if (nodo.getRight() != null && nodo.getLeft() == null) {
            removeWithChlid(nodo, ONE_NODE_RIGHT);
        } else if (nodo.getRight() == null && nodo.getLeft() != null) {
            removeWithChlid(nodo, ONE_NODE_LEFT);
        } else {
            removeWithChlid(nodo, TWO_NODES);
        }

    }

    /**
     * Elimina un nodo hoja
     *
     * @param nodo
     */
    private void removeLeaf(NodoArbolBinario<T> nodo) {

        if (isRoot(nodo)) {
            root = null;
        } else {

            NodoArbolBinario<T> parent = nodo.getParent();

            if (parent.getLeft() == nodo) {
                parent.setLeft(null);
            }

            if (parent.getRight() == nodo) {
                parent.setRight(null);
            }

            nodo = null;

        }

    }

    /**
     * Elimina un nodo interno, varia segun el numero de hijos y posicion
     *
     * @param nodo
     * @param type_node
     */
    private void removeWithChlid(NodoArbolBinario<T> nodo, int type_node) {

        NodoArbolBinario<T> siguiente = null;

        switch (type_node) {
            case ONE_NODE_LEFT:
                siguiente = nodo.getLeft();
                break;
            case ONE_NODE_RIGHT:
                siguiente = minSubTree(nodo.getRight());
                break;
            case TWO_NODES:

                siguiente = minSubTree(nodo.getRight());

                if (!isRoot(siguiente.getParent())) {

                    nodo.getLeft().setParent(siguiente);
                    nodo.getRight().setParent(siguiente);

                    if (siguiente.getParent().getLeft() == siguiente) {
                        siguiente.getParent().setLeft(null);
                    } else if (siguiente.getParent().getRight() == siguiente) {
                        siguiente.getParent().setRight(null);
                    }

                }

                break;
        }

        siguiente.setParent(nodo.getParent());

        if (!isRoot(nodo)) {

            if (nodo.getParent().getLeft() == nodo) {
                nodo.getParent().setLeft(siguiente);
            } else if (nodo.getParent().getRight() == nodo) {
                nodo.getParent().setRight(siguiente);
            }

        } else {
            root = siguiente;
        }

        if (nodo.getRight() != null && nodo.getRight() != siguiente) {
            siguiente.setRight(nodo.getRight());
        }

        if (nodo.getLeft() != null && nodo.getLeft() != siguiente) {
            siguiente.setLeft(nodo.getLeft());
        }

        nodo = null;

    }

    /**
     * Calcula el valor minimo de un subarbol
     *
     * @param nodo
     * @return
     */
    private NodoArbolBinario<T> minSubTree(NodoArbolBinario<T> nodo) {

        if (nodo != null && nodo.getLeft() != null) {
            while (!isLeaf(nodo)) {
                nodo = minSubTree(nodo.getLeft());
            }

        }

        return nodo;
    }

    public NodoArbolBinario<T> getNode(NodoArbolBinario<T> nodo, T elemento) {

        NodoArbolBinario<T> aux = null;

        if (nodo.getElement().compareTo(elemento) == 0) {
            aux = nodo;
        } else {
            if (nodo.getLeft() != null) {
                aux = getNode(nodo.getLeft(), elemento);
            }

            if (nodo.getRight() != null) {
                aux = getNode(nodo.getRight(), elemento);
            }
        }

        return aux;
    }

    public T getElement(NodoArbolBinario<T> nodo, T elemento) {

        NodoArbolBinario<T> aux = getNode(nodo, elemento);

        if (aux == null) {
            return null;
        }

        return aux.getElement();
    }

    public void getNodes(NodoArbolBinario<T> nodo, T elemento, ListaDinamica<NodoArbolBinario<T>> lista_nodos) {

        if (nodo.getElement().compareTo(elemento) == 0) {
            lista_nodos.addLast(nodo);
        }

        if (nodo.getLeft() != null) {
            getNodes(nodo.getLeft(), elemento, lista_nodos);
        }

        if (nodo.getRight() != null) {
            getNodes(nodo.getRight(), elemento, lista_nodos);
        }

    }

    public ListaDinamica<T> getElements(NodoArbolBinario<T> nodo, T elemento) {

        ListaDinamica<T> elementos = new ListaDinamica<>();
        ListaDinamica<NodoArbolBinario<T>> lista_nodos = new ListaDinamica<>();

        getNodes(nodo, elemento, lista_nodos);

        for (NodoArbolBinario<T> aux : lista_nodos) {

            elementos.addLast(aux.getElement());

        }

        return elementos;

    }

    public void mostrar(NodoArbolBinario<T> nodo) {

        int profundidad = this.depth(nodo);

        for (int i = 0; i < profundidad; i++) {
            System.out.print(" ");
        }
        
        System.out.println("- "+nodo.getElement().toString());

        if (nodo.getLeft() != null) {
            mostrar(nodo.getLeft());
        }

        if (nodo.getRight() != null) {
            mostrar(nodo.getRight());
        }

    }

}

También os dejo una serie de vídeos donde hemos ido creando poco a poco este árbol.

Espero que os sea de ayuda. Si teneis dudas, preguntad. Estamos para ayudarte.

¿Te ha gustado y quieres apoyarme? ¡Sé mi patrón!
Etiquetas

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *