Operaciones sobre ABB

#ifndef ABB_H_INCLUDED
#define ABB_H_INCLUDED

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

/* 1. DEFINIMOS EL NODO ABB */
struct Nodo
{
    int _valor;
    struct Nodo* _izquierdo;
    struct Nodo* _derecho;
}typedef Nodo;

/* 2. CREAMOS UN NODO */
Nodo* crearNodo( int _valor )
{
    // asigno una direccion de memoria al puntero
    Nodo* _ptr = ( Nodo* )malloc( sizeof ( Nodo ) );

    // modifico los valores del puntero
    _ptr->_valor = _valor;
    _ptr->_izquierdo = NULL;
    _ptr->_derecho   = NULL;

    return _ptr;
};

/* 3. INSERTAMOS UN NODO */
void insertar( Nodo** _raiz, int _valor )
{
    if( !(*_raiz) )
    {
        *_raiz = crearNodo( _valor );
    }
    else if( _valor < (*_raiz)->_valor )
    {
        insertar( &(*_raiz)->_izquierdo, _valor );
    }
    else
    {
        insertar( &(*_raiz)->_derecho, _valor );
    }
};

/* 4. RECORRIDO PREORDEN DEL ABB */
void preOrden( const Nodo* _raiz )
{
    if( _raiz != NULL )
    {
        printf(" %d ", _raiz->_valor );
        preOrden( _raiz->_izquierdo );
        preOrden( _raiz->_derecho );
    }
}

/* 5. RECORRIDO POSORDEN */
void postOrden( const Nodo* _raiz )
{
    if( _raiz != NULL )
    {
        postOrden( _raiz->_izquierdo );
        postOrden( _raiz->_derecho );
        printf(" %d ", _raiz->_valor );
    }
}

/* 6. RECORRIDO INORDEN */
void inOrden( Nodo* _raiz )
{
    if( _raiz != NULL )
    {
        inOrden( _raiz->_izquierdo );
        printf( " %d ", _raiz ->_valor );
        inOrden( _raiz->_derecho );
    }
};

/* 7. ELIMINAR UN NODO */
void eliminar( Nodo** _raiz, int _target )
{
    /* SI EL ARBOL NO ESTA VACIO */
    if( *_raiz != NULL )
    {
        if( _target < (*_raiz)->_valor )
        {
            eliminar( &(*_raiz)->_izquierdo, _target );
        }
        else if( _target > (*_raiz)->_valor )
        {
            eliminar( &(*_raiz)->_derecho, _target );
        }
        // encontre el objetivo
        else
        {
            Nodo* objetivo = *_raiz;

            if( objetivo->_izquierdo == NULL )
            {
                *_raiz = objetivo->_derecho;
            }
            else if( objetivo->_derecho == NULL )
            {
                *_raiz = objetivo->_izquierdo;
            }
            else
            {
                /* SI ESTAMOS ACA ES PORQUE TIENE HIJO HIZQUIERDO Y DERECHO*/
                /* SE REEMPLAZA POR EL MAYOR DE LOS MENORES */
                Nodo* sucesor      = objetivo->_izquierdo;
                Nodo* padreSucesor = NULL;

                // busco al mayor de los menores y lo almaceno en el puntero aux
                while( sucesor->_derecho != NULL)
                {
                    padreSucesor = sucesor;
                    sucesor = sucesor->_derecho;
                }

                // intercambia el valor de los nodos objetivo y el nodo sucesor
                objetivo->_valor = sucesor->_valor;

                // reacomoda los nodos para que quede balanceado el arbol
                if( padreSucesor == objetivo )
                {
                    padreSucesor->_izquierdo = sucesor->_izquierdo;
                }
                else
                {
                    padreSucesor->_derecho = sucesor->_izquierdo;
                }

                // una vez reacomodado el arbol elimino la direccion de memoria del sucesor...
                objetivo = sucesor;
            }

            free( objetivo );
        }
    }
};

/* 8. BUSCAR UN NODO */
Nodo* buscar( Nodo* _raiz, int _target )
{
    if( _raiz == NULL )
    {
        return 0;
    }
    else if( _raiz->_valor == _target )
    {
        return _raiz;
    }
    else if( _target < _raiz->_valor )
    {
        buscar( _raiz->_izquierdo, _target);
    }
    else
    {
        buscar( _raiz->_derecho, _target);
    }
};

/* 9. CONTAR LAS HOJAS DEL ARBOL */
int contarHojas( const Nodo* _raiz, int* nh )
{
    if( _raiz != NULL )
    {
        contarHojas( _raiz->_izquierdo, nh );
        contarHojas( _raiz->_derecho, nh );

        if( _raiz->_izquierdo == NULL && _raiz->_derecho == NULL )
        {
            (*nh)++;
        }
    }
};

/* 10. ELIMINAR EL ARBOL */
void eliminarArbol( Nodo** _raiz )
{
    if( *_raiz != NULL )
    {
        eliminarArbol( (*_raiz)->_izquierdo );
        eliminarArbol( (*_raiz)->_derecho );

        free( *_raiz );
    }
};


#endif // ABB_H_INCLUDED