20201124 Árboles Binarios Parte 1

#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 recorrerAB(AB t){
    if(t == NULL)
        return;
    cout <<"info:" << t->info<<endl;
    recorrerAB(t->izq);
    recorrerAB(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);
}

//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);
}


//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){
        AB nuevo = new Nodo();
        nuevo->info = info;
        nuevo->izq = NULL;
        nuevo->der = NULL;
        t = nuevo;
    } else {
        if(info < t->info)
            insertarABB(t->izq, info);
        else
            insertarABB(t->der, info);
    }
}

//conocer el mayor



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);

    cout <<"cantidad de nodos:" <<contarNodos(raiz)<<endl;
    cout <<"cantidad de hojas:" <<contarHojas(raiz)<<endl;

    cout << "Hello world!" << endl;
    return 0;
}