/*
Se quieren implementar las siguientes operaciones sobre árboles generales de enteros (representados con
la semántica primer hijo, siguiente hermano) no vacíos y sin elementos repetidos:
*/

#include <iostream>
struct nodoAG {
    int dato ;
    nodoAG * pH ; //primer hijo
    nodoAG * sH ; //siguiente hermano
};
typedef nodoAG * AG ;

//(a) arbolHoja: Dado un entero x retorna un árbol que sólo contiene a x (como una hoja).
AG arbolHoja(int x){
    AG nuevo = new nodoAG;
    nuevo->dato=x;
    nuevo->pH=NULL;
    nuevo->sH=NULL;
    return nuevo;
}
//(b) esArbolHoja: Dado un árbol, retorna true si y solo si el árbol es un árbol hoja (tiene un solo elemento).
bool esArbolHoja(AG arbol){
    return (arbol!=NULL && arbol->pH==NULL && arbol->sH==NULL);
}

//(c) pertenece: Dados un árbol y un entero x, retorna true si y solo si x pertenece al árbol.
bool pertenece(AG arbol, int x){
    if (arbol==NULL){
        return false;
    }else{
        if (arbol->dato==x) {
            return true;
        }else{
            return (pertenece(arbol->pH, x) || pertenece(arbol->sH, x));
        }
    }
}

/*(d) insertar: Dados un árbol y dos enteros h y p, inserta a h como el primer hijo de p en el árbol (hijo más
a la izquierda) si p pertenece al árbol y h no pertenece al árbol. En caso contrario la operación no tiene
efecto.*/

AG buscar(AG arbol, int x){
    if (arbol==NULL){
        return NULL;
    }else{
        if (arbol->dato==x) {
            return arbol;
        }else{
            AG hijo_en_ph=buscar(arbol->pH, x);
            if (hijo_en_ph!=NULL){
                return hijo_en_ph;
            }else{
                return buscar(arbol->sH, x);
            }
        }
    }
}

void insertar(AG &arbol,int h, int p){
    AG ptr_p=buscar(arbol,p);
    if(ptr_p!=NULL && !pertenece(arbol,h)){
        AG nuevo=arbolHoja(h);
        nuevo->sH=ptr_p->pH;
        ptr_p->pH=nuevo;
    }
}

//(e) borrar: Dados un árbol y un entero x, elimina a x del árbol si es una hoja del árbol y no es la raíz
//del mismo. En caso contrario la operación no tiene efecto. Al eliminar el elemento se debe liberar la
//memoria asignada a él.

bool borrarRec(int x, AG& g) {
    bool result = false;
    if (g != NULL) {
        if (g->dato == x) {
            // Cumple con el requerimiento de no borrar si no es hoja
            if (g->pH == NULL) {
                AG aBorrar = g;
                g = g->sH;
                delete aBorrar;
                result = true; // Se encontró y se borró el elemento
            }
            else {
                result = true; // Se encontró el elemento pero no se borró porque no es hoja
            }
        }
        else {
            result = borrarRec(x, g->pH);
            if (!result) {
                result = borrarRec(x, g->sH);
            }
        }
    }
    return result;
}

void borrar(int x, AG& g) {
    if (g != NULL && g->dato != x) {
        borrarRec(x, g->pH);
    }
}



int main()
{
    AG arbol = arbolHoja(1);
    insertar(arbol, 2, 1);
    insertar(arbol, 3, 1);
    insertar(arbol, 4, 2);

    printf("El árbol es una hoja: %d\n", esArbolHoja(arbol));
    printf("El elemento 4 pertenece al árbol: %d\n", pertenece(arbol, 4)); //1 es True y 0 False

    borrar(4, arbol);

    printf("El elemento 4 pertenece al árbol después de borrar: %d\n", pertenece(arbol, 4)); //1 es True y 0 False

    return 0;
}