Hola a todos, hoy os dejaré compartido el código del árbol binario de búsqueda que hemos hecho en el canal de Youtube.
Para los últimos métodos añadidos, necesitáis la lista enlazada, de aquí:
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.
Aquí te dejo el repositorio de Github.
Espero que os sea de ayuda. Si tenéis dudas, preguntad. Estamos para ayudarte.
A este no se le puede agregar un objeto de tipo Persona, empleado etc, ya que no sale .
Te equivocas, puedes insertar objetos del tipo Persona ya que es es generico.