AISD_Drzewa_v3

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <fstream>
#include <typeinfo>
#include <math.h>

using namespace std;

// struktura pojedynczego wezla
struct Element
{
    int klucz;
    Element *wsk_prawy;
    Element *wsk_lewy;
    Element *wsk_gora;
    // konstruktor automatycznie ustawia odpowiednie wartosci
    Element(int wartosc)
    {
        klucz = wartosc;
        wsk_prawy = NULL;
        wsk_lewy = NULL;
        wsk_gora = NULL;
    }
};

// generuje malejacy ciag o odpowiedniej dlugosci
void generate_sequence(int sequence_size, vector <int> &numbers)
{
    srand(time(NULL));
    numbers.push_back(rand()%100+1);
    for(int i = 1; i < sequence_size; i++)
    {
        numbers.insert(numbers.begin(), numbers[0]+rand()%100+1);
    }
}

// przeksztalca ciag poprzez polowienie binarne na ciag, ktory pozwoli zbudowac drzewo AVL
//                    FROM                  TO
void sequence_for_AVL(vector <int> numbers, vector <int> &numbers_altered, int lewy, int prawy)
{
    int srodek = (lewy+prawy)/2;
    //cout << "Numbers[srodek] " << "[" << srodek << "] " << numbers[srodek] << endl;
    numbers_altered.push_back(numbers[srodek]);
    // wywoluje polowienie rekurencyjnie
    if(srodek-lewy>0)
    {
        sequence_for_AVL(numbers, numbers_altered, lewy, srodek);
    }
    if(prawy-srodek>1)
    {
        sequence_for_AVL(numbers, numbers_altered, srodek+1, prawy);
    }
}

// dodaje element (wartosc) do drzewa
void add_element(Element* &wezel, int wartosc)
{
    // jezeli wezel jest pusty to po prostu wstawia na niego nowy element
    if(wezel == NULL)
    {
        wezel = new Element(wartosc);
    }
    // jezeli nie no to wywolujemy funkcje rekurencyjnie dla lewego syna lub prawego
    else
    {
        if(wartosc > wezel->klucz)
        {
            if(wezel->wsk_prawy == NULL)
            {
                wezel->wsk_prawy = new Element(wartosc);
                wezel->wsk_prawy->wsk_gora = wezel;
            }
            else
            {
                add_element(wezel->wsk_prawy, wartosc);
            }

        }
        if(wartosc < wezel->klucz)
        {
            if(wezel->wsk_lewy == NULL)
            {
                wezel->wsk_lewy = new Element(wartosc);
                wezel->wsk_lewy->wsk_gora = wezel;
            }
            else
            {
                add_element(wezel->wsk_lewy, wartosc);
            }
        }
    }
}

void wyszukaj_MAX(Element* wezel)
{
    if(wezel->wsk_prawy == NULL)
    {
        cout << endl;
        cout << "MAX: " << wezel->klucz << endl;
        cout << "---KONIEC PROCEDURY---" << endl;
    }
    else
    {
        cout << wezel->klucz << " ";
        wyszukaj_MAX(wezel->wsk_prawy);
    }
}

void wyszukaj_MIN(Element* wezel)
{
    if(wezel->wsk_lewy == NULL)
    {
        cout << endl;
        cout << "MIN: " << wezel->klucz << endl;
        cout << "---KONIEC PROCEDURY---" << endl;
    }
    else
    {
        cout << wezel->klucz << " ";
        wyszukaj_MIN(wezel->wsk_lewy);
    }
}

Element* wyszukaj_nastepnik(Element* wezel)
{
    while(wezel->wsk_lewy!=NULL)
    {
        wezel = wezel->wsk_lewy;
    }
    return wezel;
}

Element* wyszukaj_element(int klucz, Element* wezel)
{
    //cout << "Wywolanie funkcji: " << wezel->klucz << " Adres: " << wezel  << endl;
    if(wezel == NULL)
    {
        return NULL;
    }

    if(wezel->klucz == klucz)
    {
        return wezel;
    }
    else if(klucz > wezel->klucz)
    {
        wyszukaj_element(klucz, wezel->wsk_prawy);
    }
    else
    {
        wyszukaj_element(klucz, wezel->wsk_lewy);
    }
}

void usuwanie_elementu(int klucz, Element* &wezel)
{
     if(wezel == NULL)
        return;
    if(wezel->klucz == klucz)
    {
        //cout << "Znaleziono klucz!" << endl;
        if(wezel->wsk_prawy == NULL && wezel->wsk_lewy == NULL)
        {
            //cout << "brak dzieci" << endl;
            if(wezel->wsk_gora->klucz > wezel->klucz)
            {
                wezel->wsk_gora->wsk_lewy = NULL;
            }
            else
            {
                wezel->wsk_gora->wsk_prawy = NULL;
            }
            delete wezel;
        }
        else if(wezel->wsk_prawy == NULL)
        {
            Element *tmp_adress = wezel->wsk_lewy;
            wezel->klucz = wezel->wsk_lewy->klucz;
            wezel->wsk_prawy = tmp_adress->wsk_prawy;
            wezel->wsk_lewy = wezel->wsk_lewy->wsk_lewy;
            delete tmp_adress;
        }
        else if(wezel->wsk_lewy == NULL)
        {
            Element *tmp_adress = wezel->wsk_prawy;
            wezel->klucz = wezel->wsk_prawy->klucz;
            wezel->wsk_prawy = wezel->wsk_prawy->wsk_prawy;
            wezel->wsk_lewy = tmp_adress->wsk_lewy;
            delete tmp_adress;
        }
        else
        {
            Element *nastepnik = wyszukaj_nastepnik(wezel->wsk_prawy);
            Element *syn_nastepnika = nastepnik->wsk_prawy;
            wezel->klucz = nastepnik->klucz;
            nastepnik->klucz = syn_nastepnika->klucz;
            nastepnik->wsk_prawy = syn_nastepnika->wsk_prawy;
            nastepnik->wsk_lewy = syn_nastepnika->wsk_lewy;
            delete syn_nastepnika;
        }
    }
    else if(klucz > wezel->klucz)
    {
        usuwanie_elementu(klucz, wezel->wsk_prawy);
    }
    else
    {
        usuwanie_elementu(klucz, wezel->wsk_lewy);
    }
}

// wyswietla cale drzewo w porzadku pre-order
void wyswietl_preorder(Element* wezel)
{
    if(wezel == NULL)
        return;
    cout << wezel->klucz << " ";
    // wersja robocza
    //cout << wezel->klucz << " Lewy: " << wezel->wsk_lewy << " Prawy: " << wezel->wsk_prawy << " Góra: " << wezel->wsk_gora << endl;
    wyswietl_preorder(wezel->wsk_lewy);
    wyswietl_preorder(wezel->wsk_prawy);
}

// wyswietla cale drzewo w porzadku in-order
void wyswietl_inorder(Element* wezel)
{
    if(wezel == NULL)
        return;
    wyswietl_inorder(wezel->wsk_lewy);
    cout << wezel->klucz << " ";
    wyswietl_inorder(wezel->wsk_prawy);
}


// usuwa cale drzewo w porzadku post-order
void usun_postorder(Element* &wezel)
{
    if(wezel == NULL)
        return;
    usun_postorder(wezel->wsk_lewy);
    usun_postorder(wezel->wsk_prawy);
    delete wezel;
}

// dotyczy rotacji
void zmiana_na_liste(Element* &pseudo_root)
{
    Element* ogon = pseudo_root;
    Element* pozostalosc = pseudo_root->wsk_prawy;
    while(pozostalosc!=NULL)
    {
        if(pozostalosc->wsk_lewy==NULL)
        {
            ogon = pozostalosc;
            pozostalosc = pozostalosc->wsk_prawy;
        }
        else
        {
            Element* temp = pozostalosc->wsk_lewy;
            pozostalosc->wsk_lewy = temp->wsk_prawy;
            temp->wsk_prawy = pozostalosc;
            pozostalosc = temp;
            ogon->wsk_prawy = temp;
        }
    }
}

//dotyczy rotacji
void kompresuj(Element* &pseudo_root, int licznik)
{
    Element* skaner = pseudo_root;
    for(int i = 0; i<licznik; i++)
    {
        Element* dziecko = skaner->wsk_prawy;
        skaner->wsk_prawy = dziecko->wsk_prawy;
        skaner = skaner->wsk_prawy;
        dziecko->wsk_prawy = skaner->wsk_lewy;
        skaner->wsk_lewy = dziecko;
    }
}

//dotyczy rotacji
void lista_na_drzewo(Element* &pseudo_root, int wielkosc)
{
    int ilosc_lisci = wielkosc + 1 - pow(2, log2(wielkosc+1));
    kompresuj(pseudo_root, ilosc_lisci);
    wielkosc = wielkosc - ilosc_lisci;
    while(wielkosc > 1)
    {
        kompresuj(pseudo_root, wielkosc/2);
        wielkosc = wielkosc/2;
    }
}

// rownowarzenie drzewa
Element* rotacja_DSW(Element* &wezel, int wielkosc)
{
    // tworzy kopie korzenia drzewa
    Element* pseudo_root = new Element(NULL);
    pseudo_root->wsk_prawy = wezel;
    zmiana_na_liste(pseudo_root);
    lista_na_drzewo(pseudo_root, wielkosc);
    wezel = pseudo_root->wsk_prawy;
    delete pseudo_root;
}

int main()
{
    int sequence_size;
    bool proper_value;
    bool quit = false;
    bool good_input = false;
    int choice;
    int klucz_poddrzewa;
    int ile_usunac;
    int klucz_usuwania;
    bool user_input;
    vector <int> numbers;
    vector <int> numbers_altered;
    Element *root_BST = NULL;
    Element *root_AVL = NULL;
    Element *szukany = NULL;
    while(!quit)
    {
        proper_value = false;
        while(!proper_value)
        {
            cout << "Podaj wielkosc ciagu malejacego: ";
            cin >> sequence_size;
            if(cin && sequence_size > 0)
            {
                generate_sequence(sequence_size, numbers);
                sequence_for_AVL(numbers, numbers_altered, 0, numbers.size());
                // tworzenie drzew BST i AVL
                for(int i = 0; i<numbers.size(); i++)
                {
                    add_element(root_BST, numbers[i]);
                    add_element(root_AVL, numbers_altered[i]);
                }
                // wyjscie z petli wewnetrznej programu
                proper_value = true;
            }
        }
        while(!good_input)
        {
            // do zrobienia:  7 jeszcze jest wyszukaj MIN XD, trzeba by tu pozmienaic numerki
            cout << "Wybierz akcje: 1)Wyszukaj MAX, 2)Usun wybrane wezly, 3)Wypisz pre-order" << endl;
            cout << "4)Wypisz in-order, 5)Usun drzewo post-order, 6)Wypisz poddrzewo (pre-order)," << endl;
            cout << "7)Rownowarz drzewo BST(DSW), 8)Wyjscie, Wybor:";
            cin >> choice;
            if(!cin || choice < 0 || choice >= 9)
            {
                cout << "Wybrano bledna akcje!" << endl;
                exit(0);
            }
            switch(choice)
            {
            case 1:
                cout << "Sciezka BST: ";
                wyszukaj_MAX(root_BST);
                cout << endl;
                cout << "Sciezka AVL: ";
                wyszukaj_MAX(root_AVL);
                break;
            case 2:
                ile_usunac = 0;
                klucz_usuwania = 0;
                user_input = false;
                while(!user_input)
                {
                    cout << "Ile wezlow usunac?:";
                    cin >> ile_usunac;
                    if(cin && ile_usunac > 0 && ile_usunac < numbers.size())
                    {
                        user_input = true;
                    }
                }
                for(int i = 1; i<=ile_usunac; i++)
                {
                    cout << "[" << i << "] klucz:";
                    cin >> klucz_usuwania;
                    if(!cin)
                    {
                        cout << "Zly input!" << endl;
                        exit(0);
                    }
                    else
                    {
                        // usuwanie z drzewa BST
                        cout << "Usuwanie wezla z drzewa BST!" << endl;
                        szukany = wyszukaj_element(klucz_usuwania, root_BST);
                        usuwanie_elementu(klucz_usuwania, szukany);
                        // usuwanie z drzewa AVL
                        cout << "Usuwanie wezla z drzewa AVL!" << endl;
                        szukany = wyszukaj_element(klucz_usuwania, root_AVL);
                        usuwanie_elementu(klucz_usuwania, szukany);
                    }
                }
                break;
            case 3:
                cout << "BST pre-order: " << endl;
                wyswietl_preorder(root_BST);
                cout << endl;
                cout << "--- KONIEC PROCEDURY ---" << endl;
                cout << "AVL pre-order: " << endl;
                wyswietl_preorder(root_AVL);
                cout << endl;
                cout << "--- KONIEC PROCEDURY ---" << endl;
                break;
            case 4:
                cout << "BST in-order: " << endl;
                wyswietl_inorder(root_BST);
                cout << endl;
                cout << "--- KONIEC PROCEDURY ---" << endl;
                cout << "AVL in-order: " << endl;
                wyswietl_inorder(root_AVL);
                cout << endl;
                cout << "--- KONIEC PROCEDURY ---" << endl;
                break;
            case 5:
                cout << "BST usun post-order... " << endl;
                usun_postorder(root_BST);
                cout << endl;
                cout << "--- KONIEC PROCEDURY ---" << endl;
                cout << "AVL usun post-order... " << endl;
                usun_postorder(root_AVL);
                cout << endl;
                cout << "--- KONIEC PROCEDURY ---" << endl;
                break;
            case 6:
                cout << "Wypisywanie poddrzewa. Podaj klucz: ";
                cin >> klucz_poddrzewa;
                if(!cin)
                {
                    cout << "Blad wejscia!" << endl;
                    exit(0);
                }
                cout << "PODDRZEWO Z BST...: ";
                if(wyszukaj_element(klucz_poddrzewa, root_BST) == NULL)
                {
                    cout << "Nie znaleziono wezla w strukturze o podanym kluczu!" << endl;
                }
                else
                {
                    //cout << "Adres wyszukany: " << wyszukaj_element(klucz_poddrzewa, root_BST) << endl;
                    wyswietl_preorder(wyszukaj_element(klucz_poddrzewa, root_BST));
                    cout << endl;
                }
                cout << "PODDRZEWO Z AVL...: ";
                if(wyszukaj_element(klucz_poddrzewa, root_AVL) == NULL)
                {
                    cout << "Nie znaleziono wezla w strukturze o podanym kluczu!" << endl;
                }
                else
                {
                    //cout << "Adres wyszukany: " << wyszukaj_element(klucz_poddrzewa, root_AVL) << endl;
                    wyswietl_preorder(wyszukaj_element(klucz_poddrzewa, root_AVL));
                    cout << endl;
                }
                cout << "--- KONIEC PROCEDURY ---" << endl;
                break;
            case 7:
                rotacja_DSW(root_BST, sequence_size);
                rotacja_DSW(root_AVL, sequence_size);
                break;
            case 8:
                exit(0);
                break;
            }
        }
    }
    return 0;
}