20201128 ABB Parte 2 (eliminación, búsqueda, altura)

#include <iostream>

using namespace std;

struct Nodo {
    int info; //key value
    struct Nodo* izq;
    struct Nodo* der;
};
typedef Nodo* AB;



//mostrando toda la izq y luego la derecha
void preorden(AB t){
    if(t == NULL)
        return;
    cout<<", "<<t->info;
    preorden(t->izq);
    preorden(t->der);
}

//cómo puedo saber la cantidad de nodos que tiene el árbol?
int contarNodos(AB t){
    if(t == NULL)
        return 0;

    return 1 + contarNodos(t->izq) + contarNodos(t->der);
}
void inordenAB(AB t){
    if(t == NULL)
            return;
    inordenAB(t->izq);
    cout<<", "<<t->info;
    inordenAB(t->der);
}

void postordenAB(AB t){
    if(t == NULL)
        return;
    postordenAB(t->izq);
    postordenAB(t->der);
    cout<<", "<<t->info;
}
//como saber la cantidad de hojas?
//hoja= sus dos hijos =  null
int contarHojas(AB t){
    if(t == NULL)
        return 0;

    if(t->izq == NULL and t->der == NULL) //punto final
        return 1;

    return contarHojas(t->izq) + contarHojas(t->der);
}

int altura(AB t){
    if(t == NULL)
        return -1; //el arbol tiene valor 0

    //recorro por la izq y por la derecha veo el al altura mayor
    int alturaizq = altura(t->izq);
    int alturader = altura(t->der);
    //cual de los dos es mayor
    if(alturaizq > alturader)
        return 1 + alturaizq;
    else
        return 1 + alturader;
}



//conocer el mayor

/**Hoy revisaremos **/
//cuenta nodos internos
//altura
//recorrido pre-in-post{Orden}
/**1) Agregue la función buscar(arbol T, int elemento) que devuelva -1 si el elemento no se encuentra en el árbol y en caso de encontrarlo indique la cantidad de saltos necesarios para encontrar el elemento.

crear la clase ArbolBinario<Type>
    add(value<Type>, key)
    bool empty()
    getKey() retorna el key de la posición actual
    getValue() retorna el value de la posición actual

    viewPre()
    viewIn()
    viewPost()
    bool exists(key)
    <Type> find(key) retorna el value

    count() retorna la cantidad de elementos
    height() retorna la altura
    leaves() retorna la cantidad de hojas
    bool remove(key) retorna true si lo pudo eliminar

**/

//Arboles binarios de búsqueda
//menores a la izquierda y mayores a la derecha
void insertarABB(AB &t, int info){
    //crear un nodo
    if(t == NULL){
        t = new Nodo();
        t->info= info;
        t->izq = NULL;
        t->der = NULL;
    } else {
        if(info < t->info)
            insertarABB(t->izq, info);
        else
            insertarABB(t->der, info);
    }
}

int buscar(AB t, int k){
    if( t == NULL)
        return -1; // si el arbol viene vacio
    if(t-> info == k){
        return t->info;
    }
    else{
        if(k < t->info)
            return buscar(t->izq, k);
        else
            return buscar(t->der, k);
    }
}

void desplazarAlMayor(AB &s, AB &p){
    if(s->der != NULL)
        return desplazarAlMayor(s->der, p);

    p = s;
    s = s->izq;
}

bool eliminarABB(AB &t, int k){
    //cuando el arbol esta vacio
    if(t == NULL)
        return false;

    if( t->info == k) {
        AB q = t;
        //si tiene un solo hijo
        if(t->der == NULL)
            t = t->izq; //salto al hijo
        else if(t->izq == NULL)
            t = t->der; //salto al hijo
        else {
            //tengo dos hijos
            //busco el mayor elemento al lado izquierdo
            desplazarAlMayor(t->izq, q);
            t->info = q->info;
        }
        //eliminar
        delete q;
        return true;
    } else {
        //recorrido
        if(k < t->info)
            eliminarABB(t->izq, k);
        else
            eliminarABB(t->der, k);
    }
    //termino de recorrer el arbol y no lo encontró
    //return false;
}

int main()
{
    AB raiz = NULL;

/*    AB uno = new Nodo();
    uno->info = 9;
    uno->izq = NULL;
    uno->der = NULL;

    AB dos = new Nodo();
    dos->info=3;
    dos->izq = NULL;
    dos->der = NULL;

    AB tres = new Nodo();
    tres->info=2;
    tres->izq = NULL;
    tres->der = NULL;

    AB cuatro = new Nodo();
    cuatro->info=10;
    cuatro->izq = NULL;
    cuatro->der = NULL;

    raiz = uno;
    uno->izq = dos;
    dos->der = tres;
    tres->izq = cuatro;

    recorrerAB(raiz);*/


    insertarABB(raiz, 10);
    insertarABB(raiz, 5);
    insertarABB(raiz, 15);
    insertarABB(raiz, 3);
    insertarABB(raiz, 7);
    insertarABB(raiz, 14);
    insertarABB(raiz, 18);
//    recorrerAB(raiz);

    AB raiz2 = NULL;
    insertarABB(raiz2, 18);
    insertarABB(raiz2, 15);
    insertarABB(raiz2, 14);
    insertarABB(raiz2, 10);
    insertarABB(raiz2, 7);
    insertarABB(raiz2, 5);
    insertarABB(raiz2, 3);
   // recorrerAB(raiz2);

    /*cout <<"cantidad de nodos:" <<contarNodos(raiz)<<endl;
    cout <<"cantidad de hojas:" <<contarHojas(raiz)<<endl;
    cout <<"Altura:" <<altura(raiz)<<endl;
    cout <<"Altura2:" <<altura(raiz2)<<endl;
    cout <<"inOrden:" <<endl;
    inordenAB(raiz2);

    */
    cout <<"\nPre:" <<endl;
    preorden(raiz);
    cout <<"\ninOrden:" <<endl;
    inordenAB(raiz);
    cout <<"\nPost:" <<endl;
    postordenAB(raiz);
    cout <<"\nbuscando el numero 15:\t"<<buscar(raiz,15);
    cout <<"\nbuscando el numero 20:\t"<<buscar(raiz,20);

    cout <<"\neliminando 15:"<<eliminarABB(raiz, 15);
    cout <<"\neliminando 20:"<<eliminarABB(raiz, 20);
    cout <<"\neliminando 3:"<<eliminarABB(raiz, 3);
    cout <<"\neliminando 15:"<<eliminarABB(raiz, 18);
    cout <<"\neliminando 20:"<<eliminarABB(raiz, 14);
    cout <<"\neliminando 3:"<<eliminarABB(raiz,7);
    cout <<"\neliminando 3:"<<eliminarABB(raiz,5);
    cout <<"\neliminando 3:"<<eliminarABB(raiz,10);

    cout <<"\nPre:" <<endl;
    preorden(raiz);
    cout << "\nHello world!" << endl;
    return 0;
}