Árbol De Búsqueda Binaria

ABB Completo.cpp

//Practica De Arboles ABB
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <windows.h>
using namespace std;

struct Nodo
{
    int dato;
    Nodo *izq = NULL;
    Nodo *der = NULL;
    Nodo *gfe; //Puntero para saber quien es el padre de el nodo
};

typedef struct Nodo *ABB;

int auxX = 0;
COORD coord={0,0};

void gotoxy(int,int); //Funcion para posicionar el cursor
void Recorridos(void);  //Menu
void Limpiar(void); //Funciones pause y cls
ABB CrearNodo(int x,ABB); //Crear Nodo
void Insertar(ABB &,int,ABB); //Insertar un nodo ya sea en la der o la izq
int Buscar(ABB,int); //Regresa un puntero para saber si se encuentra o no
void ArbolCompleto(ABB,int); //Muestra el arbol en posicion vertical
void PreIn(ABB); //Preorden Inverso
void InIn(ABB); //InOrden Inverso
void PostIn(ABB); //PostOrden Inverso
void PreOn(ABB); //PreOrden Converso
void InOn(ABB); //InOrden Converso
void PostOn(ABB); //PostOrden Converso
void MostrarArbol(ABB,int); //Muestra el arbol en posicion vertical
void Eliminar(ABB,int); //Elimina un nodo hoja
void EliminarNodo(ABB); //Selecciona el caso de eliminacion
ABB Minimo(ABB); //Selecciona el dato menor del lado izq
ABB Maximo(ABB); //Selecciona el dato mayor del lado der
void Reemplazar(ABB,ABB); //Intercambia el nodo por el nodo hoja
void DestruirNodo(ABB); //Elimina el nodo seleccionado
void Niveles(ABB,int); //Impresion por niveles

int main()
{
    ABB arbol = NULL;
    int opc1;
    int opc2;
    int cont = 0;
    int bus;
    char res;
    int n;
    while(1)
    {
        cout << "A R B O L  D E  B U S Q U E D A  B I N A R I A" << endl
             << "\n1) Insertar" << endl
             << "2) Eliminar" << endl
             << "3) Recorridos" << endl
             << "4) Buscar" << endl
             << "5) Salir" << endl
             << "Seleccione Opcion: ";
        do
        {
            cin >> opc1;
        }while(opc1 < 1 && opc1 > 6);

        switch(opc1)
        {
        case 1:
            cout << "\nDato a Insertar: ";
                cin >> n;
            Insertar(arbol,n,NULL);
            Limpiar();
        break;

        case 2:
            cout << "Soy Eliminar" << endl;
            cout << "Numero a Eliminar: ";
                cin >> bus;
            Eliminar(arbol,bus);
            Limpiar();
        break;

        case 3:
            cout << "Yo soy los recorridos" << endl;
            Recorridos();
            do
            {
                cin >> opc2;
            }while(opc2 < 1 && opc2 > 8);

            switch(opc2)
            {
            case 1:
                cout << "PreOrden Inverso" << endl;
                PreIn(arbol);
            break;

            case 2:
                cout << "InOrden Inverso" << endl;
                InIn(arbol);
            break;

            case 3:
                cout << "PostOrden Inverso" << endl;
                PostIn(arbol);
            break;

            case 4:
                cout << "PreOrden Converso" << endl;
                PreOn(arbol);
            break;

            case 5:
                cout << "InOrden Converso" << endl;
                InOn(arbol);
            break;

            case 6:
                cout << "PostOrden Converso" << endl;
                PostOn(arbol);
            break;

            case 7:
                cout << "Niveles" << endl;
                for(int i = 0 ; i < 10 ; i++)
                    Niveles(arbol,i);
            break;

            case 8:
                system("cls");
                cout << "Arbol Completo" << endl;
                //ArbolCompleto(arbol,cont);
                 auxX = 0;
                MostrarArbol(arbol,0);
            break;
            }

            Limpiar();
        break;

        case 4:
            cout << "Yo soy buscar" << endl;
            if(arbol == NULL)
                cout << "Arbol vacio" << endl;
            else
            {
                do
                {
                   cout << "\nDato a Buscar: ";
                    cin >> bus;

                    if(Buscar(arbol,bus))
                        cout << "Dato econtrado" << endl;
                    else
                        cout << "Dato no encontrado" << endl;

                    cout << "Buscar otro dato(s/n): ";
                        cin >> res;
                    res = toupper(res);
                }while(res == 'S');
            }
            Limpiar();
        break;

        case 5:
            exit(0);
        break;
        }
    }
}

void Recorridos(void)
{
    cout << "1) PreOrden Inverso" << endl
         << "2) InOrden Inverso" << endl
         << "3) PostOrden Inverso" << endl
         << "4) PreOrde Converso" << endl
         << "5) InOrden Converso" << endl
         << "6) PostOrden Converso" << endl
         << "7) Niveles" << endl
         << "8) Mostrar Arbol" << endl
         << "Seleccione Opcion: ";
}

void Limpiar(void)
{
    cout << endl;
    system("pause");
    system("cls");
}

ABB CrearNodo(int x, ABB gfe)
{
    ABB q = new(struct Nodo);
    q -> dato = x;
    q -> gfe = gfe;

    return q;
}

void Insertar(ABB &arbol, int x, ABB gfe)
{
    if(arbol == NULL)
    {
        arbol = CrearNodo(x,gfe);
    }
    else
    {
        if(x == arbol -> dato)
            cout << "Dato repetido" << endl;
        else
        {
            if(x < arbol -> dato)
                Insertar(arbol -> izq,x,arbol);
            else
                Insertar(arbol -> der,x,arbol);
        }
    }
}

int Buscar(ABB arbol,int n)
{
    while(arbol)
    {
        if(n == arbol -> dato)
            return true;
        else
        {
            if(n < arbol -> dato)
                arbol = arbol -> izq;
            else
                arbol = arbol -> der;
        }
    }
    return false;
}

void ArbolCompleto(ABB arbol, int cont)
{
    if(arbol == NULL)
    {
        return;
    }
    else
    {
        ArbolCompleto(arbol -> der, cont+1);
        for(int i = 0 ; i < cont ; i++)
            cout << "   ";

        cout << arbol -> dato << endl;
        ArbolCompleto(arbol -> izq, cont+1);
    }
}

void PreIn(ABB arbol)
{
    if(arbol != NULL)
    {
        cout << arbol -> dato << " ";
        PreIn(arbol -> izq);
        PreIn(arbol -> der);
    }
}

void InIn(ABB arbol)
{
    if(arbol != NULL)
    {
        InIn(arbol -> izq);
        cout << arbol -> dato << " ";
        InIn(arbol -> der);
    }
}

void PostIn(ABB arbol)
{
    if(arbol != NULL)
    {
        PostIn(arbol -> izq);
        PostIn(arbol -> der);
        cout << arbol -> dato << " ";
    }
}

void PreOn(ABB arbol)
{
    if(arbol != NULL)
    {
        cout << arbol -> dato << " ";
        PreOn(arbol -> der);
        PreOn(arbol -> izq);
    }
}

void InOn(ABB arbol)
{
    if(arbol != NULL)
    {
        InOn(arbol -> der);
        cout << arbol -> dato << " ";
        InOn(arbol -> izq);
    }
}

void PostOn(ABB arbol)
{
    if(arbol != NULL)
    {
        PostOn(arbol -> der);
        PostOn(arbol -> izq);
        cout << arbol -> dato << " ";
    }
}

void MostrarArbol(ABB arbol, int auxY)
{
     if(arbol == NULL)
         return;

     auxX += 5;
     MostrarArbol(arbol -> izq,auxY+2);//Se para hasta el nodo mas a la izquierda del árbol

     gotoxy(5+auxX-auxY ,7+auxY);//posiciona el nodo segun sus variables en X y en Y

     cout << arbol -> dato << endl << endl;//Muestra el dato del nodo respectivo

     MostrarArbol(arbol -> der,auxY+2);//Se para hasta el nodo mas a la derecho del árbol
}

void gotoxy(int x,int y)
{
    coord.X=x;
    coord.Y=y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
}

//Eliminar nodo
void Eliminar(ABB arbol,int n)
{
    if(arbol == NULL)
        return;
    else if(n < arbol -> dato){
        Eliminar(arbol -> izq,n);
    }
    else if(n > arbol -> dato){
        Eliminar(arbol -> der,n);
    }
    else{
        EliminarNodo(arbol);
    }

}

//Funcion para determinar el nodo mas izq
ABB Minimo(ABB arbol)
{
    if(arbol == NULL)
        return NULL;

    if(arbol -> izq)
        return Minimo(arbol -> izq);
    else
        return arbol;
}

//Funcion para determinar el nodo mas der
ABB Maximo(ABB arbol)
{
    if(arbol == NULL)
        return NULL;

    if(arbol -> der)
        return Maximo(arbol -> der);
    else
        return arbol;
}

//Funcion para Reemplazar dos nodos(un hijo)
void Reemplazar(ABB arbol, ABB nuevoNodo)
{
    if(arbol -> gfe)
    {
        if(arbol -> dato == arbol -> gfe -> izq -> dato)
        {
            arbol -> gfe -> izq = nuevoNodo;
        }
        else if(arbol -> dato == arbol -> gfe -> der -> dato){
            arbol -> gfe -> der = nuevoNodo;
        }
    }

    if(nuevoNodo)
    {
        nuevoNodo -> gfe = arbol -> gfe;
    }
}

//Funcion para destruir un nodo
void DestruirNodo(ABB nodo)
{
    nodo -> izq = NULL;
    nodo -> der = NULL;

    delete nodo;
}

//Eliminar nodo encontrado
void EliminarNodo(ABB nodoEliminar)
{
    int op;
    if(nodoEliminar -> izq && nodoEliminar -> der)
    {
          cout   << "1) Sucesor" << endl
             << "2) Antesesor" << endl
            << "Que lado quieres elimiar: ";

            cin >> op;

        if(op == 1)
        {
            ABB menor = Minimo(nodoEliminar -> der);
            nodoEliminar -> dato = menor -> dato;
            EliminarNodo(menor);
        }
        else if(op == 2)
        {
            ABB menor = Maximo(nodoEliminar -> izq);
            nodoEliminar -> dato = menor -> dato;
            EliminarNodo(menor);
        }

    }
    else if(nodoEliminar -> izq){
        Reemplazar(nodoEliminar,nodoEliminar -> izq);
        DestruirNodo(nodoEliminar);
    }
    else if(nodoEliminar -> der){
        Reemplazar(nodoEliminar,nodoEliminar -> der);
        DestruirNodo(nodoEliminar);
    }
    else
    {
        Reemplazar(nodoEliminar,NULL);
        DestruirNodo(nodoEliminar);
    }
}

void Niveles(ABB arbol,int n)
{
    ABB aiz = new(struct Nodo);
    ABB ade = new(struct Nodo);
    if(n < 0)
        return;
    else
        if(n == 0)
        {
            if(arbol != NULL)
                cout << arbol -> dato << " ";
        }
        else
            if(arbol != NULL)
            {
                aiz = arbol -> izq; ade = arbol -> der;
                Niveles(aiz, n-1);
                Niveles(ade, n-1);
            }
}