Arboles

Árboles {text:list-item} Alguna vez hemos visto ese conjunto de muñecos de madera de origen ruso (matrioshkas) en la que uno se encuentra dentro de otro. Dentro del primer muñeco, se encuentra un muñeco menor, y dentro de ese muñeco, hay otro muñeco de menor tamaño y así sucesivamente. Un método recursivo es como los muñecos rusos: se reproducen a sí mismo con versiones más y máspequeñas.
{draw:frame}
Recursión es la capacidad de un método o función de invocarse a sí mismo para resolver un problema [1]. Cada vez que un método se llama a sí mismo, se envía una parte más pequeña del problema, a fin de encontrar una solución a la misma.
En Java, un método puede llamar a otros métodos, pero además, ¡se puede llamar a sí mismo! Haciendo una llamada recursiva.
Larecursión se forma de dos elementos:
Caso base. El momento en que se detiene la recursión
Llamada recursiva. Invocación del método a sí mismo
Cuando se alcanza el caso base, la recursión comienza un proceso llamado “backtracking” (retroceso), resolviendo las llamadas anteriores de sí mismo.
Ejemplo clásico de recursión
El calculo del factorial de un número, es el método másrecurrido para explicar la recursión. Supongamos que solamente sabemos la definición de factorial:
El factorial de 0 (cero), es igual a 1 (caso base)
El factorial de N, es igual a N multiplicado por el factorial de N-1 (llamada recursiva)
Calculemos el factorial de 3
Factorial(3) = 3 x Factorial(3-1) // por definición
Factorial(3) = 3 x Factorial(2)
Pero ahora nos damoscuenta que desconocemos el factorial de 2, así que procedemos a calcularlo
Factorial(2) = 2 x Factorial(2-1) // por definición
Factorial(2) = 2 x Factorial(1)
Seguimos sin conocer el factorial de 3, de 2, y ahora de 1. Así que pasamos a calcular el factorial de 1
Factorial(1) = 1 x Factorial(1-1) // por definición
Factorial(1) = 1 x Factorial(0)
Conocemos el factorial de 0 (cero)que es 1 (nuestro caso base), por lo que comenzamos a resolver e iniciar el backtracking.
Factorial(1) = 1 x Factorial(0) = 1 x 1 = 1
Factorial(2) = 2 x Factorial(1) = 2 x 1 = 2
Factorial(3) = 3 x Factorial(2) = 3 x 2 = 6
El factorial de 3, es igual a 6 ( 3 x 2 x 1).
Para programar recursión, debemos tener en cuenta que siempre debe existir una forma de llegar al caso base, de locontrario, las llamadas recursivas serían infinitas. La recursión se utiliza siempre que deseemos resolver un problema a través de él mismo, mediante fracciones más sencillas de él.
Existen diversas aplicaciones para la recursión, tales como cálculos matemáticos, trabajo con listas o árboles, etc. Ejemplos:
Sucesión de Fibonacci
Encontrar un nodo hoja en árboles
Recorrer unalista
Etc
{text:list-item}
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura compuesta por un dato y varios árboles. La forma gráfica se puede apreciar como sigue:
{draw:frame}
En relación con los nodos, debemos definir algunos conceptos como:
Nodohijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, ‘L’ y ‘M’ son hijos de ‘G’.
Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, ‘A’ es padre de ‘B’, ‘C’ y ‘D’.
En cuanto a la posición dentro del árbol, tenemos:
Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para acceder al árbol. En el ejemplo,ese nodo es ‘A’.
Nodo hoja: nodo que no tiene hijos. En el ejemplo, hay varios: ‘K’, ‘M’, ‘O’, etc.
Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo ‘B’, ‘G’, ‘D’, ‘J’, etc.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:...