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:



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:


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:



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:

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.



  7. 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.

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

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

  10. 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.

  11. 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.

  12. 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.

  13. 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 ÁRBOLES.


UNA IMPLEMENTACIÓN MATRICIAL

Sea A un árbol en el cual los nodos se etiquetan 0,1,2,...,n-1,es decir,cada nodo contiene un campo de información que contendrá estos valores.La representación más simple de A que soporta la operación PADRE es una matriz lineal P en la cual el valor de P[i] es un valor o un cursor al padre del nodo i.La raíz de A puede distinguirse dándole un valor nulo o un valor a él mismo como padre.Por ejemplo.,podemos usar un esquema de cursores donde P[i]=j si el nodo j es el padre del nodo i,y P[i]=-1 (suponemos que NODO_NULO=-1) si el nodo i es la raíz.La definición del tipo sería:

#define MAXNODOS 100                     /*Por ejemplo*/
#define NODO_NULO -1

typedef int nodo;                        /*Indica una casilla de la matriz*/
typedef int *ARBOL;


Esta representación usa la propiedad de los árboles de que cada nodo tiene un único padre.Con esta representación el padre de un nodo puede encontrarse en tiempo constante.Un camino hacia arriba en el árbol puede seguirse atravesando el árbol en tiempo proporcional al número de nodos en el camino.Podemos soportar también el operador ETIQUETA añadiendo otra matriz L ,tal que L[i] es la etiqueta del nodo i ,o haciendo que los elementos de la matriz A sean registros consistiendo en un entero(cursor)y una etiqueta.EJEMPLO:Véase el árbol de la figura 7:



La representación de padre por cursores no facilita las operaciones que requieren información de hijos.Dado un nodo n ,es costoso determinar los hijos de n o la altura de n.Además,la representación por cursores del padre no especifica el orden de los hijos de un nodo.Por tanto,operaciones como HIJO_IZQDA y HERMANO_DRCHA no están bien definidas.Podríamos imponer un orden artificial,por ejemplo,numerando los hijos de cada nodo después de numerar el padre,y numerar los hijos en orden creciente de izquierda a derecha.

Nota:Téngase en cuenta que aunque esta implementación no parece muy adecuada, es posible ampliarla con la utilización de nuevos campos de cursores.Por ejemplo:Podemos añadir dos matrices adicionales para almacenar para cada nodo tanto el hijo a la izquierda como el hermano a la derecha.

IMPLEMENTACIÓN DE ÁRBOLES POR LISTAS DE HIJOS

Una forma útil e importante de representar árboles es formar para cada nodo una lista de sus hijos.Las listas pueden representarse por cualquier método,pero como el número de hijos que cada nodo puede tener puede ser variable,las representaciones por listas enlazadas son las más apropiadas.La figura 8 sugiere como puede representarse el árbol del ejemplo de la figura 7:

Hay una matriz de celdas de cabecera indexadas por nodos ,que suponemos numerados 0,1,2,...,n-1. Cada punto de cabecera apunta a una lista enlazada de elementos que son nodos.Los elementos sobre una lista encabezada por cabecera[i] son los hijos de i(por ejemplo, 9 y 4 son los hijos de 8).Si desarrollamos la estructura de datos que necesitamos en términos de un tipo de dato abstracto tLista (de nodos) y damos una implementación particular de listas,puede verse como las abstracciones encajan.

#include                       /*Definidas apropiadamente*/
#define MAXNODOS 100                     /*Por ejemplo*/
#define NODO_NULO -1

typedef int nodo;                        
typedef struct {
	tLista cabecera[MAXNODOS];
	tEtiqueta etiquetas[MAXNODOS];
	nodo raiz;
     }ARBOL;


Suponemos que la raíz de cada árbol está almacenada explícitamente en el campo raíz.El -1 en el campo raíz se usa para representar el árbol nulo o vacío.La siguiente función muestra el código para la operación HIJO_IZQDA:

nodo HIJO_IZQDA(nodo n,ARBOL T)
{
   tLista L;

   L=T.cabecera[n];
   if(PRIMERO(L)==FIN(L))
      return NODO_NULO;                 /*No tiene hijos*/
   else
      return RECUPERA(PRIMERO(L),L);    /*Recupera el primero(izqda)*/
}


Las demás operaciones son también fáciles de implementar utilizando la anterior estructura para el tipo de dato y usando las primitivas del TDA Lista.

Nota:Las funciones PRIMERO,FIN y RECUPERA usadas en el ejemplo anterior pertenecen al TDA Lista anteriormente estudiado.

IMPLEMENTACIÓN DE ÁRBOLES BASADA EN CELDAS ENLAZADAS

Al igual que ocurre en los TDA estudiados (Listas,Pilas o Colas), un nodo puede ser declarado de forma que la estructura del árbol pueda ir en aumento mediante la obtención de memoria de forma dinámica,haciendo una petición de memoria adicional cada vez que se quiere crear un nuevo nodo.

#define ARBOL_VACIO NULL
#define NODO_NULO NULL

typedef int tEtiqueta             /*Algún tipo adecuado*/
typedef struct tipocelda{
     struct tipocelda *padre,*hizqda,*herdrchaAr;
     tEtiqueta etiqueta;
    }*nodo;
typedef nodo tArbol; 


Observemos que bajo esta implementación cada nodo de un árbol contiene 3 punteros: padre que apunta al padre,hizqda que apunta al hijo izquierdo y herdrcha que apunta al hermano a la derecha del nodo.Para esta implementación de árbol vamos a presentar las funciones primitivas de las que hablábamos al principio.Suponemos que para referenciar el nodo i la variable puntero apuntará a ese nodo.Suponemos también unas variables de tipo nodo y que la variable T de tipo árbol apunta a la raíz del árbol.

nodo PadreAr(nodo n,tArbol T)
    	
    	
   
{
  return n->padre;
}

nodo HizqdaAr(nodo n,tArbol T)
    	
    	
   
{
  return n->hizqda;
}

nodo HerdrchaAr(nodo n,tArbol T)
    	
    	
   
{
  return n->herdrchaAr;
}

tEtiqueta EtiquetaAr(nodo n,tArbol T)
    	
    	
   
{
  return n->etiqueta;
}

void ReEtiquetaAr(tEtiqueta e,nodo n,tArbol T)
    	
    	
   
{
  n->etiqueta=e;
}

nodo RaizAr(tArbol T)
    	
    	
   
{
  return T;
}

tArbol Crea0(tEtiqueta et)
    	
    	
   
{
  tArbol raiz;
  
  raiz=(tArbol)malloc (sizeof(struct tipocelda));
  if (!raiz){
    error("Memoria Insuficiente.");
  }
  raiz->padre=NULL;
  raiz->hizqda=NULL;
  raiz->etiqueta=et;

  return raiz;
}

void Destruir(tArbol T)
    	
    	
   
{
  
  if(T){
     destruir(T->hizqda);
     destruir(T->herdrcha);
     free(T);
  }
}

void Insertar_hijo_izqda(nodo n,tArbol Ti,tArbol T)
    	
    	
   
{
   
  Ti->herdrcha=n->hizqda;
  Ti->padre=n;
  n->hizqda=Ti;
}

void Insertar_hermano_drcha(nodo n,tArbol Td,tArbol T)
    	
    	
   
{
   
  if(n==raizAr(T)){
    error("Memoria Insuficiente.");
  }
  Td->herdrcha=n->herdrcha;
  Td->padre=n->padre;
  n->herdrcha=Td;
}

tArbol Podar_hijo_izqda(nodo n,tArbol T)
    	
    	
   
{
  tArbol Taux;
   
  Taux=n->hizqda;
  if(Taux!=ARBOL_VACIO){
    n->hizqda=Taux->herdrcha;
    Taux->padre=NODO_NULO;
    Taux->herdrcha=NODO_NULO;
  }
  
  return Taux;
}

tArbol Podar_hermano_drcha(nodo n,tArbol T)
    	
    	
   
{
  tArbol Taux;
   
  Taux=n->herdrcha;
  if(Taux!=ARBOL_VACIO){
    n->herdrcha=Taux->herdrcha;
    Taux->padre=NODO_NULO;
    Taux->herdrcha=NODO_NULO;
  }

  return Taux;
}


Como vemos hemos implementado creaRaiz de manera que el árbol devuelto es un único nodo.Es posible construir en C un procedimiento con un número variable de parámetros:

Los podemos realizar mediante la implementación de un número de parámetros indeterminado y haciendo uso del tipo va_list que podemos encontrar en el fichero cabecera stdarg.h.El procedimiento podría ser el siguiente:

tArbol CreaRaiz(tEtiqueta et,tArbol T1,...,tArbol Tn,NULL)
    	
    	
   
{
  va_list ap;
  nodo n,aux,raiz;

  /*Reservamos memoria para el nodo raiz*/
  raiz=(nodo)malloc(sizeof(struct tipocelda));
  if(!raiz){
    error("Memoria Insuficiente.");
  }
  /*Inicializamos el nodo raiz*/
  raiz->padre=NULL;
  raiz->hizqda=NULL;
  raiz->herdrcha=NULL;
  raiz->etiqueta=et;
  /*Un bucle para insertar los subarboles*/
  va_start(ap,et);          /*Inicio de argumentos*/
  for(;;){
    n=(nodo)va_arg(ap,nodo);
    if(n==NULL)break;       /*No quedan mas hijos*/
    if(raiz->hizqda)aux->herdrcha=n;
    else raiz->hizqda=n;
    aux=n;
    aux->herdrcha=NULL;
    aux->padre=raiz;
  }
  va_end(ap);               /*Final de argumentos*/
  return(tArbol)raiz;
}


La llamada a la función tendría como parámetros una etiqueta para el nodo raíz del árbol resultante y una lista de nodos que podría ser vacía en cuyo caso el árbol que resulta tiene un único nodo:su raíz con etiqueta et. Por último,después de dicha lista,es necesario un parámetro adicional(NULL) que indica el final de la lista tras cuya lectura el procedimiento dejaría de añadir más hijos al nodo raíz que se está construyendo.

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 llama Lectura 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:





Tutor de Estructuras de Datos Interactivo
Exposito Lopez Daniel, Abraham García Soto, Martin Gomez Antonio Jose
Director de proyecto: Joaquín Fernández Valdivia
5º Licenciatura Informatica
ETSII 99/00 (Universidad de Granada).