ARBOLES

Un árbol es una estructura de datos, que puede definirse de forma recursiva como:

• Una estructura vacía.
• Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.

Es, por tanto, una estructura no secuencial. 

Otra definición nos da el árbol como un tipo de grafo un árbol es un grafo acíclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en esta sección no se tratará esta implementación.

"Formas de representación"

Mediante un grafo:

- Mediante un diagrama encolumnado:

a
  b
    d
  c
    e
    f

"Nomenclatura sobre árboles"

• Raíz: es aquel elemento que no tiene antecesor.
• Rama: arista entre dos nodos.
• Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.
• Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.
• Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.
• Hoja: nodo que no tiene descendientes: grado 0.
• Nodo interno: aquel que tiene al menos un descendiente.
• Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.
• Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.
• Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.

Aclaraciones: se ha denominado a a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que b fuera la raíz, y a y d los sucesores inmediatos de la raíz b. Sin embargo, en las implementaciones sobre un computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz.

"Declaración de árbol binario"

Se definirá el árbol con una clave de tipo entero (puede ser cualquier otra tipo de datos) y dos hijos: izquierdo (izq) y derecho (der). Para representar los enlaces con los hijos se utilizan punteros. El árbol vacío se representará con un puntero nulo.

Un árbol binario puede declararse de la siguiente manera:

typedef struct tarbol 
{ 
   int clave; 
   struct tarbol *izq,*der; 
} tarbol;

"Recorridos sobre árboles binarios"

- Recorridos en profundidad:

* Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la clave      del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza.

Si se hace el recorrido en preorden del árbol de la figura 1 las visitas serían en el orden siguiente: a,b,d,c,e,f.

void preorden (tarbol*a)

{

   if (a !=NULL) {

       visitar (a);

       preorden (a->izq);

       preorden (a->der);

   }

}

* Recorrido en inorden u orden central: se visita el subárbol izquierdo, el nodo actual, y después se visita el subárbol derecho. En el ejemplo de la figura 1 las visitas serían en este orden: b,d,a,e,c,f.

void inorden(tarbol *a)

 {

    if (a != NULL) {

        inorden(a->izq);

        visitar(a);

        inorden(a->der);

   }

}

* Recorrido en postorden: se visitan primero el subárbol izquierdo, después el subárbol derecho, y por último el nodo actual. En el ejemplo de la figura 1 el recorrido quedaría así: d,b,e,f,c,a.

void postorden(arbol *a)

{

   if (a != NULL) {

      postorden(a->izq);

      postorden(a->der);

      visitar(a);

   }

} 

La ventaja del recorrido en postorden es que permite borrar el árbol de forma consistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este recorrido se borrará el árbol o subárbol que se pasa como parámetro. La razón para hacer esto es que no se debe borrar un nodo y después sus subárboles, porque al borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla de manipular una estructura de datos inexistente. Una alternativa es utilizar una variable auxiliar, pero es innecesario aplicando este recorrido.

- Recorrido en amplitud:

Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1 (como mucho hay uno, la raíz), después los nodos de nivel 2, así hasta que ya no queden más.
Si se hace el recorrido en amplitud del árbol de la figura una visitaría los nodos en este orden: a,b,c,d,e,f
En este caso el recorrido no se realizará de forma recursiva sino iterativa, utilizando una cola como estructura de datos auxiliar. El procedimiento consiste en encolar (si no están vacíos) los subárboles izquierdo y derecho del nodo extraido de la cola, y seguir desencolando y encolando hasta que la cola esté vacía.
En la codificación que viene a continuación no se implementan las operaciones sobre colas.

void amplitud(tarbol *a)

{

  tCola cola;   /* las claves de la cola serán de tipo árbol binario */

  arbol *aux;

 

  if (a != NULL) {

    CrearCola(cola);

    encolar(cola, a);

    while (!colavacia(cola)) {

      desencolar(cola, aux);

      visitar(aux);

      if (aux->izq != NULL) encolar(cola, aux->izq);

      if (aux->der != NULL) encolar(cola, aux->der);

    }

  }

}

Construcción de un árbol binario

Hasta el momento se ha visto la declaración y recorrido de un árbol binario. Sin embargo no se ha estudiado ningún método para crearlos. A continuación se estudia un método para crear un árbol binario que no tenga claves repetidas partiendo de su recorrido en preorden e inorden, almacenados en sendos arrays.

Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es sencillo cuando uno es capaz de construir el árbol viendo sus recorridos pero sin haber visto el árbol terminado.

Partiendo de los recorridos preorden e inorden del árbol de la figura 1 puede determinarse que la raíz es el primer elemento del recorrido en preorden. Ese elemento se busca en el array inorden. Los elementos en el array inorden entre izq y la raíz forman el subárbol izquierdo. Asimismo los elementos entre der y la raíz forman el subárbol derecho. Por tanto se tiene este árbol:

A continuación comienza un proceso recursivo. Se procede a crear el subárbol izquierdo, cuyo tamaño está limitado por los índices izq y der. La siguiente posición en el recorrido en preorden es la raíz de este subárbol. Queda esto:

El subárbol b tiene un subárbol derecho, que no tiene ningún descendiente, tal y como indican los índices izq y der. Se ha obtenido el subárbol izquierdo completo de la raíz a, puesto que b no tiene subárbol izquierdo:

Después seguirá construyéndose el subárbol derecho a partir de la raíz a.

-Bibliografia
http://www.algoritmia.net/articles.php?id=17