ABB (implementación).

   Esta entrada presenta la implementación de un ABB en base a dos enfoques respecto a la inserción de elementos:

1. Enfoque recursivo.
2. Enfoque iterativo.

   Para ambas implementaciones se utiliza la clase NodoABB definida en el Ejemplo NodoABB, por lo que será la primera clase que se describirá.

   La clase NodoABB define un nodo capaz de almacenar objetos genéricos. Cada nodo definido por la clase tiene la forma de cada uno de los nodos de la siguiente figura:

Árbol binario de búsqueda (ABB) conformado por objetos de la clase NodoABB.

 

    Observe además que cada objeto instanciado tendrá dos referencias a objetos como él, las cuales representarán referencias hacia el subárbol izquierdo (nodoIzquierdo) y hacia el subárbol derecho (nodoDerecho).

   Los detalles restantes deberían resultarle familiares al lector, ya que en esencia se refieren a un constructor y a los métodos de tipo set y get para cada uno de los atributos. Asegúrese de comprender el Ejemplo NodoABB en su totalidad antes de continuar.

Enfoque recursivo.

   Probablemente el enfoque más común para la implementación de un ABB debido a la naturaleza inherente a la definición de dicha estructura de datos, sea el enfoque basado en la recursividad.

   El Ejemplo ABBr muestra la definición de la clase ABBr, la cual es en esencia la implementación de la representación definida en el diagrama de clases UML presentado en la entrada ABB (representación y diseño).

   El estudio y la comprensión de la implementación de los métodos de recorrido para un árbol binario de búsqueda (líneas 34-68), se dejan como ejercicio para el lector.

   El método inserta (líneas 13-18), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, delega la responsabilidad de la inserción de elemento dentro de arbol al método privado recursivo insertaR (línea 17).

   Por su parte, la idea del método insertaR (líneas 21-32) es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:

• Si elemento es menor (línea 22), debe ser insertado en el subárbol izquierdo.
• Si el subárbol izquierdo está vacío o disponible (línea 23), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 24). Si no está vacío (línea 25), se recorre el subárbol izquierdo de manera recursiva (línea 26) para encontrar la posición apropiada para elemento dentro del subárbol.
• Si elemento es mayor (línea 27), debe ser insertado en el subárbol derecho.
• Si el subárbol derecho está vacío o disponible (línea 28), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 29). Si no está vacío (línea 30), se recorre el subárbol derecho de manera recursiva (línea 31) para encontrar la posición apropiada para elemento dentro del correspondiente subárbol.

   La clase de prueba para la clase ABBr del Ejemplo ABBr se muestra en el Ejemplo PruebaArbol.

   La clase PruebaArbol del Ejemplo PruebaArbol utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico; el cual, además de presentarse en la salida estándar (línea 15), representa el valor a ser insertado dentro del árbol binario de búsqueda (línea 16).

   Finalmente, el Ejemplo PruebaArbol realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Es ampliamente recomendable que el lector realice varias ejecuciones de la clase PruebaArbol y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.

Una posible salida de los Ejemplos PruebaArbol y Prueba ABB.

 

    Una posible salida para el Ejemplo PruebaArbol se muestra en la figura anterior.

Enfoque iterativo.

   Un enfoque alternativo para la implementación de la operación de inserción en un árbol binario de búsqueda, es utilizar un ciclo en lugar de recursividad.

   El enfoque propuesto es casi tan compacto como el recursivo pero mucho más eficiente. La implementación sin recursividad del ABB representado en el diagrama de clase de la entrada ABB (representación y diseño) se presenta en el Ejemplo ABB.

   Al igual que antes, el estudio y la comprensión de la implementación de los métodos de recorrido (líneas 34-68), se dejan como ejercicio para el lector.

   El método inserta (líneas 13-32), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, se genera una referencia alterna (línea 17) para recorrer el árbol (línea 18).

   Al igual que antes, la idea es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:

• Si elemento es menor (línea 19), debe ser insertado en el subárbol izquierdo.
• Si el subárbol izquierdo está vacío o disponible (línea 20), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 21). Si no está vacío (línea 22), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol izquierdo (línea 23) para encontrar la posición apropiada para elemento dentro del árbol.
• Si elemento es mayor (línea 24), debe ser insertado en el subárbol derecho.
• Si el subárbol derecho está vacío o disponible (línea 25), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 26). Si no está vacío (línea 27), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol derecho (línea 28) para encontrar la posición apropiada para elemento dentro del ABB.
• Finalmente, si el elemento no fue menor ni mayor, entonces por tricotomía de los números no le queda otra más que ser igual, en cuyo caso no hay nada por hacer mas que terminar (líneas 29 y 30).

   La clase de prueba para la clase ABB del Ejemplo ABB se muestra en el Ejemplo PruebaABB.

   Al igual que antes, la clase PruebaABB del Ejemplo PruebaABB utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico, el cual además de presentarse en la salida estándar (línea 15), representa el valor que será insertado dentro del árbol binario de búsqueda (línea 16).

   Finalmente, el Ejemplo PruebaABB también realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Una vez más, se recomienda ampliamente que el lector realice varias ejecuciones de la clase PruebaABB y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.

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.