lunes, 4 de febrero de 2013

Operaciones básicas con árboles


Operaciones básicas con árboles

^
Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles.
De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:
  • Añadir o insertar elementos.
  • Buscar o localizar elementos.
  • Borrar elementos.
  • Moverse a través del árbol.
  • Recorrer el árbol completo.
Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de recorrer árboles.

Recorridos por árboles

^
El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas.
Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.
Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.
Supongamos que tenemos un árbol de orden tres, y queremos recorrerlo por completo.
Partiremos del nodo raíz:
RecorrerArbol(raiz);

La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas:
void RecorrerArbol(Arbol a) \{
   if(a == NULL) return;
   RecorrerArbol(a->rama[0]);
   RecorrerArbol(a->rama[1]);
   RecorrerArbol(a->rama[2]);}

 Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas.


Árbol
Árbol
Los tres tipos son:

Pre-orden


En este tipo de recorrido, el valor del nodo se procesa antes de recorrer las ramas:
void PreOrden(Arbol a) \{
   if(a == NULL) return;
   Procesar(dato);
   RecorrerArbol(a->rama[0]);
   RecorrerArbol(a->rama[1]);
   RecorrerArbol(a->rama[2]);
}
Si seguimos el árbol del ejemplo en pre-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:
A B E K F C G L M D H I J N O


Post-orden

En este tipo de recorrido, el valor del nodo se procesa después de recorrer todas las ramas:
void PostOrden(Arbol a) \{
   if(a == NULL) return;
   RecorrerArbol(a->rama[0]);
   RecorrerArbol(a->rama[1]);
   RecorrerArbol(a->rama[2]);
   Procesar(dato);
}
Si seguimos el árbol del ejemplo en post-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:
K E F B L M G C H I N O J D A
 
 
 
Jose Troconis :O 





No hay comentarios:

Publicar un comentario