/** * Árbol binario de búsqueda * @author rcrespo */ public class ArbolBB { /** * Nodo del árbol binario de búsqueda */ class NodoBB { private Comparable clave; private Object info; public ArbolBB hijoIzq; public ArbolBB hijoDer; NodoBB(Comparable clave, Object info) { this.clave = clave; this.info = info; hijoIzq = new ArbolBB(); hijoDer = new ArbolBB(); } } private NodoBB raiz; public ArbolBB() { raiz = null; } /** * Comprueba si el árbol está vacío * @return true si el árbol está vacío o false si no. */ public boolean isVacio() { return raiz == null; } /** * Devuelve el objeto almacenado en el nodo cuya clave asociada coincide con la que se pasa como parámetro. * @param clave cadena de texto a buscar * @return objeto almacenado con la clave buscada */ public Object buscar(Comparable clave) { Object resultado = null; if (raiz != null) { // si el árbol no está vacío if (clave.compareTo(raiz.clave) < 0) { // Si la clave a buscar es menor que la de la raíz // busca en el subárbol izquierdo resultado = raiz.hijoIzq.buscar(clave); } else if (clave.compareTo(raiz.clave) > 0) { // Si la clave a buscar es mayor que la de la raíz // busca en el subárbol derecho resultado = raiz.hijoDer.buscar(clave); } else { // Clave encontrada resultado = raiz.info; } } return resultado; } /** * Inserta un nuevo elemento en el árbol, con la clave y la información indicadas * @param clave del nuevo elemento * @param info nuevo objeto a almacenar */ public void insertar(Comparable clave, Object info) { if (isVacio()) { // Si el árbol está vacío, insertar el nuevo elemento como raíz raiz = new NodoBB(clave, info); } else { if (clave.compareTo(raiz.clave) < 0) { // clave menor -> insertar en hijo izquierdo raiz.hijoIzq.insertar(clave, info); } else if (clave.compareTo(raiz.clave) > 0) { // clave mayor -> hijo derecho raiz.hijoDer.insertar(clave, info); } else { // clave igual -> insertar aquí raiz.info = info; } } } /** * Presenta por salida estándar todas las entradas del árbol, siguiendo el recorrido pre-orden. * Para cada nodo, se presenta: * 1º Información almacenada en el nodo * 2º Hijo izquierdo * 3º Hijo derecho */ public void mostrarPreOrden() { if (!isVacio()) { // Datos del nodo actual (raíz) System.out.println("Clave: " + raiz.clave); System.out.println("Información: "); System.out.println(raiz.info); raiz.hijoIzq.mostrarPreOrden(); // Imprimir subárbol izquierdo raiz.hijoDer.mostrarPreOrden(); // Imprimir subárbol derecho } } /** * Presenta por salida estándar todas las entradas del árbol, siguiendo el recorrido in-orden, * de modo que la información aparece ordenada. * Para cada nodo, se presenta: * 1º Hijo izquierdo * 2º Información almacenada en el nodo * 3º Hijo derecho */ public void mostrarInOrden() { if (!isVacio()) { raiz.hijoIzq.mostrarInOrden(); // Imprimir subárbol izquierdo // Datos del nodo actual (raíz) System.out.println("Clave: " + raiz.clave); System.out.println("Información: "); System.out.println(raiz.info); raiz.hijoDer.mostrarInOrden(); // Imprimir subárbol derecho } } public void pintarH(int centro) { if(raiz!=null) { raiz.hijoIzq.pintarH(centro - 2); for (int i = 0; i < centro; i++) System.out.print(" "); System.out.println(raiz.info); raiz.hijoDer.pintarH(centro - 2); } } /* metodo que devuelve el número de elementos mayores que uno dado en t: * debe recorrer el arbol comparando con todos los elementos e ir sumando * uno cada vez que se cumpla el criterio */ public int elementosMayoresQue(Comparable t) { int res = 0; if(raiz!=null) { res = res + raiz.hijoIzq.elementosMayoresQue(t); if (raiz.clave.compareTo(t)>0) res = res + 1; res = res + raiz.hijoDer.elementosMayoresQue(t); } return res; } /* metodo que recorre el arbol (aprovechando la ordenación de los elementos, recuerde que * es un árbol binario) y va almacenando el camino. El camino corresponde a la sucesión de * atributos info de los nodos del arbol que encuentra en el camino. Debe añadirlos a una String * de forma que se pueda imprimir por pantalla. Utilice el método toString() sobre el atributo * en concreto */ public String caminoAElemento(Comparable t) { String res = ""; if (buscar(t) == null) return res; if (raiz != null) { res = res + raiz.info.toString() + " "; if (t.compareTo(raiz.clave) < 0) { res = res + raiz.hijoIzq.caminoAElemento(t); } else if (t.compareTo(raiz.clave) > 0) { res = res + raiz.hijoDer.caminoAElemento(t); } } return res; } public static void main(String[] args) { /* Arbol de prueba */ ArbolBB arbol = new ArbolBB(); arbol.insertar(new Integer(10), "i10"); arbol.insertar(new Integer(5), "i05"); arbol.insertar(new Integer(7), "i07"); arbol.insertar(new Integer(3), "i03"); arbol.insertar(new Integer(4), "i04"); arbol.insertar(new Integer(2), "i02"); arbol.insertar(new Integer(1), "i01"); arbol.insertar(new Integer(6), "i06"); arbol.insertar(new Integer(9), "i09"); arbol.insertar(new Integer(8), "i08"); arbol.insertar(new Integer(15), "i15"); arbol.insertar(new Integer(17), "i17"); arbol.insertar(new Integer(13), "i13"); arbol.insertar(new Integer(14), "i14"); arbol.insertar(new Integer(12), "i12"); arbol.insertar(new Integer(11), "i11"); arbol.insertar(new Integer(16), "i16"); arbol.insertar(new Integer(19), "i19"); arbol.insertar(new Integer(18), "i18"); arbol.insertar(new Integer(20), "i20"); arbol.pintarH(10); /* Prueba de mayores que */ System.out.println("Elementos mayores que 2: " + arbol.elementosMayoresQue(new Integer(2))); System.out.println("Elementos mayores que 11: " + arbol.elementosMayoresQue(new Integer(11))); System.out.println("Elementos mayores que 16: " + arbol.elementosMayoresQue(new Integer(16))); System.out.println("Elementos mayores que 20: " + arbol.elementosMayoresQue(new Integer(20))); /* Prueba de obtener camino */ System.out.println("-------------"); System.out.println(arbol.caminoAElemento(new Integer(11))); } }