OpcionesLa 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
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:
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 partirde esta clase NodoBinario se define la clase ArbolBinario
como sigue:
