ARBOLES GENERALES

ARBOLES GENERALES

________________________________________

1. INTRODUCCIÓN.

Hasta ahora las estructuras de datos que hemos estudiado eran de tipo lineal, o sea,existía una relación de anterior y siguiente entre los elementos que la componían(cada elemento tendrá uno anterior y otro posterior , salvo los casos de primero y último).Pues bien, aquí se va a estudiar una estructuración de los datos más compleja: los árboles.

Este tipo de estructura es usual incluso fuera del campo de la informática.El lector seguramente conoce casos como los árboles gramaticales para analizar oraciones,los árboles genealógicos ,representación de jerarquías,etc...La estructuración en árbol de los elementos es fundamental dentro del campo de la informática aplicándose en una amplia variedad de problemas como veremos más adelante.

En principio podemos considerar la estructura de árbol de manera intuitiva como una estructura jerárquica.Por tanto,para estructurar un conjunto de elementos ei en árbol, deberemos escoger uno de ellos e1 al que llamaremos raíz del árbol.Del resto de los elementos se selecciona un subconjunto e2,...,ek estableciendo una relación padre-hijo entre la raíz y cada uno de dichos elementos de manera que e1 es llamado el padre de e2,de e3,...ek y cada uno de ellos es llamado un hijo de e1.Iterativamente podemos realizar la misma operación para cada uno de estos elementos asignando a cada uno de ellos un número de 0 o más hijos hasta que no tengamos más elementos que insertar.El único elemento que no tiene padre es e1,la raíz del árbol.Por otro lado hay un conjunto de elementos que no tienen hijos aunque sí padre que son llamados hojas.Como hemos visto la relación de paternidad es una relación uno a muchos.

Para tratar esta estructura cambiaremos la notación:

• Las listas tienen posiciones.Los árboles tienen nodos.

• Las listas tienen un elemento en cada posición.Los árboles tienen una etiqueta en cada nodo (algunos autores distinguen entre árboles con y sin etiquetas.Un árbol sin etiquetas tiene sentido aunque en la inmensa mayoría de los problemas necesitaremos etiquetar los nodos. Es por ello por lo que a partir de ahora sólo haremos referencia a árboles etiquetados).

Usando esta notación,un árbol tiene uno y sólo un nodo raíz y uno o más nodos hoja.

Desde un punto de vista formal la estructura de datos árbol es un caso particular de grafo, más concretamente,en la teoría de grafos se denota de forma similar como árbol dirigido. A pesar de ello,la definición formal más usual de árbol en ciencias de la computación es la recursiva:

• El caso básico es un árbol con un único nodo.Lógicamente este nodo es a la vez raíz y hoja del árbol.

• Para construir un nuevo árbol a partir de un nodo nr y k árboles A1 ,A2,...,Ak de raíces n1,n2,...,nk con N1,N2,...,Nk elementos cada uno establecemos una relación padre-hijo entre nr y cada una de las raíces de los k árboles.El árbol resultante de N=1 + N1 + ... + Nk nodos tiene como raíz el nodo nr, los nodos n1,n2,...,nk son los hijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. Además a cada uno de los Ai se les denota subárboles de la raíz.

Ejemplo: Consideremos el ejemplo de la siguiente figura.

Podemos observar que cada uno de los identificadores representa un nodo y la relación padre-hijo se señala con una línea.Los árboles normalmente se presentan en forma descendente y se interpretan de la siguiente forma:

• E es la raíz del árbol.

• S1,S2,S3 son los hijos de E.

• S1,D1 componen un subárbol de la raíz.

• D1,T1,T2,T3,D3,S3 son las hojas del árbol.

• etc...

Además de los términos introducidos consideraremos la siguiente terminología:

1. Grado de salida o simplemente grado.Se denomina grado de un nodo al número de hijos que tiene.Así el grado de un nodo hoja es cero.En la figura anterior el nodo con etiqueta E tiene grado 3.

2. Caminos.Si n1,n2,...,nk es una sucesión de nodos en un árbol tal que ni es el padre de ni+1 para 1<=i<=k-1 ,entonces esta sucesión se llama un camino del nodo ni al nodo nk.La longitud de un camino es el número de nodos menos uno, que haya en el mismo.Existe un camino de longitud cero de cada nodo a sí mismo.Ejemplos sobre la figura anterior:

 E,S2,D2,T3 es un camino de E a T3 ya que E es padre de S2,éste es padre de D2,etc.

 S1,E,S2 no es un camino de S1 a S2 ya que S1 no es padre de E.

3. Ancestros y descendientes.Si existe un camino,del nodo a al nodo b ,entonces a es un ancestro de b y b es un descendiente de a.En el ejemplo anterior los ancestros de D2 son D2,S2 y E y sus descendientes D2,T1,T2 y T3(cualquier nodo es a la vez ancestro y descendiente de sí mismo). Un ancestro o descendiente de un

...