20201204 Clase ABB con templates

#include <iostream>
using namespace std;

/**
crear la clase BinaryTree<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()  private ->preorden(raiz)
    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

**/



template <class TypeValue, class TypeKey>
class BinaryTree {
public:
    BinaryTree(){
        root=NULL;
    };

    void add(TypeValue value, TypeKey key){
        insertarABB(root, value, key);
    };

    void viewPre(){
        preorden(root);
    };

    void viewPreClass(){
        preordenClass(root);
    };

    int height(){
        return altura(root);
    }; //retorna la altura

    bool remove(TypeKey key){
        return eliminarABB(root, key);
    }; //retorna true si lo pudo eliminar

private:
    struct Nodo {
        TypeKey key; //key value
        TypeValue value;
        struct Nodo* izq;
        struct Nodo* der;
    };
    typedef Nodo* AB;

    AB root; //variable raiz

    void insertarABB(AB &t, TypeValue value, TypeKey key){
    //crear un nodo
        if(t == NULL){
            t = new Nodo();
            t->value= value;
            t->key= key;
            t->izq = NULL;
            t->der = NULL;
        } else {
            if(key < t->key)
                insertarABB(t->izq, value, key);
            else
                insertarABB(t->der, value, key);
        }
    }

    void preorden(AB t){
        if(t == NULL)
            return;

        cout << " " << t->value;
        preorden(t->izq);
        preorden(t->der);
    }

    //este método lo utilizaremos cuando trabajamos con clases
    void preordenClass(AB t){
        if(t == NULL)
            return;

        cout <<" "<<t->value.toString();
        preordenClass(t->izq);
        preordenClass(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;
    }

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

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

        if( t->key == key) {
            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->value = q->value;
            }
            //eliminar
            delete q;
            return true;
        } else {
            //recorrido
            if(key < t->key)
                return eliminarABB(t->izq, key);
            else
                return eliminarABB(t->der, key);
        }
    }
};

class Persona {
public:
    Persona(int rut=0, string nombre = ""){
        this->rut = rut;
        this->nombre = nombre;
    };

    int getRut(){
        return this->rut;
    };

    string getNombre(){
        return nombre;
    };

    //lo uso para el visualizador de preorden
    string toString(){
        return this->nombre;
    };
private:
    string nombre;
    int rut;
};

int main() {
    BinaryTree <string, int> bt;
    bt.add("uno", 1);
    bt.add("dos",2);

    bt.viewPre();
    cout<< "Altura" << bt.height()<< endl;

    bt.remove(1);
    bt.viewPre();

    /************************************/
    BinaryTree <int, string> btQuijote;
    btQuijote.add(1, "david");
    btQuijote.add(2, "Cristobal");

    /************************************/
    //con clases
    BinaryTree <Persona, int> btPersonas;
    Persona p1 = Persona(134321, "Juan");
    btPersonas.add(p1, p1.getRut());

    Persona p2 = Persona(144321, "Maria");
    btPersonas.add(p2, p2.getRut());

    btPersonas.viewPreClass();
    cout<< "Altura" << btPersonas.height()<< endl;

    btPersonas.remove(1);
    btPersonas.viewPreClass();



    return 0;
}