Proyecto AVL Y ABB

[Ucles016]

define _CRT_SECURE_NO_WARNINGS

include

include

                #include <cstdlib>

include

               #include <fstream>

include

            #include <sstream>

include

define pow2(n) (1 << (n)) //se dine una la constante n elevandola al cuadrado

using namespace std;

//creamos la funcion gotoxy para poder utilizar gotoxy void gotoxy(int x = 0, int y = 0) { HANDLE hcon; hcon = GetStdHandle(STD_OUTPUT_HANDLE); COORD dwPos; dwPos.X = x; dwPos.Y = y; SetConsoleCursorPosition(hcon, dwPos); }

struct nodo { //struct nodo lo creamos para el arbol binario //la raiz que va ser tipo int (entero) int nro; struct nodo izq, der, *padre; //creamos 3 punteros de tipo nodo para el arbol binario }; struct avl_nodo //struct avl_nodo lo creamos para el arbol balanceado { int data; //entero que guardara los datos en los nodos

struct avl_nodo *izq;    //puntero tipo struct avl_nodo
struct avl_nodo *der;    //puntero tipo struct avl_nodo

}*raiz; //creamos un puntero llamado raiz

//identifacamos a nodo como ABB typedef struct nodo *ABB;

//protos

bool Busqueda(ABB &arbol, int n); void Eliminarnodo(nodo ); nodo minimo(nodo ); void reemplazar(nodo, nodo ); void destruirNodo(nodo ); void Elm(); void menu(); void crear(); void ordenamiento();

// funciones publicas de avl

class avlTree { public: int A(avl_nodo ); int diff(avl_nodo ); avl_nodo rr_rotation(avl_nodo ); avl_nodo ll_rotation(avl_nodo ); avl_nodo lr_rotation(avl_nodo); avl_nodo rl_rotation(avl_nodo); avl_nodo balance(avl_nodo ); avl_nodo insert(avl_nodo , int); void verAvl(avl_nodo *, int);

avlTree()
{
    int raiz = NULL;
}

};

//variables Globales int n = 0; int x; //dato de tipo entero publico char *ptrc; //puntero tipo char string contenido2; //de tipo string publica int auxX = 0;//Variable publica. char linea[128]; //vector tipo char ABB arbol = NULL; //arbol tipo struct ABB int datos; //de tipo entero publico int choice, item; // de tipo entero avlTree avl; // avl tipo struct avltree

ABB crearNodo(int x, nodo padre) //crear nodo sera de tipo struct nodo { ABB nuevoNodo = new nodo; //intaciamos creamos un nuevo nodo nuevoNodo->nro = x; //nuevo nodo apunta raiz es igual a x nuevoNodo->izq = NULL; // nuevo nodo apunta al nodo izq es igual a nulo nuevoNodo->der = NULL; // nuevo nodo apunta al nodo der es igual a nulo nuevoNodo->padre = padre; // nuevo nodo apunta al nodo padre y es igual al nodo padre return nuevoNodo; // retornamos el valor del nuevo nodo } int avlTree::A(avl_nodo temp) //Funcion para calcular la altura { int h = 0; if (temp != NULL) { int l_height = A(temp->izq); int r_height = A(temp->der); int max_height = max(l_height, r_height); h = max_height + 1; } return h; } int avlTree::diff(avl_nodo temp) //Funcion para calcular la diferencia de altura entre izquierda y derecha { int l_height = A(temp->izq); int r_height = A(temp->der ); int b_factor = l_height - r_height; return b_factor; } avl_nodo avlTree::rr_rotation(avl_nodo parent) //hace la rotacion de izquierda a izquierda { avl_nodo temp; temp = parent->der; parent->der= temp->izq; temp->izq = parent; return temp; } avl_nodo avlTree::ll_rotation(avl_nodoparent) //Hace la rotacion de derecha a derecha { avl_nodo *temp; temp = parent->izq; parent->izq = temp->der; temp->der= parent; return temp; }

avl_nodo avlTree::lr_rotation(avl_nodoparent)//hace la rotacion de derecha a izquierda { avl_nodo *temp; temp = parent->izq; parent->izq = rr_rotation(temp); return ll_rotation(parent); }

avl_nodo avlTree::rl_rotation(avl_nodo parent)// hace la rotacion de izquierda a derecha { avl_nodo *temp; temp = parent->der; parent->der = ll_rotation(temp); return rr_rotation(parent); }

avl_nodo avlTree::balance(avl_nodo temp) // calculamo el factor de balance (equilibrio) del arbol { int bal_factor = diff(temp); if (bal_factor > 1) { if (diff(temp->izq) > 0) temp = ll_rotation(temp); else temp = lr_rotation(temp); } else if (bal_factor < -1) { if (diff(temp->der) > 0) temp = rl_rotation(temp); else temp = rr_rotation(temp); } return temp; }

avl_nodo avlTree::insert(avl_nodo raiz, int x) //insertamos los valores de x al avl { if (raiz == NULL) { raiz = new avl_nodo; raiz->data = x; raiz->izq = NULL; raiz->der= NULL; return raiz; } else if (x < raiz->data) { raiz->izq = insert(raiz->izq, x); raiz = balance(raiz); } else if (x >= raiz->data) { raiz->der= insert(raiz->der, x); raiz = balance(raiz); } return raiz; }

void insertar(ABB &arbol, int x, nodo *padre) //insertamos los valores del ABB { if (arbol == NULL) { arbol = crearNodo(x, padre);

}
else if (x < arbol->nro)
    insertar(arbol->izq, x, arbol);
else if (x > arbol->nro)
    insertar(arbol->der, x, arbol);

}

void preOrden(ABB arbol) //calculamos el preorden de los datos { if (arbol != NULL) { cout << arbol->nro << " "; preOrden(arbol->izq); preOrden(arbol->der); } }

void enOrden(ABB arbol) //calculamos el preorden de los datos { if (arbol != NULL) { enOrden(arbol->izq); cout << arbol->nro << " "; enOrden(arbol->der); } }

void postOrden(ABB arbol) //calculamos el preorden de los datos { if (arbol != NULL) { postOrden(arbol->izq); postOrden(arbol->der); cout << arbol->nro << " "; } } int contar_hojas(nodo *p) //calculamos las cantidades de hojas que tiene el arbol { if (p == NULL) return 0; else if (p->izq == NULL && p->der == NULL) return 1; else return contar_hojas(p->izq) + contar_hojas(p->der); }

void verArbol(ABB arbol, int auxY = 0) //Funcion para poder colocar el arbol BINARIO verticalmente {

if (arbol == NULL)
{//Arbol vacio nada que mostrar

    return;
}

auxX += 7.2;//variable que permite posicionarse en el eje X

verArbol(arbol->izq, auxY + 3); //Se para hasta el nodo mas a la izquierda del árbol construye primero el subarbol izq porque sus valores en X son menores
if (arbol->izq != NULL)

{
    gotoxy(21.5 + auxX - auxY, 26.5 + auxY);
    cout << " / ";

}
else if (arbol->der != NULL)
{
    gotoxy(21.5 + auxX - auxY, 26.5 + auxY);
    cout << " \\";

}
else if ((arbol->der == NULL) || (arbol->izq == NULL)) {
    gotoxy(21.5 + auxX - auxY, 26.5 + auxY);
    cout << " /";

}
else {
    gotoxy(21.5 + auxX - auxY, 26.5 + auxY);
    cout << " \\";

}

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

cout << "|" << arbol->nro << "|";//Muestra el dato del nodo respectivo

verArbol(arbol->der, auxY + 4);

}

void avlTree::verAvl(avl_nodo *ptr, int auxY) //Funcion para poder colocar el arbol BALANCEADO verticalmente { if (ptr != NULL) { //Arbol vacio nada que mostrar

    auxX += 7;//variable que permite posicionarse en el eje X

    verAvl(ptr->izq, auxY + 4);//Se para hasta el nodo mas a la izquierda del árbol construye primero el subarbol izq porque sus valores en X son menores

    if (ptr->izq == ptr->izq)

    {
        gotoxy(21.5 + auxX - auxY, 29.5 + auxY);
        cout << " /";

    }
    else if (ptr->der != ptr->der)
    {
        gotoxy(21.5 + auxX - auxY, 29.5 + auxY);
        cout << " \\";

    }
    else if ((ptr->der == NULL) || (ptr->izq == NULL)) {
        gotoxy(21.5 + auxX - auxY, 29.5 + auxY);
        cout << "\\";

    }
    else {
        gotoxy(21.5 + auxX - auxY, 29.5 + auxY);
        cout << " /";

    }

    gotoxy(20 + auxX - auxY, 30 + auxY);//posiciona el nodo segun sus variables en X y en Y
    if (ptr == raiz) {
        gotoxy(21.5 + auxX - auxY, 29.5 + auxY);
        cout << " ";
    }
    cout << "|" << ptr->data << "|";//Muestra el dato del nodo respectivo

    verAvl(ptr->der, auxY + 4);
}

}

bool Busqueda(ABB &arbol, int n) { //Creamos una busquedad para el arbol if (arbol == NULL) { return false; } else if (arbol->nro == n) { return true; } else if (n< arbol->nro) { return Busqueda(arbol->izq, n); } else { return Busqueda(arbol->der, n); } system("pause>null");

} void Eliminar(nodo *arbol, int n) //FUncion sirve para poder eliminar nodos del arbol

{ if (arbol == NULL) { return; } else if (nnro) { Eliminar(arbol->izq, n);//si el valor es menor busca por la izquierda

}
else if (n>arbol->nro) {
    Eliminar(arbol->der, n);//si es mayor vamos a buscar por la derecha
}
else// si noo es mayor ni menor y el arbol no esta vacio "lo encontramos"
{

    Eliminarnodo(arbol);
}

}

//funcion para determinar el nodo mas izquierdo posible

nodo minimo(nodo arbol) //funcion para encontrar el mimnimo { if (arbol == NULL) { return NULL; } else if (arbol->izq) {//si tiene hijo izq return minimo(arbol->izq); } else if (arbol->der) {//si tiene hijo der return minimo(arbol->der); } else { return arbol; //si no tinen hijo izq le regresamos el misno nodo

}

} void Eliminarnodo(nodo *nodoEliminar) {

//puede ser hoja 0 hijos
//hijo izquierdo o derecho

//eliminacion con 2 subarboles hijos
if (nodoEliminar->izq && nodoEliminar->der) {
    nodo *menor = minimo(nodoEliminar->der);
    nodoEliminar->nro = menor->nro;
    Eliminarnodo(menor);
}
else if (nodoEliminar->izq) {//si tiene hijo izq
    reemplazar(nodoEliminar, nodoEliminar->izq);
    destruirNodo(nodoEliminar);
}
else if (nodoEliminar->der) {//si tiene hijo der
    reemplazar(nodoEliminar, nodoEliminar->der);
    destruirNodo(nodoEliminar);
}
else {//nodo terminal
    reemplazar(nodoEliminar, NULL);
    destruirNodo(nodoEliminar);

}

} void reemplazar(nodo arbol, nodo nuevoNodo) { if (arbol->padre) { //arbol->padre hay que asignarle el nuevo hijo if (arbol->nro <= arbol->padre->izq->nro) { arbol->padre->izq = nuevoNodo; }

    else if (arbol->nro <= arbol->padre->der->nro) {
        arbol->padre->der = nuevoNodo;
    }

}

if (nuevoNodo) {
    //asignarle su nuevo padre
    nuevoNodo->padre = arbol->padre;

}

} void destruirNodo(nodo *nodo) { nodo->izq = NULL; nodo->der = NULL;

delete nodo;

} void LimpiarArbol(ABB &arbol) //limpiamos completamente el arbol

{

if (arbol == NULL)
    return;
if (arbol->der == NULL)
{
    if (arbol->izq == NULL)
    {
        delete(arbol);
    }
    else
    {
        LimpiarArbol(arbol->izq);
    }

}
else {
    LimpiarArbol(arbol->der);
}

}

void menu() { //Menu PRINCIPAL system("color 70");

int op;
do {
system("cls");

gotoxy(2, 49); cout << " ******************* ";
gotoxy(2, 50); cout << "1.ver ABB \n";
gotoxy(2, 51); cout << "2.ver Avl \n";
gotoxy(2, 52); cout << "3.Eliminar \n";
gotoxy(2, 53); cout << "4.Ordenamientos \n";
gotoxy(2, 54); cout << "5.Buscar \n";
gotoxy(2, 55); cout << "0. Salirn\n";
      cout << endl;
gotoxy(2, 56); cout << "Seleccione una Opcion -";
cin >> op;

    switch (op)
    {
    case 1:
    {

        verArbol(arbol, 0);
         auxX = 0;
        system("pause> null");

        break;

    }
    case 2:
    {

        avl.verAvl(raiz, 0);
        auxX = 0;
        system("pause> null");

        break;
    }
    case 3:
    {

        Elm();

        system("pause> null");

        break;
    }
    case 4: {

        ordenamiento();
        system("pause>null");

        break;
    }
    case 5: {

        cout << "\t\t Buscar \n\n";
        cout << "\t\tIngrese el elemento a buscar - ";
        cin >> datos;

        if (Busqueda(arbol, datos) == true) {
            cout << "\t\t El Elemento - dato   Ha sido encontrado   \n";
        }
        else {
            cout << "\t\t elemento no encontradon";

        }

        system("pause>null");

        break;

    }

    }

} while (op != 0);

system("pause< null");

} void Elm() {

auxX = 0;
cout << endl << endl << endl << endl;
string contenido1;
contenido1 += "PatitoBinario.txt";
ifstream fs(contenido1, ios::in);
char linea1[128];
long contador = 0L;
if (fs.fail())
    cerr << "El fichero no existe" << endl;
else
    while (!fs.eof()) {
        while (!fs.eof()) {
            fs.getline(linea, sizeof(linea));

        }
        gotoxy(7, 57); cout << "DATOS PARA ELIMINAR : " << linea << endl;

        cin.get();
    }

gotoxy(4, 58); cout << "\t\t********* Eliminar *************\n\n";
gotoxy(4, 59); cout << "\t\tDigite el Numero a Eliminar -> ";

cin >> datos;

Eliminar(arbol, datos);

}

void crear() { system("cls"); string conten; gotoxy(35, 15); cout << "Ingresa el nombre del archivo a crear(sin el .txt): "; cin.ignore(); getline(cin, contenido2); gotoxy(35, 16); cout << "Ingresa los datos o numero de nodos para el arbol: "; getline(cin, conten); contenido2 += ".txt"; ofstream fs(contenido2.c_str()); fs << conten << endl; fs.close(); gotoxy(35, 21); cout << "El archivo ha sido creado correctamente presiona ENTER para continuar" << endl;

} void ordenamiento() {

    gotoxy(5, 57); cout << "**********ordenamientos*********";

    gotoxy(2, 58); cout << " En orden   :  ";   gotoxy(15, 58);   enOrden(arbol);
    gotoxy(2, 59); cout << " Pre Orden  :  ";  gotoxy(15, 59); preOrden(arbol);
    gotoxy(2, 60); cout << " Post Orden :  ";  gotoxy(15, 60); postOrden(arbol);
    gotoxy(2, 61); printf("*Numero de hojas: %d\n", contar_hojas(arbol));
    gotoxy(3, 62); cout << " * numero de nodos : " << n;
    gotoxy(4, 63); cout << "  *suma de nodos y hojas : " << n + contar_hojas(arbol);

    cout << endl << endl;

}

void main() { system(" color 70"); int opcion; int n = 0; // numero de nodos del arbol

do {
menu1:
    system("cls");
    gotoxy(35, 15); cout << "Hola, Bienvenido al Generador de Arboles, ";
    gotoxy(35, 16); cout << "para continuar y crear tu arbol presiona - 1 -";
    gotoxy(35, 17); cout << "(si no tienes ningun archivo, puedes crear uno, presionando -2-)";
    gotoxy(35, 18); cout << "--->"; cin >> opcion;
    switch (opcion) {
    case 0:
        break;
    case 1:
    {
        gotoxy(35, 19); cout << "Necesito que ingreses el nombre de tu archivo";

        gotoxy(35, 20); cout << "(sin el .txt): ";

        cin.ignore();
        getline(cin, contenido2);
        contenido2 += ".txt";
        ifstream fs(contenido2.c_str(), ios::in);
        long contador = 0L;
        if (fs.fail()) {
            gotoxy(35, 20); cerr << "El fichero no existe deseas crear uno?" << endl;
            gotoxy(35, 21); cout << "Presiona 2 para crear >";
            cin >> opcion;
            if (opcion == 2)
            {
                crear();
            }
        }
        else {

            fs.getline(linea, sizeof(linea));
            cout << "Datos >   " << " " << linea;

        }
        ptrc = strtok(linea, ",");

        for (int i = 0; i <= n; i++)
        {

            while (ptrc != NULL)
            {

                x = atoi(ptrc);

                ptrc = strtok(NULL, ",");
                n++;

                insertar(arbol, x, NULL);
                raiz = avl.insert(raiz, x);

            }

        }
        system("pause>nul");
        menu();
        break;

    }
    case 2:
    {

        crear();
        system("pause>nul");
        goto menu1;
        break;

    }

    }

} while (opcion !=0); system("Pause>NULL");

}

[Ucles016]

proyecto final donde mostramos el 2 arboles graficamente abb y avl