UNIT uArbol;


INTERFACE
USES uElem;

TYPE
    TArbol = ^TNodo;

    TNodo = RECORD
        izq:TArbol;
        rai:TElem;
        der:TArbol;
    END;

    PROCEDURE CrearArbolVacio(VAR arbol:TArbol);

    FUNCTION EsArbolVacio(arbol:TArbol):boolean;

    PROCEDURE ConstruirArbol (VAR arbol:TArbol; i:TArbol; r:TElem; d:TArbol);

    FUNCTION Altura(arbol:TArbol):integer;

    FUNCTION NumNodos(arbol:TArbol):integer;

    FUNCTION NumHojas(arbol:TArbol):integer;

    FUNCTION Equilibrado(arbol:TArbol):boolean;

    PROCEDURE HijoDer(arbol:TArbol; VAR d:TArbol);

    PROCEDURE HijoIzq(arbol:TArbol; VAR i:TArbol);

    PROCEDURE Raiz(arbol:TArbol; VAR r:TElem);

    PROCEDURE Inorden(arbol:TArbol);

    PROCEDURE Postorden(arbol:TArbol);

    PROCEDURE Preorden(arbol:TArbol);

{A partir de aquí, instrucciones de árbol binario de búsqueda}

    PROCEDURE InsertarOrdenado (VAR arbol:TArbol; elem:TElem);

    PROCEDURE Mayor (arbol:TArbol; VAR m:TElem);

    PROCEDURE Menor (arbol:TArbol; VAR men:TElem);

    FUNCTION Pertenece (arbol:TArbol; elem:TElem):boolean;

    PROCEDURE Eliminar (VAR arbol:TArbol; elem:TElem);

IMPLEMENTATION

    PROCEDURE CrearArbolVacio(VAR arbol:TArbol);
        BEGIN
            arbol := NIL;
        END;{CrearArbolVacio}

    FUNCTION EsArbolVacio(arbol:TArbol):boolean;
        BEGIN
            EsArbolVacio := (arbol = NIL);
        END;{EsArbolVacio}

    PROCEDURE ConstruirArbol (VAR arbol:TArbol; i:TArbol; r:TElem; d:TArbol);
        BEGIN
            new(arbol);
            Asignar( arbol^.rai , r);
            arbol^.izq := i;
            arbol^.der := d;
        END;{ConstruirArbol}

    FUNCTION Altura(arbol:TArbol):integer;
        FUNCTION Maximo (a,b:integer):integer;
            BEGIN
                IF a>b THEN
                    Maximo := a
                ELSE
                    Maximo := b;
            END;{Maximo}

        BEGIN
            IF EsArbolVacio(arbol) THEN
                Altura := 0
            ELSE
                BEGIN
                    Altura := 1 + Maximo( Altura(arbol^.izq) , Altura(arbol^.der) );
                END;{ELSE}

        END;{Altura}

    FUNCTION NumNodos(arbol:TArbol):integer;
        BEGIN
            IF EsArbolVacio(arbol) THEN
                NumNodos := 0
            ELSE
                BEGIN
                    NumNodos := 1 + NumNodos(arbol^.izq) + NumNodos(arbol^.der);
                END;{ELSE}
        END;{NumNodos}

    FUNCTION NumHojas(arbol:TArbol):integer;
        BEGIN
            IF ( EsArbolVacio(arbol^.izq) ) AND ( EsArbolVacio(arbol^.der) ) THEN
                NumHojas := 1
            ELSE
                NumHojas := NumHojas(arbol^.izq) + NumHojas(arbol^.der);
        END;{NumHijos}

    FUNCTION Equilibrado(arbol:TArbol):boolean;
        BEGIN
            IF EsArbolVacio(arbol) THEN
                Equilibrado := TRUE
            ELSE
                Equilibrado := ( NumNodos(arbol^.izq) = NumNodos(arbol^.der) );

        END;{Equilibrado}

    PROCEDURE HijoDer(arbol:TArbol; VAR d:TArbol);
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                d := arbol^.der;
        END;{HijoDer}

    PROCEDURE HijoIzq(arbol:TArbol; VAR i:TArbol);
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                i := arbol^.izq;
        END;{HijoIzq}

    PROCEDURE Raiz(arbol:TArbol; VAR r:TElem);
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                Asignar(r , arbol^.rai);
        END;{Raiz}

    PROCEDURE Inorden(arbol:TArbol);
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                BEGIN
                    Inorden(arbol^.izq);
                    Mostrar(arbol^.rai);
                    Inorden(arbol^.der);
                END;{IF}
        END;{Inorden}

    PROCEDURE Postorden(arbol:TArbol);
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                BEGIN
                    Postorden(arbol^.izq);
                    Postorden(arbol^.der);
                    Mostrar(arbol^.rai);
                END;{IF}
        END;{Postorden}

    PROCEDURE Preorden(arbol:TArbol);
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                BEGIN
                    Mostrar(arbol^.rai);
                    Preorden(arbol^.izq);
                    Preorden(arbol^.der);
                END;{IF}
        END;{Postorden}

{A partir de aquí, instrucciones de árbol binario de búsqueda}

    PROCEDURE InsertarOrdenado (VAR arbol:TArbol; elem:TElem);
        VAR
            i,d:TArbol;
        BEGIN
            CrearArbolVacio(i);
            CrearArbolVacio(d);
            IF EsArbolVacio(arbol) THEN
                BEGIN
                    ConstruirArbol(arbol , i , elem , d);
                END{IF}
            ELSE
                IF EsMayor( elem , arbol^.rai ) THEN
                    InsertarOrdenado(arbol^.der , elem)
                ELSE
                    IF EsMayor( arbol^.rai , elem) THEN
                        InsertarOrdenado(arbol^.izq , elem);
        END;{InsertarOrdenado}

    PROCEDURE Mayor (arbol:TArbol; VAR m:TElem);
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                IF arbol^.der = NIL THEN
                    m := arbol^.rai
                ELSE
                    Mayor(arbol^.der , m);

        END;{Mayor}

    PROCEDURE Menor (arbol:TArbol; VAR men:TElem);
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                IF arbol^.izq = NIL THEN
                    men := arbol^.rai
                ELSE
                    Menor(arbol^.izq , men);

        END;{Mayor}

    FUNCTION Pertenece (arbol:TArbol; elem:TElem):boolean;
        BEGIN
            IF EsArbolVacio(arbol) THEN
                Pertenece := FALSE
            ELSE
                IF EsMayor(elem , arbol^.rai) THEN
                    Pertenece(arbol^.der , elem)
                ELSE
                    IF EsMayor( arbol^.rai , elem) THEN
                        Pertenece(arbol^.izq , elem)
                    ELSE
                        Pertenece := TRUE;
        END;{Pertenece}

    PROCEDURE Eliminar (VAR arbol:TArbol; elem:TElem);
        VAR
            aux:TArbol;
            min:TElem;
        BEGIN
            IF NOT(EsArbolVacio(arbol)) THEN
                BEGIN
                    IF Iguales(arbol^.rai , elem) THEN
                        IF EsArbolVacio(arbol^.der) THEN
                            BEGIN
                                aux := arbol;
                                arbol := arbol^.izq;
                                dispose(aux);
                            END{IF}
                        ELSE
                            IF EsArbolVacio(arbol^.izq) THEN
                                BEGIN
                                    aux := arbol;
                                    arbol := arbol^.der;
                                    dispose(aux);
                                END{IF}
                            ELSE
                                BEGIN
                                    Menor(arbol^.der , min);
                                    Asignar(arbol^.rai , min);
                                    Eliminar(arbol^.der , min);
                                END{ELSE}
                    ELSE
                        IF EsMayor( elem , arbol^.rai) THEN
                            Eliminar(arbol^.der , elem)
                        ELSE
                            Eliminar(arbol^.izq , elem);
                END; {IF}
        END; {Eliminar}

END.