davisf

Codificación Huffman Hola, a toda la comunidad taringuera. En esta ocasión voy a hablarles (escribirles) sobre un método de compresión sencillísimo: la codificación Huffman. En este post nos ocuparemos sólo de la parte conceptual del algoritmo sin deternos en los detalles rigurosos como la correctitud del algoritmo, prefijos, etc. El archivo de texto de ejemplo Empecemos con algo sencillo. Para esta entrada utilizaremos un archivo de texto plano con el siguiente contenido: yo compre pocas copas, pocas copas yo compre, como yo compre pocas copas, pocas copas yo pague Este texto contiene 94 caracteres (letras) y si damos una mirada al peso del archivo, nos daremos cuenta de que pesa unos 94 bytes más o menos. De lo anterior podemos intuir que cada carácter pesa 1 byte, y si, estamos en lo correcto. El código ASCII Cada carácter del archivo de texto pesa 1 byte, que es lo mismo que 8 bits (8 dígitos que sólo pueden ser ceros o unos). ¿Por qué pesan 8 bits? La respuesta se encuentra en el código ASCII. Cada carácter tiene una representación única de 8 bits en el código ASCII. Por ejemplo, el carácter "p" se representa en ASCII como 01110000. Se puede ver una tabla detallada del código ASCII en Wikipedia. En el texto de ejemplo tenemos 13 caracteres distintos; la codificación ASCII de estos caracteres son dados en la siguiente tabla: carácter ASCII y 01111001 o 01101111 00100000 c 01100011 m 01101101 p 01110000 r 01110010 e 01100101 a 01100001 s 01110011 , 00101100 g 01100111 u 01110101 Así, por ejemplo, la cadena (palabra) "copas" está compuesta por los caracteres "c" (01100011), "o" (01101111), "p" (01110000), "a" (01100001) y "s" (01110011). Así, la cadena "copas" tiene la siguiente representación binaria ASCII (los colores son sólo para distinguir): 0110001101101111011100000110000101110011 Observa que la cadena "copas" tiene un peso de 40 bits en codificación ASCII. ¿Por qué 8 bits? En esta sección, básicamente vamos a detallar la respuesta a la pregunta del por qué son necesarios 8 bits para representar a un carácter dando un pequeño repaso de los números binarios. Recordemos que cualquier numero en base 10 (decimal) puede representarse en base dos (binario) y viceversa. Por ejemplo, el número binario 11001 es 25 en decimal. Para transformar un número binario a decimal basta con sumar potencias de dos de acuerdo a la posición de los dígitos "1". Por ejemplo, para el número binario 11001, los dígitos "1" aparecen en las posiciones cero, tres y cuatro por lo que la suma de potencias de dos es: por cierto, el número binario 11001 es de 5 bits (cinco dígitos binarios). El alfabeto ASCII tiene un total de 256 caracteres disponibles como puede verse en la página web AsciiTable. Para poder representar de manera única a cada carácter, el código ASCII asigna a cada carácter un numero desde el 0 hasta el 255. Por ejemplo, el carácter "m" tiene asignado el número 109 que en binario es 1101101 (7 bits). El número 255 es 11111111 en binario; así, los caracteres ASCII tendrán una representación binario desde el 00000000 hasta el 11111111. Esta es la razón por la cual se necesitan 8 bits para representar a cada carácter de manera única en el código ASCII. Una primera idea (codificación de ancho fijo) En esta sección veremos una codificación basándonos en la siguiente observación: El texto de ejemplo no útiliza todos los caracteres del código ASCII. De hecho sólo utiliza 13 caracteres diferentes. Como no utilizamos los 256 caracteres ASCII, no necesitamos los 8 bits de representación ASCII. Creemos nuestra propia codificación asignando a cada carácter un número del 0 al 12. La siguiente tabla muestra los códigos de nuestra nueva codificación: carácter decimal binario y 0 0000 o 1 0001 2 0010 c 3 0011 m 4 0100 p 5 0101 r 6 0110 e 7 0111 a 8 1000 s 9 1001 , 10 1010 g 11 1011 u 12 1100 La palabra "copas" es codificado como (los colores son sólo para distinguir): 00110001010110001001 Observa que la cadena "copas" tiene 20 bits en esta nueva codificación. Así, hemos logrado reducir el peso del texto al 50%. Aunque hemos logrado una compresión del 50%, esta compresión no es la más óptima. Una mejor idea (codificación de ancho variable) En la sección anterior hemos logrado comprimir el peso del texto al 50% con una codificación de ancho constante; hemos llegado a esa codificación mediante la observación de que nuestro texto no utiliza todos los caracteres ASCII por lo que no son necesarios 8 bits sino 4 bits para su representación. Podemos idear otra codificación mediante la siguiente observación: Hay caracteres que aparecen con mayor frecuencia que otros mientras que hay otros que apenas aparecen en el texto. La siguiente tabla muestra la frecuencia con la que aparecen los caracteres en el texto: carácter frecuencia y 4 o 17 16 c 12 m 4 p 12 r 3 e 4 a 9 s 8 , 3 g 1 u 1 La idea está dada: dar a los caracteres de mayor frecuencia una codificación con menor cantidad de bits que los caracteres de menor frecuencia. Ahora la pregunta es: ¿de qué manera codificamos los caracteres para que tengan una cantidad de bits variable? La respuesta radica en la codificación Huffman, el cual proporciona una codificación óptima con ancho de bits variable. El núcleo de la codificación Huffman radica en la construcción del árbol de codificación Huffman. Construcción del árbol de codificación Huffman El algoritmo para construir el árbol de codificación Huffman es el siguiente: 1. Crear una lista de N hojas, a cada hoja le corresponde un carácter y su respectiva frecuencia. 2. Repetir hasta que sólo quede un árbol en la lista. 2.1. Buscar los dos árboles cuyas raíces tengan menor valor, sean "Min1" y "Min2". 2.2. Crear un nuevo árbol cuya raíz tiene como valor "Min1 + Min2" y tiene como hijos a los árboles "Min1" y "Min2". 2.3. Eliminar los árboles "Min1" y "Min2" de la lista e insertar en la lista el nuevo árbol creado en el paso anterior. 3. El árbol que queda en la lista es el árbol de codificación Huffman. Este algoritmo es algo impreciso (sobre todo por la notación) pero nos servirá para ilustrar la construcción del árbol de codificación Huffman. Es evidente que "la magia" se produce dentro de las iteraciones (paso 2), por lo que vamos a detallar sólo las iteraciones. Iteración 1 Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 12 y 13. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 1 y min2 = 1 Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 2 y cuyos hijos son los árboles min1 y min2. Paso 3. Eliminamos los árboles de las posiciones 12 y 13 e insertamos el nuevo árbol creado en la lista. Iteración 2 Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 11 y 12. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 3 y min2 = 2 Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 5 y cuyos hijos son los árboles min1 y min2. Paso 3. Eliminamos los árboles de las posiciones 11 y 12 e insertamos el nuevo árbol creado en la lista. Iteración 3 Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 7 y 8. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 3 y min2 = 4 Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 7 y cuyos hijos son los árboles min1 y min2. Paso 3. Eliminamos los árboles de las posiciones 7 y 8 e insertamos el nuevo árbol creado en la lista. Iteración 4 Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 1 y 5. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 4 y min2 = 4 Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 8 y cuyos hijos son los árboles min1 y min2. Paso 3. Eliminamos los árboles de las posiciones 1 y 5 e insertamos el nuevo árbol creado en la lista. Iteración 5 Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 7 y 8. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 5 y min2 = 7 Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 12 y cuyos hijos son los árboles min1 y min2. Paso 3. Eliminamos los árboles de las posiciones 7 y 8 e insertamos el nuevo árbol creado en la lista. Salida Al final obtendremos un árbol como el de la siguiente imagen: Los números intermedios no nos serán útiles por lo que resumimos el grafo con sólo caracteres como en la siguiente imagen: Observemos que los caracteres que aparecen con mayor frecuencia aparecen más cerca de la raíz que los que tienen menor frecuencia. Por ejemplo, el carácter "o", que tiene la mayor frecuencia, está más cerca de la raíz que los otros caracteres. Codificación Una vez creado el árbol de codificación Huffman, la codificación es sencilla. A cada carácter se le asignará un número binario dependiendo de su posición en el árbol. Vamos a mostrar la codificación con un ejemplo para que se entienda mejor. La ruta para llegar de la raíz al carácter "r" es derecha-izquierda-derecha-derecha-izquierda; si concatenamos la ruta y cambiamos izquierda por cero y derecha por uno obtenemos que el código para "r" es 10110 (observa la siguiente imágen). La siguiente tabla muestra los códigos Huffman para cada carácter del texto de ejemplo: carácter Huffman y 11110 o 00 110 c 100 m 11111 p 010 r 10110 e 10111 a 011 s 1110 , 10100 g 101010 u 101011 Observa que el caracter que se repite más (o) tiene una menor cantidad de bits, mientras que los caracteres que menos se repiten (u y g) tienen una mayor cantidad de bits. Ahora la cadena "copas" se codifica como 100000100111110 Ahora la cadena "copas" pesa 15 bits. El tamaño total del archivo de ejemplo viene dado por la suma #bits*frecuencia Ahora el archivo pesa 279/8 = 34.9 bytes; el tamaño original del archivo era 94 bytes por lo que se ha logrado que el archivo se comprima al 34.9/94 = 37.1% del archivo original. Además del archivo codificado, es necesario tener el árbol de codificación de Huffman para poder decodificarlo, por lo que el peso del archivo final pesará un poco más que 34.9 bytes. Decodificación La decodificación es muy sencilla. Sólo necesitaremos leer bit por bit e ir avanzando por el árbol de acuerdo al bit leído: si el bit es un cero, se avanza por la rama izquierda y si el bit es un uno se avanza por el lado derecho hasta encontrar una hoja, en cuyo caso tendremos el carácter decodificado; luego de decodificar un carácter se reinicia la ruta a seguir desde la raíz del árbol. Por ejemplo para decodificar la secuencia de bits "100001111100" leemos bit por bit de izquierda a derecha: - Leemos el primer bit (1): avanzamos por la derecha comenzando por la raíz. - Leemos el segundo bit (0): avanzamos por la izquierda desde el punto anterior. - Leemos el tercer bit (0): avanzamos por la izquierda desde el punto anterior. Se ha encontrado una hoja por lo que el carácter decodificado es "c" (se reinicia la ruta desde la raíz). - Leemos el cuarto bit (0): avanzamos por la izquierda comenzando por la raíz. - Leemos el quinto bit (0): avanzamos por la izquierda desde el punto anterior. Se ha encontrado una hoja por lo que el carácter decodificado es "o" (se reinicia la ruta desde la raíz) La cadena "100001111100" decodificado es "como".

Hola a toda la comunidad taringuera, hace tiempo que no posteo nada y espero que este post le sea útil a alguien. En esta ocasión les voy a presentar una estructura de datos que me costó mucho aprenderlo y asimilarlo: los arboles binarios, sobre todo me costó por la implementación pero una vez que le agarré la onda, hasta puedo implementarlo con poca o sin ayuda de libros. Comenzaré con la definición de un árbol binario para luego pasar a la carnesita del asunto: los arboles binarios de búsqueda que es por lo que vinieron. Creo, personalmente que más que los códigos lo que quiero que aprendan son los algoritmos involucrados pues seguramente sus implementaciones (que lo han hecho uds solos) son diferentes a la mía y si entienden los algoritmos podrán adaptarlos fácilmente a sus programas ¿Preparados? Árboles binarios Definición Nota: Esta definición es sacada del libro Algorithms de Cormen. Un árbol binario es una estructura de datos que o: - no contiene nodos, o - está compuesto de tres conjuntos disjuntos de nodos: una raíz, un árbol binario llamado subárbol izquierdo y un árbol binario llamado subárbol derecho. Si el árbol no contiene nodos, lo llamaremos árbol vacío. Si un árbol binario es no vacío y sus subárboles izquierdo y derecho son vacíos, diremos que el árbol es una hoja. Para dibujar un árbol binario seguiremos las siguientes reglas: - Representaremos en general a un árbol binario mostrando solamente su raíz como en la siguiente figura - Dibujaremos una hoja indicando solamente la raíz - Cuando el subárbol izquierdo (o derecho) de un árbol binario no sea vacío, dibujaremos una línea que va desde la raíz del árbol binario hasta la raíz de su subárbol izquierdo (o derecho). Así, construiremos y dibujaremos un árbol binario de la siguiente forma recursiva (de la forma que estamos acostumbrados): así, podemos dejarlo así como está o podemos llegar a todas las hojas si queremos. Implementación de la definición en Java Supondremos que el dato almacenado en la raíz de los árboles binarios son enteros. A continuación la clase ABB que moldea a un árbol binario tal como lo hemos definido (más adelante veremos por qué le pongo como nombre ABB) public class ABB { Integer raiz; ABB subABizq; ABB subABder; // Constructor de un arbol vacio public ABB() { raiz = null; subABizq = null; subABder = null; } // constructor de una hoja public ABB( Integer raiz ) { this.raiz = new Integer( raiz ); subABizq = null; subABder = null; } } Árboles binarios de búsqueda (ABB) Definición Un ABB es un árbol binario en la que se cumplen las siguientes condiciónes: - La raíz del subárbol izquierdo (si existe) es menor que su raíz. - La raíz del subárbol derecho (si existe) es mayor que su raíz. En la siguiente figura se muestra un ejemplo de un ABB: Operaciones sobre un ABB Antes de ver las operaciones que podemos realizar sobre un ABB vamos a crear un método "utilitario" para la clase ABB. Este método se llamará esVacio y servirá para saber si un árbol binario es vacío o no. Para saber si un árbol binario es vacío o no sólo tendremos que verificar si la raíz es nula o no, si no es nula entonces el árbol no será vacío. A continuación el código del método esVacio: // avisa si el arbol es vacío o no private boolean esVacio() { boolean vacio = true; if ( raiz != null ) vacio = false; return vacio; } Insertar La primera operación que haremos e implementaremos será la inserción. Para empezar no podemos insertar un nuevo nodo en donde nos de la gana. No debemos violar las propiedades de los árboles binarios. El algoritmo de inserción es el siguiente: - Si el árbol es vacío, entonces el nuevo nodo será la raíz del árbol (obvio) y finalizar. - Si no, ---- Se compara el valor del nuevo nodo con la raíz del árbol binario. ---- Si es menor entonces el nuevo nodo se inserta en su subárbol izquierdo (aplicar este algoritmo al subárbol izquierdo), ---- Si es mayor entonces el nuevo nodo se inserta en su subárbol derecho (aplicar este algoritmo al subárbol derecho). ---- Si son iguales, ignoramos el valor (así me gusta a mi, no es obligatorio) La siguiente secuencia de imágenes muestra al algoritmo en acción: Implementación de la operación de inserción en un ABB El siguiente método ejecuta la inserción en un ABB. // insercion de un nuevo nodo en el ABB public void insertar( Integer nuevo ) { if( esVacio() ) { raiz = new Integer( nuevo ); subABizq = new ABB(); subABder = new ABB(); } else { if( nuevo < raiz ) { subABizq.insertar(nuevo); } else if ( nuevo > raiz ) { subABder.insertar(nuevo); } } } Buscar Este método es análogo al método insertar: comparamos el valor a buscar con la raíz del árbol, si es menor buscamos en el subárbol izquierdo, si es mayor buscamos en el subárbol derecho, si no, es decir, si el valor a buscar es igual a la raíz entonces retornamos la referencia al árbol encontrado. Si el árbol es vacío entonces el valor buscado no existe en el árbol y retornamos el valor nulo (null). La siguiente figura muestra un ejemplo de esta operación: Implementación de la operación de búsqueda en un ABB El siguiente código muestra la implementación del método buscar: // devuelve una referencia al árbol con la raiz buscada, si no encuentra retorna null public ABB buscar( Integer x ) { ABB buscado = null; if( !esVacio() ) { if( x < raiz ) { buscado = subABizq.buscar(x); } else if ( x > raiz ) { buscado = subABder.buscar(x); } else { return this; } } return buscado; } Eliminar Este método me gusta (aunque no recuerdo si era el más eficiente, lo dudo). Recuerda que no podemos eliminar por eliminar pues quizás el resultado viole con la definicion de ABB. Antes de ir al algoritmo de eliminación es conveniente crear un par de métodos "utilitarios": los métodos buscarMin y esHoja. El método buscarMin retorna una referencia (no null) al menor elemento de un ABB. ¿Cuál es el menor elemento de un ABB? Observa los ABBs que utilizamos de ejemplo anteriormente y busca el menor elemento de los árboles ¿te diste cuenta de dónde está el menor elemento? El menor elemento se encuentra en el lado más a la izquierda posible. Así, para encontrar el menor elemento de un ABB deberemos recorrer los subárboles izquierdos hasta que encontremos un árbol vacío. La siguiente figura muestra la manera de hallar el menor elemento en un árbol: El siguiente código muestra el método buscarMin descrito: // retorna una referencia al elemento minimo de un arbol private ABB buscarMin() { ABB arbolActual = this; while( !arbolActual.subABizq.esVacio() ) { arbolActual = arbolActual.subABizq; } return arbolActual; } El método esHoja nos indica si un árbol es una hoja o no. Su implementación es muy simple, pues por definición un árbol es una hoja si sus subárboles son vacíos. // indica si el arbol es una hoja o no private boolean esHoja() { boolean hoja = false; if( subABizq.esVacio() && subABder.esVacio() ) { hoja = true; } return hoja; } Ahora sí, el método eliminar sigue el siguiente algoritmo: - Buscar el elemento a eliminar - Si el elemento a eliminar existe, seguir ---- Si el elemento a eliminar es una hoja, entonces se puede eliminar sin escrúpulos (obvio). ---- Si no es una hoja, -------- Buscar el menor elemento del subárbol derecho del nodo a eliminar, digamos 'min'. -------- Reemplazar el valor del nodo a eliminar con el valor de 'min'. -------- Eliminar el nodo 'min' del ABB recursivamente (aplicar este algoritmo al subárbol derecho). No estoy seguro de que hayas entendido el algoritmo con palabras, por eso la siguiente figura pretende aclarar ideas ¿entendiste? Implementación de la operación de eliminación en un ABB // elimina un nodo del ABB public void eliminar( Integer a ) { ABB aEliminar = buscar(a); if (aEliminar != null) { if( aEliminar.esHoja() ) { aEliminar.raiz = null; } else { ABB min = aEliminar.subABder.buscarMin(); aEliminar.raiz = min.raiz; min.eliminar(min.raiz); } } } Recorrido preorden Ya pasamos lo más complicado ahora vienen los métodos para mostrar un árbol binario en pantalla. Existen cuatro formas de recorridos en un árbol binario, tres de estos recorridos lo implementaremos sin problemas, para el cuarto recorrido (por nivel) será necesario el uso de colas, y no estoy asumiendo que sepas colas. En caso de que sepas colas, entonces puedes estudiar los 4 recorridos sino estudia los 3 primeros, estudias colas y finalmente vuelves y estudias la cuarta forma (estudiar es una manera de decir pues no es necesario saber la implementación detallada de una cola para saber qué es una estructura FIFO - primero en entrar primero en salir). En el recorrido preorden: - Primero se muestra la raíz de un árbol - luego se hace un recorrido preorden en el subárbol izquierdo y - finalmente se hace un recorrido preorden en el subárbol derecho Hay una manera fácil de encontrar los recorridos trazando una envoltura al árbol. El recorrido preorden se logra mediante un trazo que envuelve al árbol y mostrando los nodos cada vez que el trazo toca al lado izquierdo del nodo (este método es solamente visual). Por ejemplo en la siguiente figura el recorrido preorden es: 5 - 3 - 1 - 2 - 4 - 7 - 6 - 10 - 8 - 9 - 15 Implementación del recorrido preorden // recorrido en preorden public void preOrden() { if( !esVacio() ) { System.out.println( raiz ); subABizq.preOrden(); subABder.preOrden(); } } Recorrido enorden En el recorrido enorden: - Primero se hace un recorrido enorden en el subárbol izquierdo, - luego se muestra la raíz del árbol y - finalmente se hace un recorrido enorden en el subárbol derecho El recorrido enorden se logra mediante un trazo que envuelve al árbol y mostrando los nodos cada vez que el trazo toca al lado bajo del nodo (este método es solamente visual). Por ejemplo en la siguiente figura el recorrido enorden es: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 15 Implementación del recorrido enorden // recorrido enorden public void enOrden() { if( !esVacio() ) { subABizq.enOrden(); System.out.println( raiz ); subABder.enOrden(); } } Recorrido postorden En el recorrido postorden: - Primero se hace un recorrido postorden en el subárbol izquierdo, - luego se hace un recorrido postorden en el subárbol derecho y - finalmente se muestra la raíz del árbol. El recorrido postorden se logra mediante un trazo que envuelve al árbol y mostrando los nodos cada vez que el trazo toca al lado derecho del nodo (este método es solamente visual). Por ejemplo en la siguiente figura el recorrido postorden es: 2 - 1 - 4 - 3 - 6 - 8 - 9 - 15 - 10 - 7 - 5 Implementación del recorrido postorden // recorrido postorden public void postOrden() { if( !esVacio() ) { subABizq.postOrden(); subABder.postOrden(); System.out.println( raiz ); } } Recorrido por nivel Y para finlizar (el post). En este tipo de recorrido vamos a presentar primer los nodos que estén en el nivel 0 (la raíz), luego los que están en el lugar 1 (los hijos de la raiz), luego los hijos de estos, y así sucesivamente. Por ejemplo, en la siguiente figura la salida es: 5 - 3 - 7 - 1 - 4 - 6 - 10 - 2 - 8 - 15 - 9 El algoritmo para mostrar por nivel es el siguiente (nota que, sorprendentemente, no es recursivo): - Comenzamos encolando el árbol. - Repetir mientras la cola esté vacía. ---- Desencolar un árbol de la cola y mostrar su raíz. ---- Si el subárbol izquierdo es no vacío entonces encolar el subárbol izquierdo en la cola. ---- Si el subárbol derecho es no vacío entonces encolar el subárbol derecho en la cola. Para ilustrar el algoritmo, la siguiente serie de figuras muestran el algoritmo en acción: Implementación del recorrido por nivel // recorrido por nivel public void porNivel() { Vector<ABB> cola = new Vector<ABB>(); ABB arbol; cola.add(this); while( !cola.isEmpty() ) { arbol = cola.elementAt(0); cola.remove(0); System.out.println( arbol.raiz ); if ( !arbol.subABizq.esVacio() ) cola.add( arbol.subABizq ); if (!arbol.subABder.esVacio() ) cola.add( arbol.subABder ); } } A probar nuestro código Para probar nuestro código, tenemos dos archivos: ABB.java y Main.java El archivo ABB.java contiene lo siguiente: import java.util.Vector; public class ABB { Integer raiz; ABB subABizq; ABB subABder; // Constructor de un arbol vacio public ABB() { raiz = null; subABizq = null; subABder = null; } // constructor de una hoja public ABB( Integer raiz ) { this.raiz = new Integer( raiz ); subABizq = null; subABder = null; } private boolean esVacio() { boolean vacio = true; if ( raiz != null ) vacio = false; return vacio; } public void insertar( Integer nuevo ) { if( esVacio() ) { raiz = new Integer( nuevo ); subABizq = new ABB(); subABder = new ABB(); } else { if( nuevo < raiz ) { subABizq.insertar(nuevo); } else if ( nuevo > raiz ) { subABder.insertar(nuevo); } } } public ABB buscar( Integer x ) { ABB buscado = null; if( !esVacio() ) { if( x < raiz ) { buscado = subABizq.buscar(x); } else if ( x > raiz ) { buscado = subABder.buscar(x); } else { return this; } } return buscado; } private ABB buscarMin() { ABB arbolActual = this; while( !arbolActual.subABizq.esVacio() ) { arbolActual = arbolActual.subABizq; } return arbolActual; } private boolean esHoja() { boolean hoja = false; if( subABizq.esVacio() && subABder.esVacio() ) { hoja = true; } return hoja; } public void eliminar( Integer a ) { ABB aEliminar = buscar(a); if (aEliminar != null) { if( aEliminar.esHoja() ) { aEliminar.raiz = null; } else { ABB min = aEliminar.subABder.buscarMin(); aEliminar.raiz = min.raiz; min.eliminar(min.raiz); } } } public void preOrden() { if( !esVacio() ) { System.out.println( raiz ); subABizq.preOrden(); subABder.preOrden(); } } public void enOrden() { if( !esVacio() ) { subABizq.enOrden(); System.out.println( raiz ); subABder.enOrden(); } } public void postOrden() { if( !esVacio() ) { subABizq.postOrden(); subABder.postOrden(); System.out.println( raiz ); } } public void porNivel() { Vector<ABB> cola = new Vector<ABB>(); ABB arbol; cola.add(this); while( !cola.isEmpty() ) { arbol = cola.elementAt(0); cola.remove(0); System.out.println( arbol.raiz ); if ( !arbol.subABizq.esVacio() ) cola.add( arbol.subABizq ); if (!arbol.subABder.esVacio() ) cola.add( arbol.subABder ); } } } Y el archivo Main.java contiene lo siguiente public class Main { public static void main(String[] args) { ABB arbol = new ABB(); arbol.insertar(5); arbol.insertar(3); arbol.insertar(7); arbol.insertar(1); arbol.insertar(4); arbol.insertar(6); arbol.insertar(10); arbol.insertar(2); arbol.insertar(8); arbol.insertar(15); arbol.insertar(9); System.out.println("Mostrando por niveles:"); arbol.porNivel(); arbol.eliminar(11); System.out.println("Mostrando en preorden:"); arbol.preOrden(); arbol.eliminar(6); System.out.println("Mostrando en postorden (eliminado 6):"); arbol.postOrden(); } } Y así será la salida de ejecutar Main (no es lo mas bonito pero uds. lo maquillan): Mostrando por niveles: 5 3 7 1 4 6 10 2 8 15 9 Mostrando en preorden: 5 3 1 2 4 7 6 10 8 9 15 Mostrando en postorden (eliminado 6): 2 1 4 3 9 8 15 10 7 5 FIN Espero le haya servido a alguien. PD: Quisiera crearme un blog donde coloque este tipo de cosas (tutoriales, videos, códigos) ¿Alguien sabe como hacerlo? pero no en blogspot o wordpress, sino hacer uno propio en joomla o drupal por ejemplo pues veo muchos blogs que quedan muy buenos con esos CMS y no sé como se manejan esos bichos.