Árboles en Java

Es una estructura de datos bidimensional no lineal, con propiedades especiales. Los nodos de un árbol contienen dos o más enlaces, uno de los cuales puede ser null. El nodo raíz es el primer nodo en un árbol. Cada enlace en el nodo raíz hace referencia a un hijo. El hijo izquierdo es el primer nodo en el subárbol izquierdo (también conocido como el nodo raíz del subárbol izquierdo), y el hijo derecho es el primer nodo en el subárbol derecho (también conocido como el nodo raíz del subárbol derecho). Los hijos de un nodo específico se llaman hermanos. Un nodo sin hijos se llama nodo hoja. Generalmente, los científicos computacionales dibujan árboles desde el nodo raíz hacia abajo; exactamente lo opuesto a la manera en que crecen los árboles naturales.

Representación:

Analicemos el programa del árbol binario. El método main de la clase PruebaArbol empieza creando una instancia de un objeto Árbol vacío y asigna su referencia a la variable árbol (línea 10). En las líneas 17 a 22 se generan 10 enteros al azar, cada uno de los cuales se inserta en el árbol binario mediante una llamada al método insertarNodo (línea 21). Después el programa realiza recorridos (líneas 25, 28 y 31, respectivamente). 

La clase Arbol (líneas 44 a 113) tiene un campo private llamado raiz (línea 46); una referencia tipo NodoArbol al nodo raíz del árbol. El constructor de Arbol (líneas 49 a 52) inicializa raiz con null para indicar que el árbol está vacío. La clase contiene el método insertarNodo (líneas 55 a 61) para insertar un nuevo nodo en el árbol, además de los métodos recorridoPreorden (líneas 64 a 67), recorridoPreorden (líneas 81 a 84) y recorri doPostorden (líneas 98 a 101) para empezar recorridos del árbol. 

Colas en Java - Estructura de Datos

Una cola es similar a la fila para pagar en un supermercado: el cajero atiende primero a la persona que se encuentra hasta adelante. Los demás clientes entran a la fila sólo por su parte final y esperan a que se les atienda. Los nodos de una cola se eliminan sólo desde el principio (cabeza) de la misma y se insertan sólo al final (cola) de esta. 

Por esta razón, a una cola se le conoce como estructura de datos PEPS (primero en entrar, primero en salir). Las operaciones para insertar y eliminar se conocen como enqueue (agregar a la cola) y dequeue (retirar de la cola).

Estructura:

Método insertar al final

Obtener cima

Ejemplo:

El método main de la clase PruebaCola (figura 17.14) crea un objeto de la clase Cola llamado cola. En las líneas 13, 15, 17 y 19 se agregan a la cola cuatro enteros, aprovechando la conversión autoboxing para insertar objetos Integer en la cola. En las líneas 27 a 32 se utiliza un ciclo whi 1 e infinito para sacar de la cola los objetos, en el orden “primero en entrar, primero en salir”. Cuando la cola está vacía, el método dequeue lanza una excepción Excepci onLi staVaci a y el programa muestra el rastreo de la pila para esa excepción.