De aquí en adelante , las implementaciones de recorrido serán usando una Cola , ya que los problemas que vienen, requieren los datos en forma ordenada.

Definición de Recorridos

Ejemplo

Recorridos inorden : 10 , 30 , 50 , 55 , 60 , 80 preorden : 60 , 30 , 10 , 50 , 55 , 80 postorden : 10 , 55 , 50 , 30 , 80 , 60

Implementación del recorrido inorden

Se declara una función que recibe como parámetros un arbol binario y una cola.

Las instrucciones de la función, siguen el concepto recursivo de la definición, teniendo en cuenta que el concepto de "visitar el elemento de la raiz" se reemplaza por : obtener la raíz e insertar el elemento en la cola y que la condición de la recursividad es que se encuentre con algún subárbol vacío.

*nota : Hay que tener cuidado en verificar que la cola que se pasa como parámetro sea no vacía. Las funciones serán implementadas en el archivo "funcArbin.h".

void inordenArbin(Arbin a,Cola col)
{
    if (!vacioArbin(a))
    {
        inordenArbin(izqArbin(a),col);
        TipoA raiz = raizArbin(a);
        adicCola(col,raiz);
        inordenArbin(derArbin(a),col);
    }
}

Las otras dos funciones que implementan los recorridos de preorden y postorden son similares, por lo que se omite mayor explicación.

Liberar memoria

Si se quiere eliminar todos los nodos del árbol, se puede plantear la idea que mediante un recorrido recursivo, en vez de almacenar la información en la cola , se libere memoria.
Para no provocar errores, se ve que el recorrido en postorden nos da una buena idea para ir eliminando los nodos.

Es importante que si se quiere insertar luego de haber llamado a ésta función, se debe asignar a la variable, el valor retornado por la función arbinVacio().

Ejemplo :
     
     Arbin a = arbinVacio();
     Cola c = inicCola();
     
     a = insertarArbin(a,4,mayor);
     :
     a = insertarArbin(a,23,mayor);
     
     inordenArbin(a,c);
     
     imprimir_cola(c);
     
     destruirArbin(a);
     
     a = arbinVacio();
     
     a = insertar(a,10,mayor);
     :

void destruirArbin(Arbin a)
{
    if(!vacioArbin(a))
    {
        destruirArbin(a->izq);
        destruirArbin(a->der);
        free(a);
    }
}

*nota : esta función está incluida en el archivo funcArbin.h

Programa de prueba para el recorrido inorden

El programa consiste en formar un árbol binario igual al del ejemplo (ver figura) , para luego hacer un recorrido inorden y mostrar los números que se encuentran ordenados en la cola.

*nota : como la cola se vacía mientras se recorren los datos para imprimirlos, sólo basta con liberar memoria para el árbol binario.

#include<stdio.h>
#include<stdlib.h>

/* declaración de tipos */

typedef int TipoC;
typedef int TipoA;

/* archivos necesarios */

#include "tadCola.h"
#include "tadArbin.h"
#include "funcArbin.h"

/* función específica de comparación que
será pasada como parámetro a la función
insertarArbin */

int mayor(int a , int b)
{
    return a > b;
}
 
int main()
{

    Arbin a = arbinVacio();
    Cola c = inicCola();

    int arr[] = { 60, 30 , 80, 10 , 50 , 55 };

    /* Se insertan los datos en el árbol*/

    for(int i = 0; i < 6; i++)
    {
        a = insertarArbin(a,arr[i],mayor);
    }

    /* Recorrido en inorden .. los datos
       se almacenan en la cola */ 

    inordenArbin(a,c);

    int aux;

    /* se imprimen los elementos de la cola */

    while(!vaciaCola(c))
    {
        aux = infoCola(c);    
        printf("\t%d",aux);
        elimCola(c);
    }

    /* Se destruye el árbol */

    destruirArbin(a);

    return 0;
}

Implementación de funciones

/*  funcArbin.h  */

void inordenArbin(Arbin a,Cola col)
{
    if (!vacioArbin(a))
    {
        inordenArbin(izqArbin(a),col);
        TipoA raiz = raizArbin(a);
        adicCola(col,raiz);
        inordenArbin(derArbin(a),col);
    }
}

void preordenArbin(Arbin a,Cola col)
{
    if(!vacioArbin(a))
    {
        TipoA raiz = raizArbin(a);
        adicCola(col,raiz);
        preordenArbin(izqArbin(a),col);
        preordenArbin(derArbin(a),col);
    }
}

void postordenArbin(Arbin a,Cola col)
{
    if(!vacioArbin(a))
    {
        postordenArbin(izqArbin(a),col);
        postordenArbin(derArbin(a),col);
        TipoA raiz = raizArbin(a);
        adicCola(col,raiz);
    }
}

void destruirArbin(Arbin a)
{
    if(!vacioArbin(a))
    {
        destruirArbin(a->izq);
        destruirArbin(a->der);
        free(a);
    }
}