TAD ABB + Busquedas

/* CABECERA */

#ifndef ARBOLES_H
#define ARBOLES_H

typedef int TElementoArbol;

typedef struct nodo{
    TElementoArbol elem;
    struct nodo* hijoIzq;
    struct nodo* hijoDer;
}TNodo;

typedef struct{
    TNodo *raiz;
}TArbol;

void crearArbol(TArbol *);

int esArbolVacio(TArbol*);

void imprimirArbol(TArbol*, int);

void preOrden(TNodo*);
void inOrden(TNodo*);
void postOrden(TNodo*);

//void alturaArbol(TArbol*);
//void buscarElemento(TArbol*);
//void buscarPadreElemento(TArbol*);

void insertarElem(TArbol*,TElementoArbol);
void insertarElemUtil(TNodo**,TNodo*);

void eliminarElem(TArbol*,TElementoArbol);
void eliminarElemUtil(TNodo**,TElementoArbol);
TElementoArbol buscarMax(TNodo*);


typedef TNodo* TElemento;

/* PILA */

typedef struct nodoPila{
    TElemento elem;
    struct nodoPila* ptrSig;
}TNodoPila;

typedef struct{
    TNodoPila *cima;
}TPila;

void crearPila(TPila *);

void apilar(TPila *, TElemento);

void desapilar(TPila *);

TElemento cima(TPila *);

int esVaciaPila(TPila *);

void imprimirPila(TPila *);





/* COLA */

typedef struct nodoCola{
    TElemento elem;
    struct nodoCola* ptrSig;
}TNodoCola;

typedef struct {
    TNodoCola *primero;
    TNodoCola *ultimo;
}TCola;

void crearCola(TCola *);

void encolar(TCola *, TElemento);

void desencolar(TCola *);

TElemento primero(TCola *);

int esVaciaCola(TCola *);

void imprimirCola(TCola *);


void recorridoEnProfundidad(TArbol*);
void recorridoEnAmplitud(TArbol*);


#endif  /* ARBOLES_H */




/* IMPLEMENTACION */

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

void crearArbol(TArbol *arbol){
    arbol->raiz = NULL;
}

int esArbolVacio(TArbol*arbol){
    if (arbol->raiz == NULL)
        return 1;
    else
        return 0;
}

void imprimirArbol(TArbol*arbol,int op){
    if (op == 1)
        preOrden(arbol->raiz);
    else if (op == 2)
        inOrden(arbol->raiz);
    else if (op == 3)
        postOrden(arbol->raiz);
    printf("\n");
}

void preOrden(TNodo*raiz){
    if (raiz != NULL){
        printf("%3d",raiz->elem);
        preOrden(raiz->hijoIzq);
        preOrden(raiz->hijoDer);
    }
}

void inOrden(TNodo*raiz){
    if (raiz != NULL){
        inOrden(raiz->hijoIzq);
        printf("%3d",raiz->elem);
        inOrden(raiz->hijoDer);
    }
}

void postOrden(TNodo*raiz){
    if (raiz != NULL){
        postOrden(raiz->hijoIzq);
        postOrden(raiz->hijoDer);
        printf("%3d",raiz->elem);
    }
}

//void alturaArbol(TArbol*);
//void buscarElemento(TArbol*);
//void buscarPadreElemento(TArbol*);


void insertarElem(TArbol *arbol,TElementoArbol elem){
    TNodo *ptrNuevo;
    ptrNuevo = (TNodo*)malloc(sizeof(TNodo));

    ptrNuevo->elem = elem;
    ptrNuevo->hijoDer = NULL;
    ptrNuevo->hijoIzq = NULL;

    insertarElemUtil(&arbol->raiz,ptrNuevo);
}

void insertarElemUtil(TNodo **raiz,TNodo *nuevoNodo){
    if (*raiz == NULL)
        *raiz = nuevoNodo;
    else if (nuevoNodo->elem > (*raiz)->elem)
        insertarElemUtil(&(*raiz)->hijoDer,nuevoNodo);
    else if (nuevoNodo->elem < (*raiz)-> elem)
        insertarElemUtil(&(*raiz)->hijoIzq,nuevoNodo);
}


void eliminarElem(TArbol*arbol,TElementoArbol elem){
    if (arbol->raiz == NULL)
        printf("No se puede eliminar de un arbol vacio\n");
    else
        eliminarElemUtil(&arbol->raiz,elem);
}

void eliminarElemUtil(TNodo **raiz, TElementoArbol elem){
    if (elem == (*raiz)->elem){
        if((*raiz)->hijoDer == NULL && (*raiz)->hijoIzq == NULL)
            (*raiz) = NULL;
        else if ((*raiz)->hijoDer != NULL && (*raiz)->hijoIzq != NULL){
            TElementoArbol elemMax;
            elemMax = buscarMax((*raiz));
            eliminarElemUtil(&(*raiz),elemMax);
            (*raiz)->elem = elemMax;
        }
        else{
            TNodo *ptrEliminar;
            if ((*raiz)->hijoIzq != NULL){
                ptrEliminar = (*raiz)->hijoIzq;
                (*raiz)->elem = (*raiz)->hijoIzq->elem;
                free(ptrEliminar);
            }
            else{
                ptrEliminar = (*raiz)->hijoDer;
                (*raiz)->elem = (*raiz)->hijoDer->elem;
                free(ptrEliminar);
            }
        }
    }
    else if (elem > (*raiz)->elem)
        eliminarElemUtil(&(*raiz)->hijoDer,elem);
    else if (elem < (*raiz)->elem)
        eliminarElemUtil(&(*raiz)->hijoIzq,elem);
    else if (*raiz == NULL)
        printf("No se encuentra el elemento");
}

TElementoArbol buscarMax(TNodo *raiz){
    TNodo *ptrRec;
    ptrRec = raiz->hijoIzq;
    while (ptrRec->hijoDer != NULL)
        ptrRec = ptrRec->hijoDer;
    return ptrRec->elem;
}


void recorridoEnProfundidad(TArbol*arbol){
    TPila pila;
    crearPila(&pila);
    TNodo* ptrArbol;
    ptrArbol = arbol->raiz;

    apilar(&pila,ptrArbol);
    while(!esVaciaPila(&pila)){
        TNodo * auxArbol;
        auxArbol = cima(&pila);
        printf("%3d",auxArbol->elem);
        desapilar(&pila);
        if (auxArbol->hijoDer != NULL)
            apilar(&pila,auxArbol->hijoDer);
        if (auxArbol->hijoIzq != NULL)
            apilar(&pila,auxArbol->hijoIzq);
    }
    printf("\n");
}

void recorridoEnAmplitud(TArbol*arbol){
    TCola cola;
    crearCola(&cola);
    TNodo* ptrArbol;
    ptrArbol = arbol->raiz;

    encolar(&cola,ptrArbol);
    while(!esVaciaCola(&cola)){
        TNodo *auxArbol;
        auxArbol = primero(&cola);
        printf("%3d",auxArbol->elem);
        desencolar(&cola);
        if (auxArbol->hijoIzq != NULL)
            encolar(&cola,auxArbol->hijoIzq);
        if (auxArbol->hijoDer != NULL)
            encolar(&cola,auxArbol->hijoDer);
    }
    printf("\n");
}



/* PILA */

void crearPila(TPila *pila){
    pila->cima = NULL;
}

void apilar(TPila *pila, TElemento elem){
    TNodoPila *ptrNuevo;
    ptrNuevo = (TNodoPila*)malloc(sizeof(TNodoPila));

    ptrNuevo->elem = elem;
    ptrNuevo->ptrSig = NULL;

    if (pila->cima == NULL){
        pila->cima = ptrNuevo;
    }else{
        ptrNuevo->ptrSig = pila->cima;
        pila->cima = ptrNuevo;
    }
}

void desapilar(TPila *pila){
    if (pila->cima != NULL){
        TNodoPila *ptrEliminar;
        ptrEliminar = pila->cima;
        pila->cima = pila->cima->ptrSig;
        free(ptrEliminar);
    }else{
        printf("No se puede desapilar de una pila vacia\n");
    }
}

TElemento cima(TPila *pila){
    if (pila->cima != NULL){
        return(pila->cima->elem);
    }else{
        printf("No hay cima en una pila vacia\n");
    }
}

int esVaciaPila(TPila *pila){
    return (pila->cima == NULL);
}

void imprimirPila(TPila *pila){
    TNodoPila *ptrRec;
    ptrRec = pila->cima;

    while (ptrRec != NULL){
        printf(" %d ",ptrRec->elem);
        ptrRec = ptrRec->ptrSig;
    }
    printf("NULL\n");
}




/* COLA */

void crearCola(TCola *cola){
    cola->primero = NULL;
    cola->ultimo = NULL;
}

void encolar(TCola *cola, TElemento elem){
    TNodoCola *ptrNuevo;

    ptrNuevo = (TNodoCola *)malloc(sizeof(TNodoCola));
    ptrNuevo->elem = elem;
    ptrNuevo->ptrSig = NULL;

    if (cola->primero == NULL){
        cola->primero = ptrNuevo;
        cola->ultimo = ptrNuevo;
    }else{
        cola->ultimo->ptrSig = ptrNuevo;
        cola->ultimo = ptrNuevo;
    }

}

void desencolar(TCola *cola){
    if (cola->primero != NULL){
        TNodoCola *ptrEliminar;
        ptrEliminar = cola->primero;
        cola->primero = cola->primero->ptrSig;
        free(ptrEliminar);
    }else{
        printf("No se puede desencolar en una cola vacia\n");
    }
}

TElemento primero(TCola *cola){
    if (cola->primero != NULL){
        return (cola->primero->elem);
    }else{
        printf("No hay primera en una cola vacia\n");
    }
}

int esVaciaCola(TCola *cola){
    return (cola->primero == NULL);
}


void imprimirCola(TCola *cola){
    TNodoCola *ptrRec;
    ptrRec = cola->primero;

    while (ptrRec != NULL){
        printf(" %d ",ptrRec->elem);
        ptrRec = ptrRec->ptrSig;
    }
    printf("NULL\n");
}




/* MAIN */

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

int main(int argc, char** argv) {
    TArbol arbol;

    crearArbol(&arbol);

    insertarElem(&arbol,20);
    insertarElem(&arbol,10);
    insertarElem(&arbol,5);
    insertarElem(&arbol,30);
    insertarElem(&arbol,40);
    insertarElem(&arbol,50);
    insertarElem(&arbol,12);
    insertarElem(&arbol,38);

    imprimirArbol(&arbol,1);

    eliminarElem(&arbol,5);
    imprimirArbol(&arbol,1);


    recorridoEnProfundidad(&arbol);
    recorridoEnAmplitud(&arbol);

    return (EXIT_SUCCESS);
}