Articulos de interes

Curso online gratuito - POO y Java - Click Aquí

Árboles en Java

La estructura de datos árbol al contrario que las listas es una estructura de datos no lineal. Las listas tienen un orden impuesto en sus elementos teniendo como mucho un predecesor y un sucesor. Los árboles pueden tener dos o más sucesores.

Un árbol consiste en un conjunto de nodos o vértices y un conjunto de aristas o arcos que satisface unos requisitos:

  • Existe una jerarquía de nodos, de forma que a cada nodo hijo le llega una arista de otro nodo padre. De esta forma se establece la relación padre-hijo: p es padre de h, h es un hijo de p.
  • El nodo donde comienza la jerarquía se llama nodo raíz. A este nodo no llegan arcos de ningún otro nodo, en otras palabras, no es hijo de ningún nodo padre.
  • Existe un camino único entre la raíz y cualquiera de los nodos del árbol
Arbol

Veremos ahora un poco de terminología relacionada con los árboles. En primer lugar estudiaremos qué tipos de nodos nos podremos encontrar en un árbol. Hemos visto que existe un nodo especial, el nodo raiz que no tiene padres. El caso de los nodos que no tienen hijos es el de los nodos externos o nodos hoja. El resto de nodos son internos, cuando tiene descendientes. Diremos que un nodo es descendiente de otro, si es hijo de él ó descendiente de sus hijos. Los descendientes nos determinan un subárbol con raíz el nodo descendiente.

Veremos ahora aquellos conceptos que nos dan una idea sobre la topología del árbol. Son los conceptos de camino, longitud y profundidad:

  • El camino existente entre dos nodos, es la secuencia de "arcos" que nos llevan, siguiéndolas de forma consecutiva del primero al segundo. La longitud es el número de aristas que contiene.
  • Profundidad de un nodo es la longitud del camino de la raíz a ese nodo.
  • Altura de un árbol es la profundidad máxima entre todos los nodos extremos del árbol. Es decir, "la profundidad del nodo más profundo".

Por simplificar el estudio de los árboles veremos el caso de los árboles binarios. Un árbol binario es un árbol en el que cada nodo tiene 0 ó 2 hijos (el hijo izquierdo y el derecho). Este árbol podrá ser ordenado si para cada nodo existe un orden lineal para todos su hijos, es decir, si tenemos el orden "menor que", un árbol será ordenado si para cada nodo sus hijos son menores que el padre.

Al igual que las listas la forma de definir los árboles es de manera recursiva. Definiremos inicialmente una clase Nodo que represente cada uno de los nodos del árbol:

Colas

Cada uno de los objetos de tipo NodoBinario representa una estructura de datos compuesta por el elemento que se almacena en cada nodo y dos nodos que llamaremos nodoizqy nododcha. Puesto que los nodos binario pueden tener 0 ó 2 hijos, se han definido dos tipos de constructores para cubrir los dos casos. El resto de métodos son para manipular la clase nodo de forma transparente. A partir de esta clase NodoBinario se define la clase ArbolBinario como sigue:

Colas

Notesé que un ArbolBinario como máximo puede tener un hijo, si es el caso usaremos el constructor con un solo parámetro si no es así utilizaremos el constructor por defecto, es decir, el constructor sin parámetros.

Un ArbolBinario no es mas que un NodoBinario llamado raiz. Vemos en el siguiente esquema cómo sería gráficamente la estructura del árbol:

Esquema de un árbol binario

Vamos a ver cómo se calcularía el tamaño del árbol a partir de esta definición:

Colas

Definimos una función auxiliar que calcula el tamaño de un subárbol bajo un nodo. Este método calcula una longitud 0 si el Nodo es nulo. En otro caso, la longitud será la suma de los tamaños de los nodos hijos más uno, correspondiente al nodo actual. El método tamaño llama al método tam_aux con el nodo raiz.

Veremos las distintas formas de recorrer un árbol en el capítulo de Exploración de árboles




Nombre:

Email:

Comentario: