Ejercicios selectos (árboles binarios).

Representación de un ABB.

1. Siguiendo las consideraciones descritas en el blog respecto a un ABB (entrada Árbol binario de búsqueda (ABB)), realice manualmente, es decir, en papel y lápiz, la inserción de la siguiente secuencia de elementos: 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17.
1. Aplique el recorrido en pre orden al árbol resultante.
2. Aplique el recorrido en orden al árbol resultante.
3. Aplique el recorrido en post orden al árbol resultante.
4. Aplique también el recorrido en pre orden inverso.
5. Aplique el recorrido en orden inverso al árbol resultante.
6. Aplique finalmente el recorrido en post orden inverso.
2. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 17, 20, 4, 16, 5, 3, 18, 7, 9, 4, 15, 14.
1. Aplique el recorrido en pre orden al árbol resultante.
2. Aplique el recorrido en orden al árbol resultante.
3. Aplique el recorrido en post orden al árbol resultante.
4. Aplique también el recorrido en pre orden inverso.
5. Aplique el recorrido en orden inverso al árbol resultante.
6. Aplique finalmente el recorrido en post orden inverso.
3. Modifique el Ejemplo PruebaArbol para que permita leer números desde la entrada estándar. Corrobore con el programa y los recorridos obtenidos en los ejercicios anteriores, que el árbol que genera el programa es el mismo que generó en papel y lápiz.
4. Basándose en el Ejemplo NodoABB, el Ejemplo ABBr, y el Ejemplo ABB, realice las modificaciones correspondientes en ambos tipos de implementación (recursiva e iterativa) para que, a través de métodos, proporcione solución a lo siguiente:
1. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r1 es padre de r2 (vea la figura que aparece al inicio de esta entrada).
2. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r2 es hijo de r1 (vea la figura que aparece al inicio de esta entrada).
3. Dada una referencia a un nodo cualquiera de un árbol binario, determine si dicho nodo es o no un nodo hoja.
4. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r1 es ancestro de r2.
5. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r2 es descendiente de r1.
6. Dada una referencia a un nodo cualquiera de un árbol binario, determine su nivel.
7. Determinar la altura o profundidad de un árbol binario.
8. Determinar si un árbol binario es o no un árbol estrictamente binario.
9. Determinar si un árbol binario es o no un árbol binario completo de profundidad p.
10. La implementación de las operaciones complementarias:
1. obtenPadre: regresa una referencia al padre de nd.
2. obtenHermano: regresa una referencia al hermano de nd.
3. esIzquierdo: regresa true si nd es un hijo izquierdo de algún otro nodo en el árbol binario, y false en caso contrario.
4. esDerecho: regresa true si nd es un hijo derecho de algún otro nodo en el árbol binario, y false en caso contrario.
5. Donde nd es una referencia a un nodo cualquiera de un árbol binario.
11. Determinar el número de nodos de un árbol binario.
12. La suma (se asume que el árbol binario almacena números) de todos los nodos del árbol binario.
5. Modifique el Ejemplo PruebaArbol para que almacene otro tipo de objetos además de los de la clase Integer. Pruebe con al menos las siguientes clases:
1. Float.
2. String.
3. Persona (del Ejemplo Persona).
4. Cientifico (del Ejemplo Cientifico).
6. Realice lo mismo que se pide en el ejercicio anterior, pero para el Ejemplo PruebaABB.
7. Modifique el Ejemplo PruebaABB para que:
1. En lugar de insertar números aleatorios en el árbol binario de búsqueda, solicite al usuario un número de datos n. Posteriormente deberá leer de la entrada estándar cada uno de los n datos, mismos que serán insertados en el ABB correspondiente.
2. Realice las comprobaciones de los recorridos y árboles generados manualmente. Un recorrido en preorden o postorden le hará saber si el árbol generado es correcto, tome en consideración que un recorrido en orden no le arrojará información útil al respecto.
3. Implemente los recorridos inversos descritos en la entrada (Árboles binarios (recorridos)). Nota: respecto a los recorridos inversos, resultaría sumamente conveniente que, previo a su implementación, realizara el diagrama de clases UML correspondiente basándose en el presentado en la entrada ABB (representación y diseño).
8. Con base en las consideraciones planteadas en el blog respecto a la eliminación de un ABB y al diagrama de clases UML presentado en la entrada ABB (eliminación), implemente la eliminación de elementos para un árbol binario de búsqueda, así como las modificaciones correspondientes mostradas en dicho diagrama.
9. Dada la siguiente secuencia de números: 4, 5, 7, 2, 1, 3, 6, genere en papel y lápiz su correspondiente ABB. Se deberá ilustrar paso a paso el proceso de inserción y realizar la comprobación de cada árbol con el programa generado en el Ejercicio 7.
10. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 6, 3, 1, 2, 7, 5, 4.
11. Dada la siguiente secuencia de números: 4, 5, 7, 2, 1, 3, 6, genere en papel y lápiz su correspondiente árbol AVL. Se deberá ilustrar paso a paso el proceso de inserción y rebalanceo.
12. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 6, 3, 1, 2, 7, 5, 4.
13. Dada la siguiente secuencia de números: 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 14, 10, 12, 17, 16, 18, generar:
1. El correspondiente ABB.
2. El correspondiente árbol AVL.
3. El correspondiente ABB pero con la secuencia de números invertida.
4. El correspondiente árbol AVL pero con la secuencia de números invertida.
5. En cada caso se deberá ilustrar paso a paso en cada uno de los árboles generados, el correspondiente proceso de inserción.
14. Respecto al ejercicio anterior:
1. ¿Qué conjeturas puede obtener?
2. ¿En qué tipo de árbol se genera el árbol de altura mínima?
3. ¿Cuáles serían las ventajas y desventajas de uno y otro esquema de representación de árbol y por qué?
15. Considere la figura (a) que aparece al final de esta entrada de ejercicios, misma que representa un árbol AVL. Utilizando papel y lápiz:
1. Elimine la siguiente secuencia de elementos: 4, 8, 6, 5, 2, 1, 7.
2. Deberá ilustrar paso a paso:
1. Los balances de cada uno de los nodos.
2. La identificación del nodo a eliminar y el proceso de rebalanceo a aplicar en caso de ser necesario.
3. El correspondiente árbol AVL.
3. La solución final al ejercicio se presenta en la figura (b).
16. Genere el diagrama de clases UML que represente el diseño de un árbol AVL en base a lo expuesto en el blog. Puede basarse en el diagrama de la entrada ABB (representación y diseño). La idea de este ejercicio es que su diseño derive en una implementación.
17. Realice la implementación de un árbol AVL. Tome en consideración que, además de mantener los elementos ordenados como en un ABB, en cada inserción deberá verificar el balance de los nodos, y que en caso de ser necesario, deberá aplicar los mecanismos de rebalanceo descritos en el blog para asegurar que el árbol generado es siempre un árbol AVL.
18. En la entrada Árboles binarios balanceados (AVL) se discuten los aspectos de los árboles AVL relacionados con el rebalanceo después de la inserción. Sin embargo, ¿qué pasa con la eliminación de elementos? Apoyándose en el blog y en el ejercicio anterior, analice y resuelva los aspectos implicados en la eliminación de nodos en un árbol AVL, e implemente una operación que permita realizar la eliminación de un elemento. Asegúrese de mantener siempre un árbol AVL.

(a) Árbol AVL inicial para la eliminación (adaptada del libro Algoritmos y Estructuras de Datos de Niklaus Wirth).

(b) Árbol AVL final después del proceso de eliminación.

Ejercicios selectos (transición).

1. Investigue más acerca del concepto de máquina virtual y de los bytecodes ¿Fue Java el primer lenguaje de programación en incorporar dichos conceptos?
2. Para el programa del Ejemplo Bienvenido2 pruebe lo que sucede si elimina el espacio que aparece al final de la cadena Bienvenid@. No olvide volver a compilar.
3. Considere el Ejemplo Bienvenido3 e investigue qué otras secuencias de escape existen, también infórmese si dichas secuencias coinciden o no con las que se utilizan en el lenguaje de programación C.
4. En base a lo expuesto para el Ejemplo Bienvenido4 investigue qué otros especificadores de formato existen. Infórmese también si dichos especificadores coinciden o no con los que se utilizan en el lenguaje de programación C.
5. Escriba un programa que imprima en la salida estándar su nombre (el nombre del lector). El nombre o nombres deberá aparecer en el primer renglón, el primer apellido en el segundo renglón y el segundo apellido en el tercer renglón.
6. Utilice el Ejemplo Lectura y cambie la clase Integer por el tipo primitivo int. Compruebe si es necesario o no hacer algún otro tipo de cambio para que el programa funcione.
7. En base a lo descrito en el Ejemplo Lectura modifique dicho ejemplo para agregar las cuatro operaciones aritméticas: suma, resta multiplicación y división. Los operadores aritméticos son los tradicionales: +, -, * y /. Realice lo anterior para números enteros representados como objetos (Integer), y como tipos de datos primitivos.
8. Modifique el Ejemplo Lectura para procesar ahora números Float y Double. Tome en cuenta que deberá consultar el API para cambiar el método nextInt por el método apropiado. Investigue también si existen los tipos de datos primitivos correspondientes (float y double).
9. Con base en lo descrito en el Ejemplo Lectura, modifique dicho ejemplo para que solicite al usuario su nombre completo. Tome en cuenta que deberá leer tres cadenas como se describe a continuación, y que su programa deberá imprimir el nombre completo por apellidos en una sola línea:
1. Su nombre o nombres.
2. Su primer apellido.
3. Su segundo apellido

 10. Para el Ejemplo If, ¿qué sucede si cambia la estructura de selección if por if-else? ¿Se obtiene el mismo funcionamiento? Si cambia el funcionamiento, ¿por qué? Determine su respuesta y después corroborela haciendo los cambios correspondientes. No olvide volver a compilar.

 11. Escriba un programa que presente un menú con las cuatro operaciones aritméticas y una opción para salir. Su programa deberá procesar la opción y realizar la operación correspondiente, así como mantenerse repitiendo el menú hasta que se proporcione la opción de "Salir". Investigue también si el lenguaje Java incorpora una estructura de selección múltiple (switch) como la del lenguaje C. Para este ejercicio, basta con utilizar una estructura if-else anidada. El menú deberá ser como se describe a continuación:

• Suma.
• Resta.
• Multiplicación.
• División
• Salir.

 12. Modifique el Ejemplo Arreglo para que, utilizando el procesamiento de argumentos en la línea de comandos como el que se hizo en el Ejemplo MainArgs acepte tres argumentos. Su programa deberá generar un arreglo de n enteros con un valor inicial para el primer elemento y un incremento para los demás. Observe que los elementos de args son cadenas, por lo que tendrá que consultar el API para utilizar métodos de conversión de cadenas a números enteros.

Sugerencia: consulte el método parseInt de la clase Integer. Los argumentos a procesar en la línea de comandos son:

• Tamaño del arreglo (n).
• Valor inicial (valor).
• Incremento (incremento).

 13. Siguiendo la idea del ejercicio anterior, escriba un programa que procese el tamaño (n) de un arreglo desde la línea de comandos y:

• Genere un arreglo de enteros de tamaño n.
• Solicite y almacene n enteros en el arreglo.
• Determine, haciendo un recorrido del arreglo, el número mayor.
• Determine, haciendo un recorrido del arreglo, el número menor.
• Determine, haciendo un recorrido del arreglo, el promedio (media aritmética).
• Determine, haciendo un recorrido del arreglo, la moda (el número que más veces aparece).
• Determine, haciendo un recorrido del arreglo, si un número determinado está o no en el arreglo (búsqueda lineal).

 14. Consulte al menos la entrada Excepciones para introducirse en el tema y ampliar un poco más su conocimiento respecto al uso y manejo básico de excepciones en Java.
 15. Considere el Ejemplo Coleccion. Investigue en el API las colecciones, particularmente la colección ArrayList y determine el funcionamiento del programa antes de compilarlo y ejecutarlo en la máquina virtual de Java. Compruebe su deducción respecto al funcionamiento con la salida real del programa. 

Ejemplos selectos de transición.

   Es imposible presentar, ya no digamos una entrada, sino en un blog completo un conjunto de ejemplos representativos para cualquier lenguaje de programación; sin embargo, en esta entrada se han seleccionado algunos ejemplos que pudieran ser de utilidad para la familiarización del lector con el lenguaje de programación Java, así como para comprender los ejemplos desarrollados en el blog.

Lectura de datos desde la terminal.
   Una de las tareas más comunes para cualquier programa es la lectura de datos desde la entrada estándar (teclado). Para los programas del blog que utilizan entrada de datos, se sugiere el enfoque que se presenta en el Ejemplo Lectura, el cual no hace uso de una interfaz gráfica de usuario (GUI) para centrar la atención en los aspectos relevantes (como la lectura de datos en este caso), y también para mantener más cortos los programas.

   El Ejemplo Lectura muestra en la línea 4 la importación de la clase Scanner del paquete java.util, el cual es un paquete con diversas utilerías; se recomienda en este momento echar un vistazo en el API de Java para tener una mejor idea de las clases que contiene el paquete java.util.

   Las instancias de la clase Scanner (como entrada) proporcionan diferentes servicios, entre ellos el método nextInt, el cual se encarga de obtener el siguiente número entero de la entrada estándar (líneas 17 y 19).

   Observe que el objeto entrada ha sido creado (línea 10) utilizando el objeto in de la clase System que, por decirlo de una manera simple, es la parte complementaria de System.out. Éste es el mecanismo usual para la entrada de datos. También note que han sido declarados tres objetos pertenecientes a la clase Integer (líneas 12-14).

   Java también maneja lo que se conoce como tipos de datos primitivos al estilo del lenguaje C; la clase Integer es en realidad una envoltura (wrapper) para el tipo de dato int. Una posible salida para el Ejemplo Lectura se muestra en la siguiente figura:

Una posible salida para el Ejemplo Lectura.

Estructuras de control.
   Java incorpora las estructuras de control tradicionales del enfoque estructurado, las cuales se asumen conocidas por el lector. Esta sección presenta un resumen necesariamente incompleto de las estructuras de control de selección y de repetición, con la única intención de tenerlas como una referencia inmediata.

   Estructuras de selección.
   El Ejemplo If muestra el uso de la estructuras de selección if y los operadores relacionales (líneas 20-31), así como el uso de la estructura de selección if-else (líneas 33-38).

   Los lectores familiarizados con el lenguaje de programación C notarán que tanto las estructuras de selección como los operadores relacionales son idénticos en Java, pero a diferencia de C, sí existe el tipo booleano, por lo que en Java es válido decir que una expresión se evalúa como verdadera o falsa según sea el caso.

   Note que las líneas 34 y 36 han hecho uso de una expresión de concatenación de cadenas de la forma:

objeto + cadena + objeto

lo cual es bastante común en Java. Dicha expresión lo que hace es precisamente concatenar las cadenas por medio del operador +. Note que aunque los objetos, como en el caso del ejemplo, no son cadenas, Java incorpora en la mayoría de sus clases el método toString, el cual se encarga de regresar una representación de cadena del objeto correspondiente.

   De hecho se recomienda que, en la medida de lo posible, las clases definidas por el usuario definan el método toString con la intención de mantener una compatibilidad con este tipo de situaciones como la que se acaba de describir. Tome en cuenta que aunque el método toString es heredado de la clase Object (la clase base en Java), es recomendable definir un comportamiento particular para una clase específica. Note también que no existe un llamado explícito del método sino un llamado implícito, mismo que se realiza a través del operador de concatenación de cadenas +.

   Una posible salida para el Ejemplo If se muestra en la siguiente figura:

Una posible salida para el Ejemplo If.

   Por otro lado, la siguiente tabla muestra la lista de operadores relacionales utilizados en Java:

Operador     Descripción

  ==            Igual que

    !=             Distinto de

                  <              Menor estricto que

                  >              Mayor estricto que

                <=             Menor o igual que

                >=             Mayor o igual que

   Estructuras de repetición.
   Las estructuras de repetición while, do-while y for se muestran respectivamente en los Ejemplos While, DoWhile y For.

   Los Ejemplos While, DoWhile y For se explican por sí mismos. Note que en los tres ejemplos se ha utilizado el tipo de dato primitivo int para la variable de control contador. La salida de los tres ejemplos es la misma, y se muestra en la siguiente figura:

Salida de los Ejemplos While, DoWhile y For.

Arreglos.
   El Ejemplo Arreglo muestra la creación, recorrido e impresión de un arreglo de enteros primitivos (int).

   La línea 7 define al objeto arreglo como un arreglo de enteros. Observe que el objeto es creado (new), con un tamaño específico (diez).

   Adicionalmente se definen también un par de variables:

1. Un valor inicial: valor (línea 8).
2. Un incremento: incremento (línea 9)

   Los arreglos en Java al ser creados y definidos como objetos, tienen definido el atributo público length, mismo que almacena la longitud del arreglo. Dicha propiedad es la que se utiliza como expresión condicional en los ciclos for de las líneas 12 y 17 respectivamente.

   El primer ciclo recorre el arreglo para inicializar y asignar los valores al arreglo en función de valor, incremento y la variable de control i.

   Por otro lado, el segundo ciclo realiza un recorrido tradicional para la impresión del arreglo en la salida estándar. La salida del Ejemplo Arreglo se muestra en la siguiente figura:

Salida del Ejemplo Arreglo.

Argumentos en la línea de comandos.
   El Ejemplo MainArgs muestra la forma de procesar los argumentos en la invocación de un programa, lo cual resultará útil y necesario en diversas ocasiones, como es el caso de algunos de los ejercicios planteados en el blog.

   El objeto args es un arreglo de cadenas (línea 6), por lo que en la línea 7 se verifica si se han proporcionado o no argumentos en la línea de comandos; en caso de que no, se reporta en la línea 8:

Salida del Ejemplo MainArgs sin argumentos.

 

    Si se proporcionaron argumentos, entonces se procesa la lista de argumentos con un ciclo (línea 10) y se imprime en la salida estándar dicha lista de argumentos, mismos que están almacenados en el arreglo de cadenas args:

Una posible salida del Ejemplo MainArgs con argumentos.

Excepciones.
   Las excepciones permiten una abstracción sobre el mecanismo de manejo de errores ligeros o condiciones que un programa pudiera estar interesado en atrapar y procesar.

   La idea subyacente en las excepciones es separar el manejo de este tipo de condiciones o errores de la lógica de funcionamiento inherente al programa.

   Una excepción es una situación anormal en la lógica de ejecución esperada por un programa, como el intentar clonar un objeto que no tiene implementado el mecanismo de clonación por ejemplo, manejar un formato de datos inadecuado para algún especificador, intentar realizar una operación de E/S en un canal cerrado, intentar acceder a elementos de una estructura de datos que no contiene elementos, entre muchísimas otras más.

   En la práctica, es posible definir en Java clases que gestionen excepciones o errores de una aplicación en particular. De hecho, una de las intenciones de las excepciones es la de, ante una problemática determinada, tratar de solucionarla en la medida de lo posible para continuar con el programa o aplicación, y no la de terminar con la primera dificultad que se presente.

   Un manejo completo y robusto de excepciones es una labor que, si bien su dominio no requiere de años, tampoco es una tarea trivial y queda fuera de los alcances de esta sección. Para obtener un poco más de información, refiérase a las entradas correspondientes relacionadas con las excepciones, en el contenido temático.

   Para muchos de los ejemplos desarrollados en el blog se hará uso (directo o indirecto) de la excepción definida por la clase RuntimeException del API, la cual maneja el conjunto de excepciones generadas durante la ejecución.

   La clase Throwable es la clase base de todas las excepciones que pueden ser lanzadas en Java, por lo que la revisión y estudio de esta jerarquía de clases del API es un punto inicial fundamental tanto para la comprensión de las excepciones, como para su referencia permanente. La relación de la jerarquía de clases en la que se encuentra la clase Exception en el contexto de Java, se expresa en un diagrama de clases de UML (Unified Modeling Language) de la siguiente figura:

Relación UML de la jerarquía de clases Exception de Java.

   La clase Throwable tiene dos derivaciones:

1. Error: condiciones excepcionales que son externas al programa o la aplicación; usualmente no es posible anticiparlas o recuperarse de ellas (mal funcionamiento del hardware o del sistema). Los programas sencillos normalmente no atrapan o lanzan este tipo de excepciones.
2. Excepción: indican que ocurrió algún problema pero, al menos en principio, no un problema serio. La mayoría de los programas que escriba atraparán o lanzarán este tipo de excepciones en lugar de los de la clase Error.

   La clase RuntimeException es un tipo especial de excepción reservada para indicar el uso incorrecto de un API por ejemplo. En este sentido, el Ejemplo ExcepcionEDVacia muestra la definición de una excepción bastante sencilla pero útil; de hecho, la clase mostrada en dicho ejemplo es la que se utiliza para las estructuras de datos desarrolladas en el blog.

   Note que la excepción ExcepcionEDVacia es una subclase de la clase RuntimeException. La clase RuntimeException es la super clase de las excepciones que pueden ser lanzadas durante la ejecución de la máquina virtual de Java.

Genéricos.
   La definición de jdk 5.0 introdujo nuevas modificaciones y extensiones a Java; una de ellas fue el aspecto relacionado con los genéricos (generics).

   Los genéricos son en sí mismos todo un tema de estudio, pero dado que se utilizan en la mayoría de los ejemplos del blog respecto a la definición de las estructuras de datos, aquí se presenta una exagerada y necesariamente incompleta y breve introducción.

Los genéricos permiten una abstracción sobre los tipos de datos o los objetos que se procesan, y dentro de sus objetivos se encuentran el eliminar la ambigüedad latente que existía en la conversión forzada de tipos (cast) y lo molesto de su realización, ya que usualmente un programador sabe cual es el tipo de dato que está procesando cuando utiliza una colección de datos por ejemplo.

   El siguiente fragmento de código, se utilizaba antes de los genéricos:

      List lista = new LinkedList();
      lista.add("Genericos en Java");
      String cadena = (String) lista.get(0);

   Con los genéricos el programador pone una marca (clase o tipo de datos en particular) por decirlo de alguna manera, para restringir los datos a almacenar y recuperar:

      List<String> lista = new LinkedList<String>();
      lista.add("Genericos en Java");
      String cadena = lista.get(0);

  El cambio es aparentemente simple pero significativo ya que evita los errores intencionales o accidentales en tiempo de ejecución, además de que permite al compilador hacer una verificación sobre los tipos de datos que se gestionan. Note que en el segundo fragmento de código, el cast ha sido eliminado.