ARBOLES GENERALES

. 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 nodo,distinto de sí mismo,se llama un ancestro propio o descendiente propio respectivamente.Podemos definir en términos de ancestros y descendientes los conceptos de raíz,hoja y subárbol:

     • En un árbol,la raíz es el único nodo que no tiene ancestros propios.

     • Una hoja es un nodo sin descendientes propios.

     • Un subárbol de un árbol es un nodo,junto con todos sus descendientes.

• • 1. Algunos autores prescinden de las definiciones de ancestro propio y descendiente propio asumiendo que un nodo no es ancestro ni descendiente de sí mismo.

• 4. Altura.La altura de un nodo en un árbol es la longitud del mayor de los caminos del nodo a cada hoja.La altura de un árbol es la altura de la raíz.Ejemplo: en la figura anterior la altura de S2 es 2 y la del árbol es 3.

  5. Profundidad.La profundidad de un nodo es la longitud del único camino de la raíz a ese nodo.Ejemplo: en la figura anterior la profundidad de S2 es 1.

  6. Niveles.Dado un árbol de altura h se definen los niveles 0...h de manera que el nivel i está compuesto por todos los nodos de profundidad i.

  7. Orden de los nodos.Los hijos de un nodo usualmente están ordenados de izquierda a derecha.Si deseamos explícitamente ignorar el orden de los dos hijos, nos referiremos a un árbol como un árbol no-ordenado.

  8. La ordenación izquierda-derecha de hermanos puede ser extendida para comparar cualesquiera dos nodos que no están relacionados por la relación ancestro-descendiente.La regla a usar es que si n1 y n2 son hermanos y n1 está a la izquierda de n2, entonces todos los descendientes de n1 están a la izquierda de todos los descendientes de n2.

• • RECORRIDOS DE UN ÁRBOL.

  • En una estructura lineal resulta trivial establecer un criterio de movimiento por la misma para acceder a los elementos, pero en un árbol esa tarea no resulta tan simple.No obstante, existen distintos métodos útiles en que podemos sistemáticamente recorrer todos los nodos de un árbol.Los tres recorridos más importantes se denominan preorden,inorden y postorden aunque hay otros recorridos como es el recorrido por niveles.

  • Si consideramos el esquema general de un árbol tal como muestra la figura siguiente,los recorridos se definen como sigue: 

• 1. El listado en preorden es:

     • Si el árbol tiene un único elemento, dicho elemento es el listado en preorden.

     • Si el árbol tiene más de un elemento,es decir,una estructura como muestra la figura 2,el listado en preorden es listar el nodo raíz seguido del listado en preorden de cada uno de los subárboles hijos de izquierda a derecha.

  2. El listado en inorden es:

     • Si el árbol tiene un único elemento,dicho elemento es el listado en inorden.

     • Si el árbol tiene una estructura como muestra la figura 2,el listado en inorden es listar el subárbol A1 en inorden,y listar el nodo raíz seguido del listado en inorden de cada uno de los subárboles hijos de izquierda a derecha restantes.

  3. El listado en postorden es:

     • Si el árbol tiene un único elemento,dicho elemento es el listado en postorden.

     • Si el árbol tiene una estructura como muestra la figura 2,el listado en postorden es listar en postorden cada uno de los subárboles hijos de izquierda a derecha seguidos por el nodo raíz.

  4. El listado por niveles es: desde i=0 hasta la altura h del árbol,listar de izquierda a derecha los elementos de profundidad i.Como podemos observar,un nodo n1 aparece antes que n2 en el listado por niveles si la profundidad de n1 es menor que la profundidad de n2 usando el orden de los nodos definido anteriormente para el caso en que tengan la misma profundidad.

• Como ejemplo de listados veamos el resultado que se obtendría sobre el árbol A de la figura 3.

• Los resultados de los listados de preorden,postorden e inorden son los siguientes: 

• 1. Listado preorden.

  2. A=Ar=rAvAs=rvAuAwAs= rvuAwAs=rvuwAxAyAzAs= rvuwxAyAzAs=rvuwxyAzAs=rvuwxyzAs =rvuwxyzsApAq=rvuwxyzspAq=rvuwxyzspq.

  3. Listado postorden.

  4. A=Ar=AvAsr=AuAwvAsr= uAwvAsr=uAxAyAzwvAsr= uxAyAzwvAsr=uxyAzwvAsr=uxyzwvAsr= uxyzwvApAqsr=uxyzwvpAqsr=uxyzwvpqsr.

  5. Listado inorden.

  6. A=Ar=AvrAs=AuvAwrAs= uvAwrAs=uvAxwAyAzrAs=uvxw AyAzrAs=uvxwyAzrAs=uvxwyzrAs= uvxwyzrApsAq=uvxwyzrpsAq=uvxwyzrpsq.

• • Por último,el listado por niveles de este árbol es el siguiente:r,v,s,u,w,p,q,x,y,z.

  • Finalmente es interesante conocer que un árbol no puede,en general,recuperarse con uno solo de sus recorridos.Por ejemplo:Dada la lista en inorden:vwyxzrtupsq,los árboles de la figura 4 tienen ese mismo recorrido en inorden. 

2. UNA APLICACIÓN: ARBOLES DE EXPRESIÓN.

Una importante aplicación de los árboles en la informática es la representación de árboles sintácticos,es decir,árboles que contienen las derivaciones de una gramática necesarias para obtener una determinada frase de un lenguaje.

Podemos etiquetar los nodos de un árbol con operandos y operadores de manera que un árbol represente una expresión.Por ejemplo. en la figura 5 se representa un árbol con la expresión aritmética (x-y)*(z/t). 

Para que un árbol represente una expresión,hay que tener en cuenta que:

• Cualquier hoja está etiquetada con uno y sólo un operando.

• Cualquier nodo interior n está etiquetado por un operador.

En los árboles de expresión,la sucesión del preorden de etiquetas nos da lo que se conoce como la forma prefijo de una expresión, en la que el operador precede a su operando izquierdo y su operando derecho.En el ejemplo de la figura 5,el preorden de etiquetas del árbol es *-xy/zt .

Análogamente,la sucesión postorden de las etiquetas de un árbol expresión nos da lo que se conoce como la representación postfijo de una expresión.Así en el ejemplo,la expresión postfijo del árbol es xy-zt/*.

Finalmente,el inorden de una expresión en un árbol de expresión da la expresión infijo en sí misma,pero sin paréntesis.En el ejemplo,la sucesión inorden del árbol anterior es x-y*z/t. 

3. EL TIPO DE DATO ABSTRACTO "ARBOL".

La estructura de árbol puede ser tratada como un tipo de dato abstracto.A continuación presentaremos varias operaciones sobre árboles y veremos como los algoritmos de árboles pueden diseñarse en términos de estas operaciones.Al igual que con otros TDA,existe una gran variedad de operaciones que pueden llevarse a cabo sobre árboles.

Como podremos observar,cuando se construye una instancia de este tipo,tiene al menos un elemento, es decir,hasta ahora no hemos hablado de la existencia de un árbol vacío .Realmente, según la definición que vimos,efectivamente el número mínimo de nodos de un árbol es 1.En las implementaciones usaremos un valor especial ARBOL_VACIO para el caso en que el árbol no contenga nodos,al igual que en listas existe el concepto de lista vacía.

De igual forma es necesario expresar en algunos casos que un nodo no existe para lo cual también usaremos otro valor especial NODO_NULO.Un ejemplo de su uso puede ser cuando intentemos extraer el nodo hijo a la izquierda de un nodo hoja.

A continuación mostramos el conjunto de primitivas que nosotros consideraremos:

1. CREAR_RAIZ(u).Construye un nuevo nodo r con etiqueta u y sin hijos.Se devuelve el árbol con raíz r,es decir,un árbol con un único nodo.

2. DESTRUIR(T).Libera los recursos que mantienen el árbol T de forma que para volver a usarlo se debe de asignar un nuevo valor con la operación de creación.

3. PADRE(n,T).Esta función devuelve el padre del nodo n en el árbol T .Si n es la raíz ,que no tiene padre,devuelve NODO_NULO(un valor que será usado para indicar que hemos intentado salirnos del árbol).Como precondición n no es NODO_NULO (por tanto T no es vacío).

4. .

5. HIJO_IZQDA(n,T).Devuelve el descendente más a la izquierda en el siguiente nivel del nodo n en el árbol T, y devuelve NODO_NULO si n no tiene hijo a la izquierda.Como precondición n no es NODO_NULO.

6. HERMANO_DRCHA(n,T).Devuelve el descendiente a la derecha del nodo n en el árbol T ,definido para ser aquel nodo m con el mismo padre que n ,es decir, padre p,de tal manera que m cae inmediatamente a la derecha de n en la ordenación de los hijos de p (Por ejemplo,véase el árbol de la figura 6). Devuelve NODO_NULO si n no tiene hermano a la derecha.Como precondición n no es NODO_NULO. 

1. ETIQUETA(n,T).Devuelve la etiqueta del nodo n en el árbol T (manejaremos árboles etiquetados,sin embargo no es obligatorio definir etiquetas para cada árbol).Como precondición n no es NODO_NULO.

2. REETIQUETA(e,n,T).Asigna una nueva etiqueta e al nodo n en el árbol T.Como precondición n no es NODO_NULO.

3. RAIZ(T).Devuelve el nodo que está en la raíz del árbol T o NODO_NULO si T es el árbol vacío.

4. INSERTAR_HIJO_IZQDA(n,Ti,T).Inserta el árbol Ti como hijo a la izquierda del nodo n que pertenece al árbol T.Como precondición n no es NODO_NULO y Ti no es el árbol vacío.

5. INSERTAR_HERMANO_DRCHA(n,Td,T).Inserta el árbol Td como hermano a la derecha del nodo n que pertenece al árbol T.Como precondición n no es NODO_NULO y Td no es el árbol vacío.

6. PODAR_HIJO_IZQDA(n,T).Devuelve el subárbol con raíz hijo a la izquierda de n del árbol T el cual se ve privado de estos nodos.Como precondición n no es NODO_NULO.

7. PODAR_HERMANO_DRCHA(n,T).Devuelve el subárbol con raíz hermano a la derecha de n del árbol T el cual se ve privado de estos nodos.Como precondición n no es NODO_NULO.

A continuación veremos cómo implementar el TDA árbol y posteriormente implementaremos los algoritmos de recorrido:PREORDEN,POSTORDEN,INORDEN. 

 IMPLEMENTACIÓN DE LOS RECORRIDOS DE UN ÁRBOL

Recordemos que los recorridos de un árbol pueden ser de una forma directa en Preorden, Inorden y Postorden.A continuación veremos la implementación de estos tres recorridos. Así mismo,veremos un procedimiento de lectura de un árbol en preorden. 

PREORDEN

1. Visitar la raíz.

2. Recorrer el subárbol más a la izquierda en preorden.

3. Recorrer el subárbol de la derecha en preorden.

Vamos a escribir dos procedimientos uno recursivo y otro no recursivo que toman un árbol y listan las etiquetas de sus nodos en preorden.Supongamos que existen los tipos nodo y tArbol con etiquetas del tipo tEtiqueta definidos anteriormente en la implementación por punteros.El siguiente procedimiento muestra un procedimiento recursivo que , dado el nodo n,lista las etiquetas en preorden del subárbol con raíz en n. 

void PreordenArbol(nodo n,tArbol T) {   Escribir(etiquetaAr(n,T));   for(n=hizqdaAr(n,T);n!=NODO_NULO;n=herdrchaAr(n,T))     PreordenArbol(n,T); }

En esta función hemos supuesto que existe una rutina Escribir que tiene como parámetro de entrada un valor de tipo tEtiqueta que se encarga de imprimir en la salida estándar.Por ejemplo,si hemos realizado typedef int tEtiqueta la función podría ser la siguiente: 

void Escribir(tEtiqueta et) {   fprintf(stdout,"%d",(int)et); }

Por otro lado,en los programas C hemos usado el operador de desigualdad entre un dato de tipo nodo y la constante ARBOL_VACIO.Para hacerlo más independiente de la impementación sería conveniente programar una función que podríamos llamar Arbol_Vacio que se añadiría como una nueva primitiva que nos devuelve si el subárbol que cuelga del nodo es un árbol vacío.

Para el procedimiento no recursivo,usaremos una pila para encontrar el camino alrededor del árbol.El tipo PILA es realmente pila de nodos,es decir,pila de posiciones de nodos. La idea básica subyacente al algoritmo es que cuando estamos en la posición p,la pila alojará el camino desde la raíz a p,con la raíz en el fondo de la pila y el nodo p a la cabeza.El programa tiene dos modos de operar.En el primer modo desciende por el camino más a la izquierda en el árbol,escribiendo y apilando los nodos a lo largo del camino,hasta que encuentra una hoja.A continuación el programa entra en el segundo modo de operación en el cual vuelve hacia atrás por el camino apilado en la pila,extrayendo los nodos de la pila hasta que se encuentra un nodo en el camino con un hermano a la derecha.Entonces el programa vuelve al primer modo de operación,comenzando el descenso desde el inexplorado hermano de la derecha.El programa comienza en modo uno en la raíz y termina cuando la pila está vacía. 

void PreordenArbol(tArbol T) {   pila P;    /*Pila de posiciones:tElemento de la pila es el tipo nodo*/   nodo m;   P=CREAR(); /*Funcion de creacion del TDA PILA*/    m=raizAr(T);   do{     if(m!=NODO_NULO){       Escribir(etiquetaAr(n,T));       PUSH(m,P);       m=hizqdaAr(m,T);     }     else if(!VACIA(P)){       m=herdrchaAr(TOPE(P),T);       POP(P);     }   }while(!VACIA(P));    DESTRUIR(P);          /*Funcion del TDA PILA*/ }

INORDEN

1. Recorrer el subárbol más a la izquierda en inorden.

2. Visitar la raíz.

3. Recorrer el subárbol del siguiente hijo a la derecha en inorden.

Vamos a escribir un procedimiento recursivo para listar las etiquetas de sus nodos en inorden. 

void InordenArbol(nodo n,tArbol T) {   nodo c;    c=hizqdaAr(n,T);   if(c!=NODO_NULO){     InordenArbol(c,T);     Escribir(etiquetaAr(n,T));     for(c=herdrchaAr(c,T);c!=NODO_NULO;c=herdrchaAr(c,T))       InordenArbol(c,T);   }   else Escribir(etiquetaAr(n,T)); }

POSTORDEN

1. Recorrer el subárbol más a la izquierda en postorden.

2. Recorrer el subárbol de la derecha en postorden.

3. Visitar la raíz.

El procedimiento recursivo para listar las etiquetas de sus nodos en postorden es el siguiente: 

void PostordenArbol(nodo n,tArbol T) {   nodo c;    for(c=hizqdaAr(n,T);c!=NODO_NULO;c=herdrchaAr(c,T))     PostordenArbol(c,T);    Escribir(etiquetaAr(n,T)); }

LECTURA

A continuación veremos un procedimiento que nos realizará la lectura de los nodos de un árbol introduciéndolos en preorden.La función implementada se llamaLectura aunque se listan dos funciones(la rutina Lectura2 es una función auxiliar que es usada por la primera). 

void Lectura2(nodo n,tArbol T) {   tEtiqueta etHijo,etHermano;   tArbol Hijo,Hermano;    fprintf(stdout,"Introduce hijo_izqda de:  ");   Escribir(etiquetaAr(n,T));   Leer(&etHijo);    if(comparar(etHijo,FINAL)){     Hijo=creaRaiz(etHijo);     insertar_hijo_izqda(n,Hijo,T);     Lectura2(hizqdaAr(n,T),T);   }    fprintf(stdout,"Introduce her_drcha de:   ");   Escribir(etiquetaAr(n,T));   Leer(&etHermano);    if(comparar(etHermano,FINAL)){     Hermano=creaRaiz(etHermano);     insertar_hermano_drcha(n,Hermano,T);     Lectura2(herdrchaAr(n,T),T);   } }tArbol Lectura() {   tArbol T;   tEtiqueta et;    fprintf(stdout,"En caso de que no exista el hijo_izqdo o el"             "hermano_derecho introducir el valor: ");   Escribir(FINAL);           /*FINAL actua de centinela*/   fprintf(stdout,"\nIntroduce la raiz del arbol:  ");   Leer(&et);   T=creaRaiz(et);   Lectura2(raizAr(T),T); }

Es interesante observar 5 puntos en esta rutina:

• Hemos supuesto que existe una función Leer que tiene como parámetro de entrada un puntero a una zona de memoria que almacena un valor de tipo tEtiqueta,y que sirve para leer de la entrada estándar un dato de ese tipo y almacenarlo en dicha zona de memoria.

• Existe una variable FINAL que contiene un valor para la etiqueta que "no es legal" para indicar la inexistencia de un hijo a la izquierda y/o de un hermano a la derecha.

• Suponemos que existe una función comparar que tiene como parámetros de entrada dos variables de tipo tEtiqueta y que devuelve un valor entero distinto de 0 en caso de que las variables sean distintas según el criterio implementado en la función.

• Las sentencias insertar_hijo_izqda(...);Lectura2(...);no son intercambiables,es decir,si hubieramos programado esas sentencias en otro orden (Lectura2(...);insertar_hijo_izqda(...);) la función de lectura no funcionaría correctamente.La comprobación de que esta afirmación es correcta se deja como ejercicio al lector.

• En la segunda sentencia if ocurre una situación similar al punto anterior.

• Se puede completar la rutina de lectura para que prescinda de la lectura de un posible hermano a la derecha de la raíz simplemente preguntándonos si n es la raíz del árbol T.